In der letzten Sitzung haben wir die beiden Sortieralgorithmen InsertionSort und SelectionSort kennen gelernt.
Diese schauen wir uns heute noch einmal genauer an, diesmal mit dem Fokus auf die (manuelle) Durchführung beider Algorithmen.
Der Unterschied zwischen beiden Algorithmen besteht darin, welches Element vom unsortierten in den sortierten Bereich übertragen wird und wie es in den sortierten Bereich eingeordnet wird.
- Auswahl:
- InsertionSort wählt einfach immer das erste Element (Einfach)
- SelectionSort wählt immer das kleinste Element aus dem unsortierten Bereich aus (Komplex)
- Einordnung:
- SelectionSort fügt das zu übertragende Element immer ans Ende des sortierten Bereichs an (Einfach)
- InsertionSort sortiert das zu übertragende Element an die passende Stelle ein (Komplex)
Dieses Vorgehen schauen wir uns nun an einem Beispiel an. Beide Algorithmen sollen die Liste [ 25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ] sortieren. Der Marker ^ markiert das vom Algorithmus ausgewählte Element. Der Marker # markiert die neue Position des vom Algorithmus ausgewählten Elements.
[] [ 25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
^
[ 6 ] [ 25, 17, 32, 56, 25, 19, 8, 66, 29, 20, 29 ]
# ^
[ 6, 8 ] [ 25, 17, 32, 56, 25, 19, 66, 29, 20, 29 ]
# ^
[ 6, 8, 17 ] [ 25, 32, 56, 25, 19, 66, 29, 20, 29 ]
# ^
[ 6, 8, 17, 19 ] [ 25, 32, 56, 25, 66, 29, 20, 29 ]
#
[] [ 25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
^
[ 25 ] [ 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
# ^
[ 17, 25 ] [ 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
# ^
[ 17, 25, 32 ] [ 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
# ^
[ 17, 25, 32, 56 ] [ 25, 19, 8, 66, 29, 6, 20, 29 ]
#
a) Führe die beiden Algorithmen in den Beispielen oben bis zum Ende aus!
b) Sortiere die Liste [ 81, 98, 50, 98, 23, 30, 6, 11, 42, 32, 76, 62 ] mit SelectionSort.
c) Sortiere die Liste [ 1, 88, 61, 18, 90, 83, 89, 21, 7, 72, 64, 6 ] mit InsertionSort.
[] [ 25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
^
[ 6 ] [ 25, 17, 32, 56, 25, 19, 8, 66, 29, 20, 29 ]
# ^
[ 6, 8 ] [ 25, 17, 32, 56, 25, 19, 66, 29, 20, 29 ]
# ^
[ 6, 8, 17 ] [ 25, 32, 56, 25, 19, 66, 29, 20, 29 ]
# ^
[ 6, 8, 17, 19 ] [ 25, 32, 56, 25, 66, 29, 20, 29 ]
# ^
[ 6, 8, 17, 19, 20 ] [ 25, 32, 56, 25, 66, 29, 29 ]
# ^
[ 6, 8, 17, 19, 20, 25 ] [ 32, 56, 25, 66, 29, 29 ]
# ^
[ 6, 8, 17, 19, 20, 25, 25 ] [ 32, 56, 66, 29, 29 ]
# ^
[ 6, 8, 17, 19, 20, 25, 25, 29 ] [ 32, 56, 66, 29 ]
# ^
[ 6, 8, 17, 19, 20, 25, 25, 29, 29 ] [ 32, 56, 66 ]
# ^
[ 6, 8, 17, 19, 20, 25, 25, 29, 29, 32 ] [ 56, 66 ]
# ^
[ 6, 8, 17, 19, 20, 25, 25, 29, 29, 32, 56 ] [ 66 ]
# ^
[ 6, 8, 17, 19, 20, 25, 25, 29, 29, 32, 56, 66 ] []
#
[] [ 25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
^
[ 25 ] [ 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
# ^
[ 17, 25 ] [ 32, 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
# ^
[ 17, 25, 32 ] [ 56, 25, 19, 8, 66, 29, 6, 20, 29 ]
# ^
[ 17, 25, 32, 56 ] [ 25, 19, 8, 66, 29, 6, 20, 29 ]
# ^
[ 17, 25, 25, 32, 56 ] [ 19, 8, 66, 29, 6, 20, 29 ]
# ^
[ 17, 19, 25, 25, 32, 56 ] [ 8, 66, 29, 6, 20, 29 ]
# ^
[ 8, 17, 19, 25, 25, 32, 56 ] [ 66, 29, 6, 20, 29 ]
# ^
[ 8, 17, 19, 25, 25, 32, 56, 66 ] [ 29, 6, 20, 29 ]
# ^
[ 8, 17, 19, 25, 25, 29, 32, 56, 66 ] [ 6, 20, 29 ]
# ^
[ 6, 8, 17, 19, 25, 25, 29, 32, 56, 66 ] [ 20, 29 ]
# ^
[ 6, 8, 17, 19, 20, 25, 25, 29, 32, 56, 66 ] [ 29 ]
# ^
[ 6, 8, 17, 19, 20, 25, 25, 29, 29, 32, 56, 66 ] []
#
[] [ 81, 98, 50, 98, 23, 30, 6, 11, 42, 32, 76, 62 ]
^
[ 6 ] [ 81, 98, 50, 98, 23, 30, 11, 42, 32, 76, 62 ]
# ^
[ 6, 11 ] [ 81, 98, 50, 98, 23, 30, 42, 32, 76, 62 ]
# ^
[ 6, 11, 23 ] [ 81, 98, 50, 98, 30, 42, 32, 76, 62 ]
# ^
[ 6, 11, 23, 30 ] [ 81, 98, 50, 98, 42, 32, 76, 62 ]
# ^
[ 6, 11, 23, 30, 32 ] [ 81, 98, 50, 98, 42, 76, 62 ]
# ^
[ 6, 11, 23, 30, 32, 42 ] [ 81, 98, 50, 98, 76, 62 ]
# ^
[ 6, 11, 23, 30, 32, 42, 50 ] [ 81, 98, 98, 76, 62 ]
# ^
[ 6, 11, 23, 30, 32, 42, 50, 62 ] [ 81, 98, 98, 76 ]
# ^
[ 6, 11, 23, 30, 32, 42, 50, 62, 76 ] [ 81, 98, 98 ]
# ^
[ 6, 11, 23, 30, 32, 42, 50, 62, 78, 81 ] [ 98, 98 ]
# ^
[ 6, 11, 23, 30, 32, 42, 50, 62, 78, 81, 98 ] [ 98 ]
# ^
[ 6, 11, 23, 30, 32, 42, 50, 62, 78, 81, 98, 98 ] []
#
[] [ 1, 88, 61, 18, 90, 83, 89, 21, 7, 72, 64, 6 ]
^
[ 1 ] [ 88, 61, 18, 90, 83, 89, 21, 7, 72, 64, 6 ]
# ^
[ 1, 88 ] [ 61, 18, 90, 83, 89, 21, 7, 72, 64, 6 ]
# ^
[ 1, 61, 88 ] [ 18, 90, 83, 89, 21, 7, 72, 64, 6 ]
# ^
[ 1, 18, 61, 88 ] [ 90, 83, 89, 21, 7, 72, 64, 6 ]
# ^
[ 1, 18, 61, 88, 90 ] [ 83, 89, 21, 7, 72, 64, 6 ]
# ^
[ 1, 18, 61, 83, 88, 90 ] [ 89, 21, 7, 72, 64, 6 ]
# ^
[ 1, 18, 61, 83, 88, 89, 90 ] [ 21, 7, 72, 64, 6 ]
# ^
[ 1, 18, 21, 61, 83, 88, 89, 90 ] [ 7, 72, 64, 6 ]
# ^
[ 1, 7, 18, 21, 61, 83, 88, 89, 90 ] [ 72, 64, 6 ]
# ^
[ 1, 7, 18, 21, 61, 72, 83, 88, 89, 90 ] [ 64, 6 ]
# ^
[ 1, 7, 18, 21, 61, 64, 72, 83, 88, 89, 90 ] [ 6 ]
# ^
[ 1, 6, 7, 18, 21, 61, 64, 72, 83, 88, 89, 90 ] []
#
Uns Menschen fällt es sehr leicht, das kleinste Element auszuwählen (SelectionSort) bzw. ein beliebiges Element in eine bereits sortierte Liste einzuordnen (InsertionSort). Der Computer benötigt hierfür allerdings auch einen Algorithmus.
Natürlich sollen unsere beiden Sortieralgorithmen beides in einem (also Sortieren und das kleinste Element auswählen bzw. Sortieren und das erste Element passend einsortieren) können. Somit muss man die beiden Algorithmen jeweils ineinander verschachteln und ggf. Variablennamen anpassen.
Somit ergeben sich in beiden Fällen Sortieralgorithmen, bei denen zwei Schleifen ineinander verschachtelt sind. Es gibt allerdings einen weiteren berühmten Sortieralgorithmus, der ähnlich vorgeht: BubbleSort.
Lest den Artikel BubbleSort auf inf-schule.de. Notiert eure Antworten zu den Fragen im Artikel im Gruppendokument.
- Bearbeitet nur Aufgabe 1 aus dem Artikel! (Antworten → Gruppendokument!)
- Lest anschließend das Fachkonzept: BubbleSort und probiert den Algorithmus in Processing aus.
a) Das Beispiel unten zeigt den ersten Durchlauf von BubbleSort. Die Marker ^ und * markieren die beiden vom Algorithmus ausgewählten Elemente, wobei ^ nicht vertauscht, * aber schon. Der Marker # markiert das erste Element des bereits sortierten Bereichs. Führe den Algorithmus bis zum Ende aus!
[ 92, 95, 84, 25, 70, 45, 27 ]
^ ^
[ 92, 95, 84, 25, 70, 45, 27 ]
* *
[ 92, 84, 95, 25, 70, 45, 27 ]
* *
[ 92, 84, 25, 95, 70, 45, 27 ]
* *
[ 92, 84, 25, 70, 95, 45, 27 ]
* *
[ 92, 84, 25, 70, 45, 95, 27 ]
* *
[ 92, 84, 25, 70, 45, 27, 95 ]
#
b) Sortiere [ 78, 32, 94, 12, 32, 95, 34 ] mit BubbleSort!
[ 92, 84, 25, 70, 45, 27, 95 ]
* * #
[ 84, 92, 25, 70, 45, 27, 95 ]
* * #
[ 84, 25, 92, 70, 45, 27, 95 ]
* * #
[ 84, 25, 70, 92, 45, 27, 95 ]
* * #
[ 84, 25, 70, 45, 92, 27, 95 ]
* * #
[ 84, 25, 70, 45, 29, 92, 95 ]
#
[ 84, 25, 70, 45, 29, 92, 95 ]
* * #
[ 25, 84, 70, 45, 29, 92, 95 ]
* * #
[ 25, 70, 84, 45, 29, 92, 95 ]
* * #
[ 25, 70, 45, 84, 29, 92, 95 ]
* * #
[ 25, 70, 45, 29, 84, 92, 95 ]
#
[ 25, 70, 45, 29, 84, 92, 95 ]
^ ^ #
[ 25, 70, 45, 29, 84, 92, 95 ]
* * #
[ 25, 45, 70, 29, 84, 92, 95 ]
* * #
[ 25, 45, 29, 70, 84, 92, 95 ]
#
[ 25, 45, 29, 70, 84, 92, 95 ]
^ ^ #
[ 25, 45, 29, 70, 84, 92, 95 ]
* * #
[ 25, 29, 45, 70, 84, 92, 95 ]
#
[ 25, 29, 45, 70, 84, 92, 95 ]
^ ^ #
[ 25, 29, 45, 70, 84, 92, 95 ]
#
[ 25, 29, 45, 70, 84, 92, 95 ]
#
[ 25, 29, 45, 70, 84, 92, 95 ]
#