Algorithmen 2

Sortieren

Sortierverfahren sind von großer Bedeutung für die Informatik, siehe auch http://de.wikipedia.org/wiki/Sortierverfahren

Vielen Sortierverfahren liegt das folgende Modell zugrunde ⇒ vgl. Abbildung:

zu Beginn liegt ein sortierter und ein unsortierter Datenbereich vor

beide Datenbereiche werden durch ein Grenzelement voneinander getrennt

anfangs besteht der sotrierte Haufen aus nur einem einzigen Element (hier die „7“), dem Grenzelement

Das Grenzelement wird während des Sortiervorgangs von links nach rechts geschoben, bis das ganze Zahlenfeld durchlaufen ist

Tauschen von Elementen

Möchte man zwei Elemente miteinander vertauschen, so wird ein Algorithmus mit dem Ansatz

feld[i] = feld[j];
feld[j] = feld[i];

nicht zum gewünschten Ergebnis führen, warum? Berichtige den Code.

Sortieren durch Auswahl (Selection Sort)

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:

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.

Aufgaben

Sortiere die Zahlen 7, 5, 3, 8, 4, 6, 1, 2, 9 auf einem Blatt Papier nach dem Auswahlverfahren.

Folge dem Arbeitsplan Sortieren mit Selection-Sort

Zusatzaufgaben:

Gib den Mittelwert der Listenelemente aus.

Wie viele Elemente sind größer bzw. kleiner als der Mittelwert?

Erstelle einen Array $numbers mit den Elementen „2“ „8“ „25“ „49“ „76“ „1231“ „4232“ „4234“ „10000“ „1238123“

Schreibe ein php-Programm, welches eine beliebig eingegebene Zahl dem Array hinzufügt und anschließend zusammen mit den anderen Arrayelementen sortiert ausgibt.

für ganz Schnelle:

Finde heraus, welche Laufzeit dein Sortier-Algorithmus für 5, 10, 20, 30, …, 200, … Elemente hat und formuliere eine Aussage über die Abhängigkeit der Laufzeit von der Anzahl der Listenelemente.

Lösungsvorschlag

<form action="sortieren.php" method="POST"> <input type="text" name="zahlen" /> <input type="submit" value="Do it!" /> </form> <?php $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"; ?>

Lektion 4