Arbeitsblatt: Sortierverfahren

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.