webentwicklung-frage-antwort-db.com.de

Gibt es jemals einen guten Grund, Insertion Sort zu verwenden?

Für die allgemeine Sortierung lautet die Antwort anscheinend "Nein", da die Sortierung nach Schnell-, Zusammenführungs- und Heap-Sortierung im Durchschnitts- und im Worst-Case-Szenario tendenziell eine bessere Leistung erbringt. Die Einfügesortierung erscheint Excel jedoch beim inkrementellen Sortieren, dh Hinzufügen von Elementen zu einer Liste nacheinander über einen längeren Zeitraum, während die Liste sortiert bleibt. Dies gilt insbesondere dann, wenn die Einfügesortierung als verknüpfte Liste (O (log n) Durchschnittsfall vs. O (n)). Ein Heap scheint jedoch auch in der Lage zu sein, eine inkrementelle Sortierung durchzuführen (das Hinzufügen oder Entfernen eines einzelnen Elements zu einem Heap hat das Worst-Case-Szenario von O (log n)). Was genau hat Insertion Sort gegenüber anderen vergleichsbasierten Sortieralgorithmen oder Heaps zu bieten?

34
CS Student

Von http://www.sorting-algorithms.com/insertion-sort :

Obwohl es einer der elementaren Sortieralgorithmen mit O ist (n2) Worst-Case-Zeit, Einfügungssortierung ist der Algorithmus der Wahl, entweder wenn die Daten nahezu sortiert sind (weil adaptiv ist) oder wenn die Problemgröße ist klein (weil es wenig Overhead hat).

Aus diesen Gründen und weil es auch stabil ist, wird die Einfügungsart Oft als der rekursive Basisfall (Wenn die Problemgröße klein ist) für Höhere Overhead-Division verwendet -conquer Sortieralgorithmen, wie z. B. Zusammenführungssortierung oder Schnellsortierung.

49
guns

Ein wichtiges Konzept bei der Analyse von Algorithmen ist Asymptotic Analyse. Bei zwei Algorithmen mit unterschiedlichen asymptotischen Laufzeiten, wie z. B. einem O (n ^ 2) und einem O(nlogn), wie dies bei der Einfügungssortierung bzw. dem Quicksort der Fall ist, ist ist es nicht Bestimmt, dass einer schneller ist als der andere. 

Der wichtige Unterschied bei dieser Art von Analyse ist, dass für ausreichend großes N ein Algorithmus schneller als ein anderer ist. Wenn Sie einen Algorithmus bis zu einem Ausdruck wie O (nlogn) analysieren, lassen Sie Konstanten fallen. Bei der realistischen Analyse des Ablaufs eines Algorithmus sind diese Konstanten nur für Situationen mit kleinem n wichtig.

Was bedeutet das? Das bedeutet für bestimmte kleine n, dass einige Algorithmen schneller sind. Dieser article von EmbeddedGurus.net bietet eine interessante Perspektive für die Auswahl verschiedener Sortieralgorithmen bei begrenztem Speicherplatz (16k) und begrenztem Speichersystem. Natürlich bezieht sich der Artikel nur auf das Sortieren einer Liste von 20 Ganzzahlen, daher sind größere Ordnungen von n irrelevant. Kürzere Codes und weniger Speicherverbrauch (sowie das Vermeiden von Rekursion) waren letztendlich wichtigere Entscheidungen.

Die Einfügungssortierung hat einen geringen Overhead, kann ziemlich knapp geschrieben werden und hat zwei wichtige Vorteile: Sie ist stabil und hat einen ziemlich schnellen Fall, wenn die Eingabe nahezu sortiert ist.

15
Anthony

Ja, es gibt einen Grund, entweder eine Einfügungssortierung oder eine ihrer Varianten zu verwenden.

Die Sortieralternativen (schnelle Sortierung usw.) der anderen Antworten lassen hier die Annahme zu, dass sich die Daten bereits im Speicher befinden und betriebsbereit sind.

Wenn Sie jedoch versuchen, eine große Datenmenge von einer langsameren externen Quelle (z. B. einer Festplatte) einzulesen, wird viel Zeit verschwendet, da der Engpass eindeutig der Datenkanal oder das Laufwerk selbst ist. Es kann einfach nicht mit der CPU mithalten. Eine natürliche Reihe von Wartezeiten tritt bei jedem Lesevorgang auf. Diese Wartezeiten sind verschwendete CPU-Zyklen , es sei denn, Sie verwenden sie, um zu sortieren, während Sie gehen .

Wenn Sie zum Beispiel eine Lösung für dieses Problem finden sollten:

  1. Lesen Sie eine Tonne Daten in einer dedizierten Schleife in den Speicher
  2. Sortieren Sie diese Daten

Sie würden höchstwahrscheinlich länger dauern, als wenn Sie in zwei Threads Folgendes tun würden.

Faden A:

  1. Lesen Sie ein Datum
  2. Platzieren Sie das Datum in die Warteschlange FIFO
  3. (Wiederholen, bis die Daten vom Laufwerk erschöpft sind)

Faden B:

  1. Rufen Sie ein Datum aus der Warteschlange FIFO ab
  2. Füge es an der richtigen Stelle in deiner sortierten Liste ein
  3. (Wiederholen, bis die Warteschlange leer ist und Thread A "erledigt" sagt).

... können Sie die ansonsten verschwendete Zeit nutzen. Hinweis: Thread B behindert den Fortschritt von Thread A nicht.

Wenn die Daten vollständig gelesen wurden, sind sie sortiert und einsatzbereit.

8
user4229245

Bei den meisten Sortierverfahren wird für sehr kleine Datensätze Quicksort- und Einfügungssortierung verwendet.

4
BobbyShaftoe

JA,

Einfügesortierung ist besser als die Schnellsortierung in Kurzlisten.

Tatsächlich hat eine optimale Schnellsortierung einen Größenschwellenwert, bei dem sie stoppt, und dann wird das gesamte Array nach Einfügungssortierung über die Schwellenwertgrenzen sortiert.

Ebenfalls...

Für die Aufrechterhaltung einer Anzeigetafel ist die Sortierung der binären Einfügung möglicherweise so gut wie sie ist.

Siehe diese Seite .

1
JohnPaul

Wenn Sie über die Aufrechterhaltung einer sortierten Liste sprechen, haben Sie keinen Vorteil gegenüber einer Baumstruktur. Sie ist nur langsamer.

Vielleicht verbraucht es weniger Speicher oder ist eine einfachere Implementierung.

Beim Einfügen in eine sortierte Liste wird ein Scan durchgeführt. Dies bedeutet, dass jede Einfügung O (n) ist. Daher wird das Sortieren von n Elementen zu O (n ^ 2).

Das Einfügen in einen Container wie einen ausgeglichenen Baum ist normalerweise log (n). Daher ist die Sortierung O (n log (n)), was natürlich besser ist.

Aber für kleine Listen macht es kaum einen Unterschied. Sie können eine Einfügungssortierung verwenden, wenn Sie selbst ohne Bibliotheken schreiben müssen, die Listen klein sind und/oder Sie sich nicht für die Leistung interessieren.

1
MarkR

Bei kleinen Arrays führt die Sortierung schneller als das Quicksortieren. Java 7 und Java 8 verwendet einen dualen Pivot-Quicksort zum Sortieren primitiver Datentypen. Dual-Pivotsortierausgang führt den typischen Single-Pivot-Schnellwechselsatz aus. Gemäß dem Algorithmus des Dual-Pivot-Quicksort: 

  1. Verwenden Sie für kleine Arrays (Länge <27) den Einfügungssortieralgorithmus.
  2. Wählen Sie zwei Drehpunkte ...........

Das Einfügesortieren führt auf jeden Fall ein Quicksort für kleine Arrays aus. Deshalb werden Sie für Arrays mit einer Länge von weniger als 27 zur Einfügesortierung wechseln. Der Grund könnte sein, dass es keine Rekursionen in der Einfügesortierung gibt.

Quelle: http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf

0
Kangkan Lahkar