WikiDer > Sortieren durch Einfügen

Sortieren durch Einfügen ist ein Sortieralgorithmus.

Operation

Es beginnt mit dem Sortieren der ersten beiden Elemente der Menge. Wenn diese vorhanden sind, fügen wir das dritte Element an der richtigen Stelle hinzu. Wir tun dies, bis wir alle Elemente platziert haben.

So arrangiert ein Spieler im Grunde seine Karten in a Kartenspiel. Daher ist diese Routine auch die Kartensortierung wird genannt.

Die Zeitkomplexität beträgt in den meisten Fällen O(n²) und im besten Fall, wenn die Werte schon fast sortiert sind, beträgt die Zeitkomplexität O(n).

Implementierungen

in C

Ein Beispiel in C der Einfügung sortieren.

Vorlage<Modellnamet>LeereSortieren durch Einfügen(Vektor<t>&v){zum(intich=1;ich<v.Größe();ich){// die i ersten Elemente sind bereits in OrdnungtHilfe=v[ich];// wir extrahieren das i-te Element.intja=ich-1;während(ja>=0&&Hilfe<v[ja]){// alle Elemente, die größer als das i-te Element sind, werden um 1 Stelle nach rechts verschobenv[ja1]=v[ja];ja--;}v[ja1]=Hilfe;// Wir fügen die extrahierten Daten an der richtigen Stelle ein.}}

Eine alternative Implementierung:

zum(Wagenich=Start;ich!=Ende;ich)std::drehen(std::obere Grenze(Start,ich,*ich),ich,std::Nächster(ich));

in C#

Ein Beispiel für die Einfügungssortierung in Csharp.

Sie gehen die gesamte Tabelle durch, pro zu überprüfender Zahl (1):
1) Verfolgen Sie den Inhalt dieser Nummer (1)
2) Solange links (2) neben der Zahl (1) eine Zahl steht, die sortiert werden soll, prüfen Sie, ob diese (1) kleiner ist
3) Wenn ja, verschieben Sie diese Nummer (2) an die Stelle, an der Ihre zu sortierende Nummer (1) ist
4) zurück zu Schritt 2 bis du nicht mehr kannst
5) Geben Sie dort, wo der Index endet, die Nummer ein, die derzeit sortiert wird.

ÖffentlichkeitLeereSortieren durch Einfügen(int[]Tabelle){intX;zum(intich=1;ich<Tabelle.Länge;ich  ){X=Tabelle[ich];während((ich-1>=0)&&(X<Tabelle[ich-1])){Tabelle[ich]=Tabelle[ich-1];ich--;}Tabelle[ich]=X;}}/*Sortieren durch Einfügen*/

In Python

In Python wird dies zu:

defSortieren durch Einfügen(Warteschlange):zumichimReichweite(len(Warteschlange)):#Überlauf Karte für Karte den unsortierten TeilWert=Warteschlange[ich]#Karte i in die rechte Hand nehmenzumjaimReichweite(0,ich):#Vergleiche die Karte mit den Karten im sortierten BereichwennWert<Warteschlange[ja]:#Haben Sie die Position Ihrer Karte gefunden, Wert,Warteschlange[ja]=Warteschlange[ja],Wert#Tauschen und mit neuer Karte fortfahrenWarteschlange[ich]=Wert#Karte in der rechten Hand nach dem Überfahren gehört in Position i

In JavaScript

Ein Beispiel in Javascript der Einfügung sortieren.

FunktionSortieren durch Einfügen(Warteschlange){zum(varich=1;ich<Warteschlange.Länge;ich){varHilfe=Warteschlange[ich];varja=ich-1;während(ja>=0&&Warteschlange[ja]>Hilfe){Warteschlange[ja1]=Warteschlange[ja];ja--;}Warteschlange[ja1]=Hilfe;}RückkehrWarteschlange;}