Informatikwiki

Albert Einstein Gymnasium Reutlingen

Benutzer-Werkzeuge

Webseiten-Werkzeuge

algorithmen:algolektion03
    Sie befinden sich hier: start » algorithmen » algolektion03

    Unterschiede

    Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

    Link zu dieser Vergleichsansicht

    Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
    Nächste Überarbeitung    		Vorhergehende Überarbeitung
    algorithmen:algolektion03 [18.11.2011 14:20] – Stefan Gaumalgorithmen:algolektion03 [09.11.2014 15:47] (aktuell) – Stefan Gaum
    Zeile 1: Zeile 1:
    -[[algorithmen:algolektion02|Lektion 2 - Übungen]]+[[algorithmen:algolektion02|Lektion 3 - Übungen]]
      
      
    -====== Sortieren ======+====== Lektion 4 - Sortieren ======
      
     Sortierverfahren sind von großer Bedeutung für die Informatik, siehe auch  Sortierverfahren sind von großer Bedeutung für die Informatik, siehe auch 
    Zeile 30: Zeile 30:
      
      
    -===== Sortieren durch Auswahl (Selection Sort) =====+===== Sortieren durch Auswahl (Selectionsort) ===== 
     +[[http://de.wikipedia.org/wiki/Selectionsort|Selectionsort]] bei Wikipedia
      
     Beim Sortieren durch Auswahl wird das kleinste Element des unsortierten Bereichs gesucht, ausgewählt und schließlich mit dem Grenzelement vertauscht. Die Grenze wird anschließend um einen Schritt weitergeschoben, bis das Ende erreicht ist => vgl. Abbildung: Beim Sortieren durch Auswahl wird das kleinste Element des unsortierten Bereichs gesucht, ausgewählt und schließlich mit dem Grenzelement vertauscht. Die Grenze wird anschließend um einen Schritt weitergeschoben, bis das Ende erreicht ist => vgl. Abbildung:
    Zeile 42: Zeile 43:
     Im nachstehenden Struktogramm wird eine variable Anzahl von Elementen sortiert. Die Variablen **//kleinstes//** und //**grenze**// beschreiben dabei die //Position// des kleinsten Elementes bzw. des Grenzelementes, und NICHT das Element selber. Vorteil ist, dass sich so der Algorithmus auf verschiedene Datentypen (Zeichen, Zahlen, Buchstaben) anwenden lässt. Im nachstehenden Struktogramm wird eine variable Anzahl von Elementen sortiert. Die Variablen **//kleinstes//** und //**grenze**// beschreiben dabei die //Position// des kleinsten Elementes bzw. des Grenzelementes, und NICHT das Element selber. Vorteil ist, dass sich so der Algorithmus auf verschiedene Datentypen (Zeichen, Zahlen, Buchstaben) anwenden lässt.
      
    -{{:algorithmen:selectsort.jpg|}}+{{:algorithmen:selectsort2.jpg|}}
      
     +[[http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html|Animation für einen Selectionsort]]
      
     ===== Aufgaben ===== ===== Aufgaben =====
    Zeile 50: Zeile 52:
      
       - Sortiere die Zahlen 7, 5, 3, 8, 4, 6, 1, 2, 9 auf einem Blatt Papier nach dem Auswahlverfahren.   - Sortiere die Zahlen 7, 5, 3, 8, 4, 6, 1, 2, 9 auf einem Blatt Papier nach dem Auswahlverfahren.
    -  - Folge dem [[funktionen:funktionen|Arbeitsplan Sortieren mit Selection-Sort]]+  - Folge dem Struktogramm und programmiere einen code für diesen Sortieralgorithmus.
       - Gib den Mittelwert der Listenelemente aus.   - Gib den Mittelwert der Listenelemente aus.
       - Wie viele Elemente sind größer bzw. kleiner als der Mittelwert?   - Wie viele Elemente sind größer bzw. kleiner als der Mittelwert?
      
      
    -===== Lösungsvorschlag =====+[[algorithmen:algolektionl1|Lösungsvorschlag]]
      
    -<code php> 
    -  <form action="sortieren.php" method="POST"> 
    -  <input type="text"  name="zahlen" /> 
    -  <input type="submit" value="Do it!" /> 
    -  </form> 
          
    -  <?php +[[algorithmen:algolektion04|Lektion 5 - Pseudocode]]
    -  $jetzt = microtime(); +
    -  print $jetzt; +
    -  $zahlen = $_POST['zahlen']; +
    -  $einzelzahlen = explode(" ", $zahlen); +
    -  $anzahl = count($einzelzahlen); +
    -   +
    -  //echo $anzahl; +
    -  //print_r($einzelzahlen); +
    -   +
    -  // Alle "leeren" Elemente rauswerfen +
    -  $dieguten = array(); +
    -  for( $i=0; $i<$anzahl; $i++) { +
    -      if( is_numeric($einzelzahlen[$i])){ +
    -     print "Index $i: $einzelzahlen[$i] ist Zahl<br />"; +
    -     $dieguten[] = $einzelzahlen[$i]; +
    -      }  +
    -  }  +
    -   +
    -  print_r($dieguten); +
    -   +
    -  $anzahl = count($dieguten); +
    -  $grenze = 0; +
    -   +
    -  while($grenze < $anzahl) { +
    -  // kleinstes Element suchen +
    -  $index_min = $grenze; +
    -  for( $i = $grenze; $i<$anzahl; $i++) { +
    -  if ($dieguten[$i] < $dieguten[$index_min]) { +
    -  $index_min = $i; +
    -  } +
    -  } +
    -  // $dieguten[$index_min] ist das kleinste Element# +
    -  // vertausche $dieguten[$grenze] mit $dieguten[$index_min] +
    -  $zwischen = $dieguten[$grenze]; +
    -  $dieguten[$grenze] = $dieguten[$index_min]; +
    -  $dieguten[$index_min] = $zwischen; +
    -  // Grenze eins nach rechts +
    -  $grenze++; +
    -  }  +
    -  $zeit = microtime() - $jetzt; +
    -    +
    -  print_r($dieguten); +
    -   +
    -  print "dauer: $zeit"; +
    -  ?> +
    -</code> +
    - +
    -   +
    -[[algorithmen:algolektion04|Lektion 4 - Pseudocode]]+
    Zuletzt angesehen: • algolektion03
    algorithmen/algolektion03.1321626012.txt.gz · Zuletzt geändert: 18.11.2011 14:20 von Stefan Gaum
    Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki