Effizienz von Sortieralgorithmen in Arrays?
Hallo! Ich schreibe morgen eine Informatik Klausur über Sortieralgorithmen. Meine Frage ist erstmal was versteht man genau unter Effizienz und wann die folgenden Algorithmen besonders effizient bzw. ineffizient arbeiten: BubbleSort, InsertionSort, SelectionSort, MergeSort und QuickSort. Danke im voraus
1 Antwort
Schauen wir uns den Code an:
InsertionSort:
Der InsertionSort funktioniert, indem er eine bereits vorsortierte Liste speichert und dann für alle weiteren Elemente prüft, wohin sie müssen. Nehmen wir die Zahlenreihe 2, 3, 1, 5, 4. Der InsertionSort nimmt das erste Element und macht daraus eine Liste, eine Liste der Länge eins mit dem Wert 2. Danach prüft er das nächste Element. Ist es grösser als das grösste Listenelement, wird es hinten an die Liste angestellt. Die Liste ist dann 2, 3. Ist es kleiner, was beim nächsten Element 1 der Fall sein wird, wird geprüft, wo das Element in die Liste muss. Die 1 muss vor die 3, die 1 muss vor die 2, dann besteht die Teilliste 1,2,3 und mit 5 und 4 wird abschliessend so verfahren.
Der Code dazu:
class InsertionSort {
int[] doSorting(int[] array) {
for(int i = 1; i < array.length; i++) {
int k = array[i];
int j = i - 1;
while(j >= 0 && array[j] > k) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = k;
}
return array;
}
}
Was man sieht, ist dass der Insertion sort im zwei Position gespeichert hat, die momentan zu verarbeitende und die davor. Gleichzeitig ist der InsertionSort in der komfortablen Lage, dass er keine Sortierung vornehmen muss, wenn ein Element grösser ist als die Teilliste. Hast du 1,2,3 muss er die 5 nicht sortieren, er kann sie einfach hinten dranknallen. Der InsertionSort eignet sich deswegen besonders gut, wenn ein Array weitestgehend sortiert ist. Bei 1,2,4,5,6,7,8,3,9 muss beispielsweise nur die 3 manuell sortiert werden.
BubbleSort:
Der BubbleSort geht mehrfach durch die Liste und prüft dabei immer je zwei Elemente nebeneinander. Ist das hintere Element kleiner als das vordere, werden die Elemente vertauscht. Wir nehmen wieder das Array 2, 3, 1, 5, 4. Der BubbleSort prüft 2 und 3 - müssen nicht vertauscht werden. BubbleSort prüft 3 und 1, müssen vertauscht werden usw. Ist er einmal durch die Liste durch, beginnt er von vorne, allerdings kann er jeweils ein Element weniger durchgehen pro Durchlauf, denn durch diese Weise wird das grösste Element garantiert hinten angehängt. Du kannst es durchspielen mit dem obigen Array. Nach dem ersten Durchlauf ist die 5 garantiert zuhinterst. Nach dem zweiten Durchlauf sind 4, 5 gegeben usw.
Code:
class BubbleSort {
int[] doSorting(int[] array) {
for (int i = 1; i < array.length; i++) {
for(int j = 0; j < array.length - i; j++) {
if(array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
}
Genau wie der InsertionSort profitiert auch der BubbleSort von einer Vorsortierung. Diese muss allerdings anders aussehen. Vom Array 1,2,4,5,6,7,8,3,9 profitiert der BubbleSort nicht, es dauerst ewig, bis die drei an ihrem Platz ist. Er profitiert aber beispielsweise vom Array 2,1,4,3,6,5,7,8,9, wenn er hier einmal durchgeht und 2,1, 4,3 und 6,5 vertauscht, ist er durch.
QuickSort:
Der QuickSort funktioniert so, dass im Array ein Element als Teiler (Pivot) ausgesucht wird. Anhand dessen wird das Array dann geteilt, alles was kleiner oder gleich ist, kommt in das erste Unter-Array, alles, was grösser ist, kommt in das zweite Unter-Array. So verfährt man dann auch wiederum weiter, auch die Unter-Arrays werden wiederum durch einen Pivoten getrennt. Als Pivot kommen drei Werte in Betracht, der jeweils erste Eintrag des Arrays, der letzte Eintrag oder der Eintrag genau in der Mitte.
Nimmt man beispielsweise den ersten Eintrag, würde das Array 2, 3, 1, 5, 4 beispielsweise in 1 und 3, 5, 4 gespalten und das solange, bis eine weitere Aufspaltung nicht möglich ist (hier ein Bild, das nimmt jedoch den letzen Eintrag, nicht den ersten: https://www.geeksforgeeks.org/wp-content/uploads/gq/2014/01/QuickSort2.png
Mein Code nimmt den ersten Eintrag:
class QuickSort {
int[] doSorting(int[] array, int start, int end){
int partition = doPartitioning(array, start, end);
if(partition - 1 > start) {
doSorting(array, start, partition - 1);
}
if(partition + 1 < end) {
doSorting(array, partition + 1, end);
}
return array;
}
private int doPartitioning(int [] array, int start, int end) {
int p = array[start];
for (int i = end; i > start; i--) {
if (array[i] > p) {
int temp = array[end];
array[end] = array[i];
array[i] = temp;
end--;
}
}
int temp = array[end];
array[end] = p;
array[start] = temp;
return end;
}
}
Der QuickSort ist, wie der Name schon sagt, sehr schnell. Allerdings nur dort, wo keine Vorsortierung besteht. Im Gegensatz zum InsertionSort und zum BubbleSort kann der QuickSort eine Vorsortierung nicht erkennen, er muss so oder so die voll Aufspaltung machen. Dort, wo also überhaupt keine Struktur im unsortierten Array erkennbar ist, ergibt sich der QuickSort als Lösung. Er hat den zusätzlichen Vorteil, dass er keinen zusätzlichen Speicher braucht, da die Auftrennung in die Unter-Arrays ausgehend vom Hauptarray errechnet werden kann.
SelectionSort:
Der SelectionSort arbeitet sehr simpel. Aus dem Start-Array hinaus sucht er den kleinsten Wert und wirft ihn an den Anfang (Position 0). Aus 2,3,1,5,4 wird 1,2,3,5,4 usw.
Code:
class SelectionSort {
int[] doSorting(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int m = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[m])
m = j;
}
int temp = array[m];
array[m] = array[i];
array[i] = temp;
}
return array;
}
}
Der SelectionSort braucht keinen zusätzlichen Speicherplatz, genauso wenig wie der QuickSort. Der Vorteil am SelectionSort ist, dass er nie mehr Operationen machen muss als Array.length - 1. Denn wenn er bei jedem Durchlauf das kleinste Element ganz vorne hinlegt, sind am Ende alle Elemente der Reihe nach vorne und das grösste Element ist automatisch hinten (deswegen minus 1). Beim Array 5,4,3,2,1 würde daraus 1,5,4,3,2 => 1,2,5,4,3 => 1,2,3,5,4 => 1,2,3,4,5. Das ist vorteilhaft, wenn die Speicherbeschreibung eine kostenpflichtige Angelegenheit ist.
MergeSort:
Beim MergeSort wird das Array in Hälften aufgeteilt und am Ende wieder zusammengesetzt (Bild: https://www.geeksforgeeks.org/wp-content/uploads/Merge-Sort-Tutorial.png). Leider habe ich keinen Code hierzu. Der MergeSort braucht zusätzlichen Speicherplatz und ist deswegen bei Array schlechter geeignet als der QuickSort oder der SelectionSort. Vorteile bietet der MergeSort vor allem bei verlinkten Listen, da die referenzielle Verbindung durch die Spaltung keine speicheraufwändigen Änderungen durchlaufen muss.
Gut zusammengefasst, man sollte aber beachten, dass im Worst Case Mergesort von den angegebenen Algorithmen am effizientesten arbeitet. Danach Quicksort, und anschließend folgen mit weitem Abstand die restlichen Algorithmen.
Bei deiner Zusammenfassung ergibt sich da implizit ein anderer Eindruck