0 Daumen
108 Aufrufe

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.

von

Was genau heißt "fast sortiert"?

1 Antwort

0 Daumen

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

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...