Gibt es jemals einen guten Grund, die Einfügesortierung zu verwenden?

Für die allgemeine Sortierung scheint die Antwort nein zu sein, da schnelle Sortierung, Mischsortierung und Haldensortierung in Durchschnitts- und Worst-Case-Szenarien tendenziell besser abschneiden. Die Sortierung nach Einfügung scheint jedoch bei der inkrementellen Sortierung überragend zu sein, dh das Hinzufügen von Elementen zu einer Liste über einen längeren Zeitraum, während die Liste sortiert bleibt, insbesondere wenn die Einfügesortierung als verkettete Liste (O (log n) durchschnittlicher Fall gegen O (n)). Ein Heap scheint jedoch in der Lage zu sein, genau (oder fast) genauso gut für inkrementelles Sortieren zu arbeiten (das Hinzufügen oder Entfernen eines einzelnen Elements von einem Heap hat ein Worst-Case-Szenario von O (log n)). Was also genau hat Insertion Sort gegenüber anderen vergleichsorientierten Sortieralgorithmen oder Heaps zu bieten?

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

Obwohl es einer der elementaren Sortieralgorithmen mit O (n 2 ) worst-case-Zeit ist, ist Insertion sort der Algorithmus der Wahl, entweder wenn die Daten nahezu sortiert sind (weil sie adaptiv sind) oder wenn die Problemgröße klein ist hat einen geringen Overhead).

Aus diesen Gründen und weil es auch stabil ist, wird die Einfügesortierung oft als rekursiver Basisfall (wenn die Problemgröße klein ist) für höhere Overhead-Divide-and-Conquer-Sortieralgorithmen, wie Mischsortierung oder Schnellsortierung, verwendet.

Ein wichtiges Konzept bei der Analyse von Algorithmen ist die asymptotische Analyse. Im Fall von zwei Algorithmen mit unterschiedlichen asymptotischen Laufzeiten, wie etwa einem O (n ^ 2) und einem O (nlogn), wie es bei Insertions-Sortierung bzw. Quicksort der Fall ist, ist es nicht sicher, dass einer schneller ist als der andere.

Der wichtige Unterschied bei dieser Art von Analyse besteht darin, dass für ausreichend große N ein Algorithmus schneller ist als ein anderer. Wenn Sie einen Algorithmus bis zu einem Term wie O (nlogn) analysieren, löschen Sie Konstanten. Wenn der Lauf eines Algorithmus realistisch analysiert wird, 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 Artikel von EmbeddedGurus.net enthält eine interessante Perspektive zur Auswahl verschiedener Sortieralgorithmen im Falle eines begrenzten Speicherplatzes (16k) und eines begrenzten Speichersystems. Natürlich verweist der Artikel nur auf das Sortieren einer Liste von 20 ganzen Zahlen, so dass größere Mengen von n irrelevant sind. Kürzere Code und weniger Speicherverbrauch (sowie die Vermeidung von Rekursion) waren letztlich wichtigere Entscheidungen.

Die Einfügesortierung hat einen geringen Overhead, sie kann ziemlich knapp geschrieben werden und hat zwei wesentliche Vorteile: Sie ist stabil und hat eine ziemlich schnelle Ausführung, wenn die Eingabe fast sortiert ist.

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

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

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 während eines Lesevorgangs auf. Diese Wartezeiten sind verschwendete CPU-Zyklen, es sei denn, Sie verwenden sie zum Sortieren, während Sie fortfahren .

Zum Beispiel, wenn du deine Lösung dafür machen solltest, wäre folgendes:

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

Sie würden sehr wahrscheinlich länger dauern als wenn Sie das Folgende in zwei Threads gemacht hätten.

Faden A:

  1. Lese ein Datum
  2. Platziere das Datum in die FIFO-Warteschlange
  3. (Wiederholen, bis die Daten vom Laufwerk erschöpft sind)

Faden B:

  1. Holen Sie sich ein Datum aus der FIFO-Warteschlange
  2. Fügen Sie es an der richtigen Stelle in Ihre sortierte Liste ein
  3. (wiederhole, bis die Warteschlange leer ist und Thread A sagt “fertig”).

… die oben genannten können Sie die sonst verschwendete Zeit nutzen. Hinweis: Thread B behindert den Fortschritt von Thread A nicht.

Zu dem Zeitpunkt, zu dem die Daten vollständig gelesen wurden, ist sie sortiert und einsatzbereit.

Die meisten Sortiervorgänge verwenden Quicksort und dann die Sortierung für sehr kleine Datensätze.

Wenn Sie davon sprechen, eine sortierte Liste zu führen, gibt es keinen Vorteil gegenüber einer Art von Baum, es ist nur langsamer.

Nun, vielleicht verbraucht es weniger Speicher oder ist eine einfachere Implementierung.

Das Einfügen in eine sortierte Liste beinhaltet einen Scan, was 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, beispielsweise einen ausgeglichenen Baum, ist typischerweise 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 Insert-Sortierung verwenden, wenn Sie sie selbst ohne Bibliotheken schreiben müssen, die Listen sind klein und / oder Sie kümmern sich nicht um die performance.

JA,

Die Einfügesortierung ist besser als die Schnellsortierung in kurzen Listen.

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

Ebenfalls…

Zum Verwalten einer Anzeigetafel kann die binäre Einfügesortierung so gut sein wie möglich.

Siehe diese Seite .

Bei kleinen Arrays führt die Sortierung schneller aus als Quicksort. Java 7 und Java 8 verwenden Dual-Pivot-Quicksort zum Sortieren primitiver Datentypen. Dual Pivot Quicksort Out führt typische Single Pivot Quicksort aus. Nach dem Algorithmus des Dual-Pivot-Quicksort:

  1. Verwenden Sie für kleine Arrays (Länge <27) den Sortieralgorithmus Einfügung.
  2. Wähle zwei Drehpunkte ………..

Determinelyly insert sort out führt Quicksort für kleine Arrays aus, und deshalb wechseln Sie zur Insertion sort für Arrays mit einer Länge von weniger als 27 . 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