Selection Sort vs. Quick Sort

Question

Ich soll in meinem Java Code eine Eingabe sortieren, die bereits fast sortiert ist. Würde sich dafür eher Selection Sort, oder eher Quick Sort eignen? Welche Vor- und Nachteile hätten die beiden verschiedenen Sortierverfahren da?

Ich kenne den Unterschied, wüsste aber nicht in welchen Situationen ich welches Sortierverfahren wählen sollte.

Comments

Was genau heißt "fast sortiert"?

Answer 1

Hallo!

Folgende Seite lege ich dir ans Herz, wenn du dich mit der Komplexität der Laufzeit von Sortieralgorithmen beschäftigen willst:

http://bigocheatsheet.com/

Selectionsort hat immer O(n^2), während Quicksort O(n log(n)) im besten Falle hat. Bei sehr kleinen Datenmengen (<1000) ist es fast egal, welchen Algorithmus du verwendest. Bei großen Datenmengen (>10000) ist der Unterschied merklich. Ich kann dir gerne ein Programm bereitstellen, das einige Sortierverfahren mit vergangener Zeit beherrscht und ausgibt. Da kann man mit den Werten etwas rumspielen.

Fazit: wenn es ein kleines Array ist, reicht Selectionsort, vor allem, wenn du den Code erst implementieren musst. In allen anderen Fällen rate ich zu Quick- oder Radixsort.

Beste Grüße

Felix