Sortieralgorithmen

Question 1

Welche Sortieralgorithmen gibt es

Answer 1

Insertion Sort, Selection Sort, Bubble Sort, Quick Sort

Question 2

Wie geht der Insertion Sort vor

Answer 2

1. Grenze wird festgelegt (links davon sortiert, rechts unsortiert)
2. erstes unsortiertes Element mit sortiertem Feld vergleichen
3. Lücke an richtiger Stelle erschaffen (durch Rechtsverschiebung der Elemente)
4. Einfügen des Elements
5. Schritte 1 bis 4 wiederholen

Question 3

Abbruchbedingung Insertion Sort

Answer 3

Grenze am Ende des Feldes

Question 4

Wo ist die Grenze beim Beginn des Insertion Sort

Answer 4

zwischen ersten und zweiten Feldelement

Question 5

Wie geht der Selection Sort vor

Answer 5

1. Grenze wird festgelegt (links davon sortiert, rechts unsortiert)
2. kleinster Wert des unsortierten Feldes wird gesucht
3. Tausch vom ersten unsortierten Element und dem kleinsten unsortierten Element
4. Schritte 1 bis 3 wiederholen

Question 6

Abbruchbedingung Selection Sort

Answer 6

Grenze zwischen letzen und vorletzen Feldelement

Question 7

Wo ist die Grenze beim Beginn des Selection Sort

Answer 7

vor dem ersten Feldelement

Question 8

Wie geht der Bubble Sort vor

Answer 8

1. erstes Paar des Feldes vergleichen
2. wenn Paar nicht sortiert, dann tauschen
3. nächstes Paar anschaue
4. Schritte 2 und 3 wiederholen
5. wenn das letzte Paar verglichen wurde und im Verlauf ein Paar getauscht wurde, dann Schritte 1 bis 4 wiederholen

Question 9

Abbruchbedingung Bubble Sort

Answer 9

Durchlauf des Feldes ohne getauschtes Paar

Question 10

Wie geht der Quick Sort vor

Answer 10

1. Pivot-Element wird festgelegt (Wert des mittleren Feldelements, nicht Index)
2. Grenzen des linken Feldes werden festgelegt
3. grenzen des rechten Feldes werden festgelegt
4. Element im linken Feld suchen, das größer als das PE ist (oder das PE selbst)
5. Element im rechten Feld suchen, das kleiner als das PE ist (oder das PE selbst)
6. wenn nicht zwei Mal das PE gefunden wurde, diese beiden Elemente tauschen
7. wenn die Teilfelder durchlaufen sind, jedes Teilfeld mit dem Algorithmus behandeln (Schritte 1 bis 6 wiederholen)

Question 11

Abbruchbedingung Quick Sort

Answer 11

Wenn jedes Teilfeld (und Teilfeld des Teilfeldes…) den Algorithmus durchlaufen hat und sortiert wurde (keine weiteren rekursive Aufrufe)

Question 12

Wo wird das Pivot-Element des Quick Sort bei Feld ohne genaue Mitte angesetzt

Answer 12

es wird die linke der “beiden Mitten” genommen (da die int-Variable der Mitte die Nachkommazahlen fallen lässt)

Question 13

Was ist das besondere am Vorgehen des Quick Sort

Answer 13

rekursive Aufrufe (Problemlösung durch Aufrufen des eigenen Algorithmus mit einem einfacheren Problem bis eine Basisfall eintrifft)