Sortieren

[e.full]

hallo haben uns mit sortieren und suchen beschäftigt, habe nun eine frage:

selection sort (also sortieren durch auswahl) ist nicht abhängig von der ausgangsreihenfolge der zu sortierenden elemnte.

aber warum ist das so?

[Klotzkopp]

selection sort (also sortieren durch auswahl) ist nicht abhängig von der ausgangsreihenfolge der zu sortierenden elemnte.

Du meinst vermutlich, dass die Laufzeitkomplexität von Selection Sort davon unabhängig ist.

aber warum ist das so?

Der Algorithmus profitiert nicht von einer Vorsortierung, weil er in jedem Schritt immer alle verbliebenen unsortierten Elemente durchsuchen muss, um das jeweils nächste kleinste zu finden. Es gibt da keine Möglichkeit, die Suche vorzeitig abzubrechen. Die Anzahl der Vergleiche, die bei Selection Sort stattfinden, ist immer gleich.

[e.full]

also ich meinte die anzahl von vergleichen beim sortieren durch auswahl

und wenn ich weiss, dass die zu sortierende liste schon fast sortiert ist, d.h. noch wenige ausnahmen,

dann würde ich mich für insertion sort, d.h. sortieren durch einfügen entscheiden, weil doch dieser sortieralgorithmus stabil ist, d.h. die reihenfolge der datensätze, der schlüssel gleich ist nicht verändert wird und der aufwand dann nicht so groß ist weil die liste schon sortiert ist.

kann man das so sagen???

[Klotzkopp]

und wenn ich weiss, dass die zu sortierende liste schon fast sortiert ist, d.h. noch wenige ausnahmen,

dann würde ich mich für insertion sort, d.h. sortieren durch einfügen entscheiden, weil doch dieser sortieralgorithmus stabil ist, d.h. die reihenfolge der datensätze, der schlüssel gleich ist nicht verändert wird und der aufwand dann nicht so groß ist weil die liste schon sortiert ist.

Die erste Begründung ist Unsinn. Wenn du einen stabilen Sortieralgorithmus brauchst, musst du einen stabilen Sortieralgorithmus verwenden, das hat nichts damit zu tun, ob die Folge vorsortiert ist.

Die zweite Begründung passt schon eher. Allerdings benutzt man in der Praxis Selection Sort und Insertion Sort nur für kleine Listen, weil sie O(n^2) haben. Bei größeren Listen benutzt man dann einen der Algorithmen mit O(n log n), wie Quicksort oder Mergesort.

[e.full]

ach so ok,

also wenn ich weiss das die liste schon fast sortiert ist, also bis auf wenige elemente, dann könnte ich theoretisch insertion sort anwenden, jetzt im allgemeinem fall.

danke

[Klotzkopp]

also wenn ich weiss das die liste schon fast sortiert ist, also bis auf wenige elemente, dann könnte ich theoretisch insertion sort anwenden, jetzt im allgemeinem fall.

Theoretisch kannst du Insertion Sort immer anwenden. Alle Sortieralgorithmen erfüllen ihren Zweck.

Wenn es um die Wahl eines bestimmten Algorithmus geht, ist eine Vorsortierung nur ein Kriterium von vielen. Wichtig ist unter Anderem auch, ob du einen stabilen Algorithmus brauchst, wie groß das zu sortierende Feld ist, wie teuer ein Vergleich in Relation zu einer Vertauschung ist usw.

[InforMatik]

Bei größeren Listen benutzt man dann einen der Algorithmen mit O(n log n), wie Quicksort oder Mergesort.

Quicksort hat allerdings ein schlechtes Worst-Case Verhalten ( O(n²) ), daher besser Mergesort oder Heapsort...