Sortierverfahren
"Wer Ordnung hält ist nur zu faul zu ...sortieren."
Autor(en): Georg Weuffen, Andreas Frommer, Katrin Schäfer, Suiunbek Ibraev - Oktober 2019
Kapitelübersicht
Hier wird das Suchproblem genau spezifiziert. Ein Rahmenprogramm in der Programmiersprache C wird angegeben.
Das Verfahren "`Sortieren durch Einfügen"' wird als Idee und als C-Programm vorgestellt.
Das Verfahren "`Sortieren durch Auswahl"' wird als Idee und als C-Programm vorgestellt.
Das Verfahren "`Bubblesort"' wird als Idee und als C-Programm vorgestellt.
Das Verfahren "`Quicksort"' wird als Idee und als C-Programm vorgestellt.
Hier können Sie vergleichend die Arbeitsweise der vorgestellten Verfahren beobachten. Sie erfahren, was sonst noch interessant sein könnte und erhalten Hinweise auf Bücher zum Thema Algorithmen und Datenstrukturen.
Arbeitsblatt
Aufgabe 1
Ermitteln Sie mit Hilfe des Simulators, wie viele Schüsselvergleiche und wie viele Umspeicherungen die verschiedenen Verfahren zum Sortieren des Datensatzes
benötigen.
Aufgabe 2
Betrachtet wird ein Datensatz der Länge 10 mit lauter verschiedenen Schlüsseln.
|
a)
|
Testen Sie, wie viele Schüsselvergleiche und wie viele Umspeicherungen die verschiedenen Verfahren durchführen, wenn die Werte anfangs aufsteigend bzw. absteigend sortiert sind.
|
|
b)
|
Vergleichen Sie die ermittelten Werte mit den Aufwandsabschätzungen.
|
Aufgabe 3
Gegeben seien Datensätze mit folgenden Schlüsseln
Welche Sortierverfahren wurden durchgeführt, wenn nach 24 Umspeicherungen die Datensätze wie folgt angeordnet sind
|
a)
|
|
|
b)
|
|
|
c)
|
Wie viele Umspeicherungen benötigt man insgesamt bei den vier Sortierverfahren, um die Schlüssel aufsteigend zu sortieren.
|
Aufgabe 4
In dem Algorithmus "Sortieren durch Einfügen" wird in die sortierte Teillösung A[0] ... A[i-1] der Datensatz A[i] an der richtigen Stelle eingefügt.
Schreiben Sie den Algorithmus so um, dass in die sortierte Teillösung A[i+1] ... A[n] der Datensatz A[i] eingefügt wird.
Aufgabe 5
In dem Algorithmus "Sortieren durch Auswahl" wird im i-ten Schritt der "i-kleinste" Datensatz an die i-te Position gebracht.
Schreiben Sie den Algorithmus so um, dass im i-ten Schritt der "i-größte" Datensatz an die (n-i)-te Position gebracht wird.
Aufgabe 6
Wie ändert sich der "Bubblesort"-Algorithmus, wenn man das Feld nicht von links nach rechts sondern von rechts nach links durchlaufen möchte.
Aufgabe 7
Im Quicksort-Algorithmus wird zu Beginn eine Vertauschung durchgeführt, falls der linke Eintrag im Feld größer ist als der rechte Eintrag.
Welche Auswirkungen hat es, wenn man diese Vertauschung nicht durchführt.
Aufgabe 8
Ändern Sie die vier Algorithmen so ab, dass die Werte nicht mehr aufsteigend sondern absteigend sortiert werden.
Drucken
Inhalt
Die Verfahren
Sortieren durch Einfügen
Sortieren durch Auswahl
Sortieren durch Bubblesort
Sortieren durch Quicksort
werden vorgestellt. Dazu gibt es jeweils praktische Übungen und Simulationen in der Programmiersprache C.
Die Aufwände für Schüsselvergleiche und Umspeicherungen werden im besten und schlechtesten Fall sowie im Mittel berechnet. Eine Animation vergleicht die einzelnen Algorithmen miteinander.
Glossar
