Einfügesortierung vs. Auswahlsortierung

Ich versuche die Unterschiede zwischen Einfügesortierung und Auswahlsortierung zu verstehen.

Beide scheinen zwei Komponenten zu haben: eine unsortierte Liste und eine sortierte Liste. Beide scheinen ein Element aus der unsortierten Liste zu nehmen und es an der richtigen Stelle in die sortierte Liste aufzunehmen. Ich habe einige Websites / Bücher gesehen, die besagten, dass die Auswahlsortierung dies tut, indem sie einzeln ausgetauscht wird, während die Einfügesortierung einfach die richtige Stelle findet und sie einfügt. Ich habe jedoch andere Artikel gesehen, die etwas sagten und sagten, dass die Einfügesortierung auch tauscht. Folglich bin ich verwirrt. Gibt es eine kanonische Quelle?

Auswahl Sortieren:

Nehmen Sie bei einer gegebenen Liste das aktuelle Element und tauschen Sie es mit dem kleinsten Element auf der rechten Seite des aktuellen Elements aus.

Sortieren durch Einfügen:

Nehmen Sie bei einer gegebenen Liste das aktuelle Element und fügen Sie es an der entsprechenden Position der Liste ein. Passen Sie die Liste bei jedem Einfügen an. Es ähnelt dem Anordnen der Karten in einem Kartenspiel.

Die Zeitkomplexität der Auswahlsortierung ist immer n(n - 1)/2, während die Einfügesortierung eine bessere Zeitkomplexität aufweist als die Worst-Case-Komplexität n(n - 1)/2. Im Allgemeinen sind dann weniger oder gleiche Vergleiche erforderlich n(n - 1)/2.

Quelle: http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html

Sowohl die Einfügesortierung als auch die Auswahlsortierung haben eine äußere Schleife (über jeden Index) und eine innere Schleife (über eine Teilmenge von Indizes). Jeder Durchgang der inneren Schleife erweitert den sortierten Bereich auf Kosten des unsortierten Bereichs um ein Element, bis ihm unsortierte Elemente ausgehen.

Der Unterschied besteht darin, was die innere Schleife tut:

• Bei der Auswahlsortierung befindet sich die innere Schleife über den unsortierten Elementen. Jeder Durchgang wählt ein Element aus und verschiebt es an seine endgültige Position (am aktuellen Ende des sortierten Bereichs).

• Bei der Einfügesortierung durchläuft jeder Durchgang der inneren Schleife die sortierten Elemente. Sortierte Elemente werden verschoben, bis die Schleife die richtige Stelle zum Einfügen des nächsten unsortierten Elements gefunden hat.

Bei einer Auswahlsortierung werden sortierte Elemente in der Ausgabereihenfolge gefunden und bleiben erhalten, sobald sie gefunden werden. Umgekehrt bleiben bei einer Einfügesortierung die unsortierten Elemente so lange gespeichert, bis sie in der Eingabereihenfolge verbraucht werden, während Elemente des sortierten Bereichs ständig verschoben werden.

Was das Tauschen betrifft: Die Auswahlsortierung führt einen Austausch pro Durchgang der inneren Schleife durch. Die Einfügesortierung speichert normalerweise das einzufügende Element wie temp vor der inneren Schleife, sodass die innere Schleife die sortierten Elemente um eins nach oben verschieben und anschließend tempan die Einfügemarke kopieren kann.

AUSWAHL SORTIEREN
Nehmen wir an, dass es eine Reihe von Zahlen gibt, die in einer bestimmten / zufälligen Weise geschrieben sind, und nehmen wir an, wir sollen in aufsteigender Reihenfolge anordnen. Nehmen Sie also jeweils eine Zahl und ersetzen Sie sie durch die kleinste Nr. in der Liste verfügbar. Durch diesen Schritt erhalten wir letztendlich das gewünschte Ergebnis.

INSERTION SORT Unter Berücksichtigung
der ähnlichen Annahme, aber der einzige Unterschied besteht darin, dass wir diesmal jeweils eine Zahl auswählen und in den vorsortierten Teil einfügen, was die Vergleiche reduziert und somit effizienter ist.

Möglicherweise liegt die Verwirrung darin, dass Sie eine Beschreibung zum Sortieren einer verknüpften Liste mit einer Beschreibung zum Sortieren eines Arrays vergleichen . Aber ich kann nicht sicher sein, da Sie Ihre Quellen nicht zitiert haben.

Der einfachste Weg, Sortieralgorithmen zu verstehen, besteht oft darin, eine detaillierte Beschreibung des Algorithmus zu erhalten (nicht vage Dinge wie "Diese Sortierung verwendet Swap. Irgendwo. Ich sage nicht, wo"), um ein paar Spielkarten zu bekommen (5-10 sollten ausreichen für einfache Sortieralgorithmen) und führen Sie den Algorithmus von Hand aus.

Auswahlsortierung: Durchsuchen Sie die unsortierten Daten nach dem kleinsten verbleibenden Element und tauschen Sie sie an die Position unmittelbar nach den sortierten Daten aus. Wiederholen, bis fertig. Wenn Sie eine Liste sortieren, müssen Sie das kleinste Element nicht in Position verschieben. Stattdessen können Sie den Listenknoten von seiner alten Position entfernen und an der neuen Position einfügen.

Einfügesortierung: Nehmen Sie das Element unmittelbar nach den sortierten Daten, durchsuchen Sie die sortierten Daten, um den Ort zu finden, an dem sie abgelegt werden sollen, und legen Sie es dort ab. Wiederholen, bis fertig.

Die Einfügesortierung kann während der "Scan" -Phase Swap verwenden, muss dies jedoch nicht und ist nicht die effizienteste Methode, es sei denn, Sie sortieren ein Array eines Datentyps, der: (a) nicht verschoben, nur kopiert oder ausgetauscht werden kann; und (b) ist teurer zu kopieren als zu tauschen. Wenn beim Einfügen eine Sortierung verwendet wird, suchen Sie gleichzeitig nach der Stelle und platzieren das neue Element dort, indem Sie das neue Element wiederholt mit dem Element unmittelbar davor austauschen, solange das Element davor größer als ist es. Sobald Sie ein Element erreicht haben, das nicht größer ist, haben Sie die richtige Position gefunden und fahren mit dem nächsten neuen Element fort.

Die Logik für beide Algorithmen ist ziemlich ähnlich. Beide haben am Anfang des Arrays ein teilweise sortiertes Unterarray. Der einzige Unterschied besteht darin, wie sie nach dem nächsten Element suchen, das in das sortierte Array eingefügt werden soll.

• Einfügesortierung : Fügt das nächste Element an der richtigen Position ein.

• Auswahlsortierung : Wählt das kleinste Element aus und tauscht es mit dem aktuellen Element aus.

Außerdem ist die Einfügesortierung im Gegensatz zur Auswahlsortierung stabil .

Ich habe beide in Python implementiert, und es ist erwähnenswert, wie ähnlich sie sind:

def insertion(data):
    data_size = len(data)
    current = 1
    while current < data_size:
        for i in range(current):
            if data[current] < data[i]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

Mit einer kleinen Änderung ist es möglich, den Auswahlsortierungsalgorithmus vorzunehmen.

def selection(data):
    data_size = len(data)
    current = 0
    while current < data_size:
        for i in range(current, data_size):
            if data[i] < data[current]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

Kurz gesagt, ich denke, dass die Auswahlsortierung zuerst nach dem kleinsten Wert im Array sucht und dann den Austausch durchführt, während die Einfügungssortierung einen Wert nimmt und ihn mit jedem verbleibenden Wert (dahinter) vergleicht. Wenn der Wert kleiner ist, wird er getauscht. Dann wird derselbe Wert erneut verglichen und wenn er kleiner als der dahinter liegende ist, wird er erneut getauscht. Ich hoffe das ergibt Sinn!

Zusamenfassend,

Auswahlsortierung: Wählen Sie das erste Element aus einem unsortierten Array aus und vergleichen Sie es mit den verbleibenden unsortierten Elementen. Es ähnelt der Bubble-Sortierung, hält jedoch anstelle des Austauschs jedes kleineren Elements den kleinsten Elementindex auf dem neuesten Stand und tauscht ihn am Ende jeder Schleife aus .

Einfügesortierung: Sie unterscheidet sich von der Auswahlsortierung, bei der das erste Element aus einem unsortierten Unterarray ausgewählt und mit dem sortierten Unterarray verglichen wird. Fügen Sie das kleinste gefundene Element ein und verschieben Sie alle sortierten Elemente von rechts nach dem ersten unsortierten Element.

Ich werde es noch einmal versuchen: Überlegen Sie, was im glücklichen Fall eines fast sortierten Arrays passiert.

Während des Sortierens kann das Array aus zwei Teilen bestehen: linke Seite - sortiert, rechte Seite - unsortiert.

Einfügesortierung - Wählen Sie das erste unsortierte Element aus und versuchen Sie, einen Platz dafür im bereits sortierten Teil zu finden. Da Sie von rechts nach links suchen, kann es durchaus vorkommen, dass das erste sortierte Element, mit dem Sie vergleichen (das größte, das am weitesten rechts im linken Teil), kleiner als das ausgewählte Element ist, sodass Sie sofort mit dem nächsten unsortierten Element fortfahren können.

Auswahlsortierung - Wählen Sie das erste unsortierte Element aus und versuchen Sie, das kleinste Element des gesamten unsortierten Teils zu finden. Tauschen Sie diese beiden Elemente gegebenenfalls aus. Das Problem ist, da der richtige Teil unsortiert ist, müssen Sie jedes Mal über jedes Element nachdenken, da Sie unmöglich sicher sein können, ob es noch ein kleineres Element als das ausgewählte gibt oder nicht.

Übrigens, genau das verbessert Heapsort bei der Auswahlsortierung - es kann das kleinste Element aufgrund des Heaps viel schneller finden .

Auswahlsortierung: Wenn Sie mit dem Erstellen der sortierten Unterliste beginnen, stellt der Algorithmus sicher, dass die sortierte Unterliste immer vollständig sortiert ist, nicht nur nach ihren eigenen Elementen, sondern auch nach dem gesamten Array, dh sowohl nach sortierter als auch nach unsortierter Unterliste. Somit wird das neue kleinste Element, das einmal aus der unsortierten Unterliste gefunden wurde, nur am Ende der sortierten Unterliste angehängt.

Einfügesortierung: Der Algorithmus teilt das Array erneut in zwei Teile, aber hier wird das Element aus dem zweiten Teil ausgewählt und an der richtigen Position in den ersten Teil eingefügt. Dies garantiert niemals, dass der erste Teil in Bezug auf das gesamte Array sortiert ist, obwohl sich natürlich im letzten Durchgang jedes Element an seiner richtigen sortierten Position befindet.

Beide Algorithmen funktionieren im Allgemeinen so

Schritt 1: Nehmen Sie dann das nächste unsortierte Element aus der unsortierten Liste

Schritt 2: Platzieren Sie es an der richtigen Stelle in der sortierten Liste.

Einer der Schritte ist für einen Algorithmus einfacher und umgekehrt.

Einfügesortierung : Wir nehmen das erste Element der unsortierten Liste und fügen es irgendwo in die sortierte Liste ein . Wir wissen, wohin das nächste Element gebracht werden soll (die erste Position in der unsortierten Liste), aber es erfordert einige Arbeit, um herauszufinden, wo es platziert werden soll ( irgendwo ). Schritt 1 ist einfach.

Auswahlsortierung : Wir nehmen das Element irgendwo aus der unsortierten Liste und setzen es dann an die letzte Position der sortierten Liste. Wir müssen das nächste Element finden (es befindet sich höchstwahrscheinlich nicht an der ersten Position der unsortierten Liste, sondern irgendwo ) und es dann am Ende der sortierten Liste platzieren. Schritt 2 ist einfach

Die innere Schleife der Einfügesortierung durchläuft bereits sortierte Elemente (im Gegensatz zur Auswahlsortierung). Dadurch kann die innere Schleife abgebrochen werden, wenn die richtige Position gefunden wurde . Was bedeutet, dass:

1. Die innere Schleife durchläuft im Durchschnitt nur die Hälfte ihrer Elemente.
2. Die innere Schleife wird noch früher abgebrochen, wenn das Array fast sortiert ist.
3. Die innere Schleife wird sofort abgebrochen, wenn das Array bereits sortiert ist, wodurch die Komplexität der Einfügesortierung in diesem Fall linear wird.

Die Auswahlsortierung muss immer alle inneren Schleifenelemente durchlaufen. Aus diesem Grund wird die Einfügesortierung der Auswahlsortierung am meisten vorgezogen. Andererseits führt die Auswahlsortierung viel weniger Elementwechsel durch, was in einigen Fällen wichtiger sein kann.

Grundsätzlich funktioniert die Einfügesortierung, indem zwei Elemente gleichzeitig verglichen werden und die Auswahlsortierung das minimale Element aus dem gesamten Array auswählt und sortiert.

Die konzeptionelle Einfügesortierung sortiert die Unterliste weiter, indem zwei Elemente verglichen werden, bis das gesamte Array sortiert ist, während die Auswahlsortierung das minimale Element auswählt und es an die erste Position, das zweite minimale Element an die zweite Position usw. tauscht.

Die Einfügesortierung kann wie folgt angezeigt werden:

    for(i=1;i<n;i++)
        for(j=i;j>0;j--)
            if(arr[j]<arr[j-1])
                temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;

Die Auswahlsortierung kann wie folgt angezeigt werden:

    for(i=0;i<n;i++)
        min=i;
        for(j=i+1;j<n;j++)
        if(arr[j]<arr[min])
        min=j;
        temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;

Die Wahl dieser beiden Sortieralgorithmen hängt von der verwendeten Datenstruktur ab.

Wenn Sie Arrays verwenden, verwenden Sie die Auswahlsortierung (obwohl warum, wenn Sie qsort verwenden können?). Wenn Sie verknüpfte Listen verwenden, verwenden Sie die Einfügesortierung.

Das ist weil:

• Das Durchlaufen verknüpfter Listen ist teurer als Arrays.
• Das Einfügen verknüpfter Listen ist weitaus billiger als das Einfügen von Arrays.

Durch die Einfügesortierung wird der neue Wert in die Mitte des sortierten Segments eingefügt. Daher müssen Daten "zurückgeschoben" werden. Wenn Sie jedoch eine verknüpfte Liste verwenden, haben Sie durch Drehen von 2 Zeigern die gesamte Liste effektiv zurückgeschoben. In einem Array müssen Sie n-i-Swaps durchführen, um die Werte zurückzuschieben, was sehr teuer sein kann.

Die Auswahlsortierung wird immer an das Ende angehängt, sodass dieses Problem bei der Verwendung von Arrays nicht auftritt. Daher müssen Daten nicht "zurückgeschoben" werden.

Eine einfache Erklärung könnte wie folgt sein:

Gegeben : Ein unsortiertes Array oder eine Liste von Zahlen.

Problemstellung : Sortieren der Liste / des Arrays von Zahlen in aufsteigender Reihenfolge, um den Unterschied zwischen Auswahlsortierung und Einfügesortierung zu verstehen.

Sortieren durch Einfügen:Sie sehen die Liste zum besseren Verständnis von oben nach unten. Wir betrachten das erste Element als unseren anfänglichen Mindestwert. Die Idee ist nun, dass wir jeden Index dieser Liste / dieses Arrays linear durchlaufen, um herauszufinden, ob sich an einem Index ein anderes Element befindet, das einen geringeren Wert als den anfänglichen Mindestwert hat. Wenn wir einen solchen Wert finden, tauschen wir einfach die Werte an ihren Indizes aus, dh sagen wir, 15 war der minimale Anfangswert bei Index 1, und während des linearen Durchlaufs der Indizes stoßen wir auf eine Zahl mit geringerem Wert, beispielsweise 7 bei Index 9 Dieser Wert 7 am Index 9 wird nun gegen den Index 1 mit 15 als Wert ausgetauscht. Diese Durchquerung wird weiterhin mit dem Wert des aktuellen Index mit den verbleibenden Indizes verglichen, um sie gegen den kleineren Wert auszutauschen. Dies wird bis zum vorletzten Index der Liste / des Arrays fortgesetzt.

Auswahl Sortieren:Nehmen wir an, dass das erste Indexelement der Liste / des Arrays sortiert ist. Ausgehend vom Element am zweiten Index vergleichen wir es mit dem vorherigen Index, um festzustellen, ob der Wert kleiner ist. Die Durchquerung konnte in zwei Teile unterteilt werden, sortiert und unsortiert. Eine wäre die Visualisierung einer Vergleichsprüfung von unsortiert zu sortiert für einen bestimmten Index in der Liste / im Array. Angenommen, Sie haben den Wert 19 bei Index 1 und den Wert 10 bei Index 3. Wir betrachten die Durchquerung von unsortiert nach sortiert, dh von rechts nach links. Nehmen wir also an, wir müssen nach Index 3 sortieren. Wir sehen, dass er im Vergleich von rechts nach links einen geringeren Wert als Index 1 hat. Einmal identifiziert, platzieren wir diese Nummer 10 von Index 3 einfach an die Stelle von Index 1 mit dem Wert 19. Der ursprüngliche Wert 19 bei Index 1 wird um eine Stelle nach rechts verschoben.

Ich habe keinen Code hinzugefügt, da die Frage nach dem Verständnis des Konzepts der Durchquerungsmethode zu sein scheint.

Einfügesortierung tauschen keine Dinge aus. Obwohl eine temporäre Variable verwendet wird, ist der Punkt, an dem temp var verwendet wird, wenn wir festgestellt haben, dass ein Wert an einem Index im Vergleich zum Wert des vorherigen Index geringer ist, den größeren Wert an die Stelle kleinerer Werte verschoben wird Index, der Dinge überschreiben würde. Dann verwenden wir die temporäre Variable, die am vorherigen Index ersetzt werden soll. Beispiel: 10, 20, 30, 50, 40. Iteration 1: 10, 20, 30, 50, 50. [Temp = 40] Iteration 2: 10,20, 30, 40 (Temp-Wert), 50. Also, wir Fügen Sie einfach einen Wert an der gewünschten Position aus einer Variablen ein.

Wenn wir jedoch die Auswahlsortierung in Betracht ziehen, finden wir zuerst den Index mit dem niedrigeren Wert und tauschen diesen Wert mit dem Wert aus dem ersten Index aus und tauschen ihn wiederholt aus, bis alle Indizes sortiert sind. Dies ist genau das gleiche wie beim herkömmlichen Tauschen von zwei Zahlen. Beispiel: 30, 20, 10, 40, 50. Iteration 1: 10, 20, 30, 40, 50. Hier wird temp var ausschließlich zum Tauschen verwendet.

Durch das Einfügen wird diese Auswahl viel mehr ausgetauscht. Hier ist ein Beispiel:

Gemeinsam ist beiden, dass beide eine Partition verwenden, um zwischen dem sortierten und dem unsortierten Teil des Arrays zu unterscheiden.

Der Unterschied besteht darin, dass bei der Auswahlsortierung garantiert wird, dass sich der sortierte Teil des Arrays beim Hinzufügen von Elementen zur sortierten Partition nicht ändert.

Der Grund dafür ist, dass die Auswahl nach dem Minimum der unsortierten Menge sucht und es direkt nach dem letzten Element der sortierten Menge hinzufügt, wodurch die sortierte Menge um 1 erhöht wird.

Das Einfügen hingegen kümmert sich nur um das nächste Element, das angetroffen wird, nämlich das erste Element im unsortierten Teil des Arrays. Es nimmt dieses Element und passt es einfach an die richtige Stelle im sortierten Satz.

Die Einfügesortierung ist normalerweise immer ein besserer Kandidat für Arrays, die nur teilweise sortiert sind, da Sie Operationen verschwenden, um das Minimum zu finden.

Fazit:

Die Auswahlsortierung fügt dem Ende schrittweise ein Element hinzu, indem das minimale Element im unsortierten Abschnitt gefunden wird.

Durch die Einfügesortierung wird das erste im unsortierten Abschnitt gefundene Element an eine beliebige Stelle im sortierten Abschnitt weitergegeben.

Obwohl die zeitliche Komplexität der Auswahlsortierung und der Einfügungssortierung gleich ist, ist dies n (n - 1) / 2. Die durchschnittliche Sortierung der Leistungseinfügungen ist besser. Getestet auf meiner i5-CPU mit zufälligen 30000 Ganzzahlen dauerte die Auswahlsortierung durchschnittlich 1,5 Sekunden, während die Einfügesortierung durchschnittlich 0,6 Sekunden dauerte.

In Laienbegriffen (und wahrscheinlich der einfachste Weg, um ein umfassendes Verständnis des Problems zu erreichen)

Die Blasensortierung ähnelt dem Stehen in einer Reihe und dem Versuch, sich nach Größe zu sortieren. Sie wechseln so lange mit der Person neben Ihnen, bis Sie am richtigen Ort sind. Dies erfolgt ganz von links (oder von rechts, je nach Implementierung) und Sie wechseln weiter, bis alle sortiert sind.

Bei der Auswahlsortierung ähnelt das, was Sie tun, dem Anordnen einer Kartenhand. Sie sehen sich die Karten an, nehmen die kleinste, legen sie ganz nach links und so weiter.

Auswahl - Wählen Sie ein bestimmtes Element (das niedrigste) aus und tauschen Sie es mit dem i-ten Element (Anzahl der Iterationen) aus. (dh erste, zweite, dritte .......), wodurch die sortierte Liste auf einer Seite erstellt wird.

Einfügung - Vergleich von erstem mit zweitem Vergleich von drittem mit zweitem und erstem Vergleich von viertem mit drittem, zweitem und erstem ......

Ein Link, über den alle Sortierungen verglichen werden