Sortierverfahren - Aufgaben

Aufgabe 1:
Führen Sie das Sortieren durch Einfügen (Insertion Sort) mit Hilfe Ihrer Sortierkarten „von Hand“ durch.

Aufgabe 2:
Beschreiben Sie, wie der Pseudocode zum Sortieren durch Einfügen verändert werden muss, damit die Sortierung in absteigender Reihenfolge erfolgt.

Aufgabe 3:
Begründen Sie, dass das Sortieren durch Einfügen im besten Fall eine lineare Laufzeit, also eine Laufzeit proportional zu n, hat.

Aufgabe 4:
Führen Sie das Sortieren durch Auswählen (Selection Sort) mit Hilfe Ihrer Sortierkarten „von Hand“ durch.

Aufgabe 5:
Begründen Sie, dass auch das Sortieren durch Auswählen in jedem Fall eine quadratische Laufzeit, also eine Laufzeit proportional zu n², besitzt.

Aufgabe 6:
Das nachfolgende Video zeigt ein weiteres, einfaches Sortierverfahren - den sogenannten Bubblesort-Algorithmus.



Entwickeln Sie für dieses Verfahren einen Pseudocode für das Sortieren eines Arrays mit n Elementen. Orientieren Sie sich bei der Syntax am Beispiel zum Sortieren durch Einfügen.
Lassen Sie Ihren Algorithmus anschließend von einem Mitschüler ausführen und überprüfen Sie ihn gemeinsam auf seine Korrektheit.

Aufgabe 7:
Es kann vorkommen, dass sich einige Elemente bzgl. des gewählten Sortierkriteriums nicht unterscheiden (z.B. zwei Songs des gleichen Interpreten). Untersuchen Sie, wie sich die beiden Sortierverfahren in dieser Situation verhalten. Recherchieren Sie in diesem Zusammenhang auch, was man unter einem "stabilen Sortierverfahren" versteht und ordnen Sie die Verfahren entsprechend ein.

Aufgabe 8:

Die folgenden Münzen sollen nach Größe der Münzdurchmessers sortiert werden: Es werden die Sortierverfahren SelectionSort, InsertionSort oder BubbleSort auf die Ausgangsfolge angewandt und die Münzen nach einem Zwischenschritt des Sortiervorganges fotografiert. Ordnen Sie die Sortierverfahren jedem Münzenbild zu und begründen Sie Ihre Entscheidung. Sortiere Alltagsgestände (Stifte, Karten etc.) nach einem der drei Sortierverfahren und gehe entsprechend vor. Fotografiere mit deinem Smartphone die Ausgangssituation und einen Zwischenschritt und zeige diese deinem Partner. Der soll raten und begründen, welcher Sortieralgorithmus hier angewandt worden ist.