Beste Antwort
Zunächst sollte man sich fragen, warum ein quadratischer Sortieralgorithmus verwendet wird, wenn asymptotisch schnellere Alternativen wie Mergesort existieren oder Quicksort. Bei kleinen Arrays (weniger als 20 bis 30 Elemente) sind sowohl die Einfügesortierung als auch die Auswahlsortierung normalerweise schneller als die O (n * logn) -Alternativen. Tatsächlich wechseln viele Sortieralgorithmen, die auf dem Divide and Conquer-Paradigma basieren, zur Einfügungssortierung oder Auswahlsortierung, wenn das Array klein genug ist.
Zwischen Einfügungssortierung und Auswahlsortierung, wann welche zu verwenden?
Normalerweise führt die Einfügesortierung weniger Vergleiche durch als die Auswahlsortierung, abhängig vom Grad der „Sortierung“ des Arrays. Während die Auswahlsortierung beim Platzieren eines Elements die verbleibenden Teile des Arrays scannen muss, scannt die Einfügesortierung nur so viele Elemente wie nötig. Das heißt, wenn das Array bereits sortiert oder fast sortiert ist, wird die Einfügesortierung in O (n) -Zeit ausgeführt.
Ein Vorteil der Auswahlsortierung gegenüber der Einfügungssortierung besteht darin, dass die Anzahl der Schreibvorgänge (Swaps) erfolgt O (n), während es beim Einfügen in O (n ^ 2) ist. Dies kann wichtig sein, wenn Sie beispielsweise im Flash-Speicher sortieren, da Schreibvorgänge die Lebensdauer des Flash-Speichers verkürzen.
Antwort
In einer Auswahlsortierung für jedes Element, das angezeigt werden soll Um dem sortierten Abschnitt hinzugefügt zu werden, müssen Sie den gesamten unsortierten Teil der Liste scannen, um das minimal verbleibende Element zu finden. Bei einer Einfügesortierung müssen Sie den Abschnitt sortiert durchsuchen, um herauszufinden, wohin das nächste Element führt. Die Suche endet jedoch, sobald Sie die Einfügemarke gefunden haben (ungefähr die Hälfte) (durchschnittlich durch den sortierten Abschnitt).
Die Auswahlsortierung erfordert also durchschnittlich N / 2 Vergleiche für jedes Element, das dem sortierten Abschnitt hinzugefügt werden soll, und die Einfügungssortierung erfordert durchschnittlich N / 4 Vergleiche. Das Einfügen einer Sortierung hat jedoch eine zusätzliche Zeitstrafe beim Sortieren eines Arrays. Für jeden der N / 4-Vergleiche (im Durchschnitt) muss das Element nach oben verschoben werden, damit sowohl N / 4-Bewegungen als auch Vergleiche möglich sind. Die Auswahlsortierung erfordert nur einen einzigen Tausch.
Insgesamt gewinnt die Einfügungssortierung normalerweise das Rennen. Dies gilt insbesondere dann, wenn (für Arrays) schnelle Blockverschiebungsfunktionen vorhanden sind.