[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki11\/2020\/12\/24\/einfugesortierung-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki11\/2020\/12\/24\/einfugesortierung-wikipedia\/","headline":"Einf\u00fcgesortierung – Wikipedia","name":"Einf\u00fcgesortierung – Wikipedia","description":"before-content-x4 Sortieralgorithmus, der bei jeder Iteration das aktuelle Eingabeelement an der geeigneten Position zwischen den bereits sortierten Elementen einf\u00fcgt after-content-x4","datePublished":"2020-12-24","dateModified":"2020-12-24","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki11\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki11\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/0\/0f\/Insertion-sort-example-300px.gif","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/0\/0f\/Insertion-sort-example-300px.gif","height":"180","width":"300"},"url":"https:\/\/wiki.edu.vn\/wiki11\/2020\/12\/24\/einfugesortierung-wikipedia\/","wordCount":6017,"articleBody":" (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Sortieralgorithmus, der bei jeder Iteration das aktuelle Eingabeelement an der geeigneten Position zwischen den bereits sortierten Elementen einf\u00fcgt (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Sortieren durch Einf\u00fcgen ist ein einfacher Sortieralgorithmus, der das endg\u00fcltige sortierte Array (oder die Liste) einzeln erstellt. Bei gro\u00dfen Listen ist es viel weniger effizient als bei fortgeschritteneren Algorithmen wie Quicksort, Heapsort oder Merge-Sortierung. Die Einf\u00fcgesortierung bietet jedoch mehrere Vorteile:Einfache Implementierung: Jon Bentley zeigt eine dreizeilige C-Version und eine f\u00fcnfzeilige optimierte Version[1]Effizient f\u00fcr (recht) kleine Datens\u00e4tze, \u00e4hnlich wie bei anderen quadratischen SortieralgorithmenIn der Praxis effizienter als die meisten anderen einfachen quadratischen (dh O (n2)) Algorithmen wie Auswahlsortierung oder BlasensortierungAdaptiv, dh effizient f\u00fcr Datens\u00e4tze, die bereits im Wesentlichen sortiert sind: Die zeitliche Komplexit\u00e4t betr\u00e4gt O (kn) wenn jedes Element in der Eingabe nicht mehr als ist k Orte weg von seiner sortierten PositionStabil; dh \u00e4ndert nicht die relative Reihenfolge von Elementen mit gleichen Schl\u00fcsselnAn Ort und Stelle; dh ben\u00f6tigt nur eine konstante Menge O (1) zus\u00e4tzlichen SpeicherplatzesOnline; dh kann eine Liste so sortieren, wie sie empfangen wirdWenn Benutzer Karten manuell in einer Br\u00fcckenhand sortieren, verwenden die meisten eine Methode, die der Einf\u00fcgesortierung \u00e4hnelt.[2]Table of Contents (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Algorithmus[edit]Beste, schlechteste und durchschnittliche F\u00e4lle[edit]Beziehung zu anderen Sortieralgorithmen[edit]Varianten[edit]Listeneinf\u00fcgungssortiercode in C.[edit]Verweise[edit]Weiterf\u00fchrende Literatur[edit]Externe Links[edit]Algorithmus[edit] Ein grafisches Beispiel f\u00fcr die Einf\u00fcgesortierung. Die teilweise sortierte Liste (schwarz) enth\u00e4lt zun\u00e4chst nur das erste Element in der Liste. Bei jeder Iteration wird ein Element (rot) aus den Eingabedaten “Noch nicht auf Bestellung gepr\u00fcft” entfernt und direkt in die sortierte Liste eingef\u00fcgt.Die Einf\u00fcgesortierung wird wiederholt, wobei bei jeder Wiederholung ein Eingabeelement verbraucht wird, und es wird eine sortierte Ausgabeliste erstellt. Bei jeder Iteration entfernt die Einf\u00fcgesortierung ein Element aus den Eingabedaten, findet den Ort, zu dem es geh\u00f6rt, in der sortierten Liste und f\u00fcgt es dort ein. Es wird wiederholt, bis keine Eingabeelemente mehr vorhanden sind.Das Sortieren erfolgt normalerweise direkt, indem das Array iteriert und die sortierte Liste dahinter vergr\u00f6\u00dfert wird. An jeder Array-Position wird der Wert dort mit dem gr\u00f6\u00dften Wert in der sortierten Liste verglichen (der sich in der zuvor \u00fcberpr\u00fcften Array-Position zuf\u00e4llig daneben befindet). Wenn es gr\u00f6\u00dfer ist, bleibt das Element an Ort und Stelle und wechselt zum n\u00e4chsten. Wenn es kleiner ist, findet es die richtige Position in der sortierten Liste, verschiebt alle gr\u00f6\u00dferen Werte nach oben, um ein Leerzeichen zu erstellen, und f\u00fcgt sie an der richtigen Position ein.Das resultierende Array nach k Iterationen hat die Eigenschaft, wo die erste k + 1 Eintr\u00e4ge werden sortiert (“+1”, da der erste Eintrag \u00fcbersprungen wird). In jeder Iteration wird der erste verbleibende Eintrag der Eingabe entfernt und an der richtigen Position in das Ergebnis eingef\u00fcgt, wodurch das Ergebnis erweitert wird: (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4wirdmit jedem Element gr\u00f6\u00dfer als x nach rechts kopiert, wenn es mit verglichen wird x.Die h\u00e4ufigste Variante der Einf\u00fcgungssortierung, die mit Arrays arbeitet, kann wie folgt beschrieben werden:Angenommen, es existiert eine Funktion namens Einf\u00fcgen Entwickelt, um einen Wert in eine sortierte Sequenz am Anfang eines Arrays einzuf\u00fcgen. Es beginnt am Ende der Sequenz und verschiebt jedes Element um eine Stelle nach rechts, bis eine geeignete Position f\u00fcr das neue Element gefunden ist. Die Funktion hat den Nebeneffekt, dass der unmittelbar nach der sortierten Sequenz im Array gespeicherte Wert \u00fcberschrieben wird.Beginnen Sie am linken Element des Arrays und rufen Sie es auf, um eine Einf\u00fcgesortierung durchzuf\u00fchren Einf\u00fcgen um jedes angetroffene Element an seiner richtigen Position einzuf\u00fcgen. Die geordnete Reihenfolge, in die das Element eingef\u00fcgt wird, wird am Anfang des Arrays in dem Satz der bereits untersuchten Indizes gespeichert. Jede Einf\u00fcgung \u00fcberschreibt einen einzelnen Wert: den Wert, der eingef\u00fcgt wird.Es folgt der Pseudocode des vollst\u00e4ndigen Algorithmus, wobei die Arrays auf Null basieren:[1]i \u2190 1while i < length(A) j \u2190 i while j > 0 and A[j-1] > A[j] swap A[j] and A[j-1] j \u2190 j - 1 end while i \u2190 i + 1end whileDie \u00e4u\u00dfere Schleife l\u00e4uft \u00fcber alle Elemente mit Ausnahme des ersten, da das Pr\u00e4fix f\u00fcr einzelne Elemente A[0:1] ist trivial sortiert, also die Invariante, die die erste i Eintr\u00e4ge sind sortiert ist von Anfang an wahr. Die innere Schleife bewegt das Element A[i] an die richtige Stelle, so dass nach der Schleife die erste i+1 Elemente werden sortiert. Notiere dass der and-Der Bediener im Test muss eine Kurzschlussauswertung verwenden, andernfalls kann der Test zu einem Fehler bei den Array-Grenzen f\u00fchren, wenn j=0 und es versucht zu bewerten A[j-1] > A[j] (dh Zugriff A[-1] schl\u00e4gt fehl).Nach dem Erweitern der swap Betrieb an Ort und Stelle als x \u2190 A[j]; A[j] \u2190 A[j-1]; A[j-1] \u2190 x (wo x ist eine tempor\u00e4re Variable), kann eine etwas schnellere Version erstellt werden, die sich bewegt A[i] auf einmal in seine Position und f\u00fchrt nur eine Zuordnung im inneren Schleifenk\u00f6rper aus:[1]i \u2190 1while i < length(A) x \u2190 A[i] j \u2190 i - 1 while j >= 0 and A[j] > x A[j+1] \u2190 A[j] j \u2190 j - 1 end while A[j+1] \u2190 x[3] i \u2190 i + 1end whileDie neue innere Schleife verschiebt Elemente nach rechts, um einen Punkt f\u00fcr freizugeben x = A[i].Der Algorithmus kann auch rekursiv implementiert werden. Die Rekursion ersetzt nur die \u00e4u\u00dfere Schleife, ruft sich selbst auf und speichert sukzessive kleinere Werte von n auf dem Stapel bis n gleich 0, wobei die Funktion dann die Aufrufkette zur\u00fccksendet, um den Code nach jedem rekursiven Aufruf auszuf\u00fchren, der mit beginnt n gleich 1, mit n Erh\u00f6hen um 1, wenn jede Instanz der Funktion zur vorherigen Instanz zur\u00fcckkehrt. Der erste Anruf w\u00e4re insertionSortR (A, L\u00e4nge (A) -1).function insertionSortR(array A, int n) if n > 0 insertionSortR(A, n-1) x \u2190 A[n] j \u2190 n-1 while j >= 0 and A[j] > x A[j+1] \u2190 A[j] j \u2190 j-1 end while A[j+1] \u2190 x end ifend functionEs macht den Code nicht k\u00fcrzer, es reduziert auch nicht die Ausf\u00fchrungszeit, aber es erh\u00f6ht den zus\u00e4tzlichen Speicherverbrauch von O (1) zu AUF) (Auf der tiefsten Rekursionsebene enth\u00e4lt der Stapel N. Verweise auf die A Array, jeweils mit dem zugeh\u00f6rigen Wert der Variablen n von N. bis 1).Beste, schlechteste und durchschnittliche F\u00e4lle[edit]Die beste Eingabe ist ein Array, das bereits sortiert ist. In diesem Fall hat die Einf\u00fcgesortierung eine lineare Laufzeit (dh O (n)). W\u00e4hrend jeder Iteration wird das erste verbleibende Element der Eingabe nur mit dem am weitesten rechts stehenden Element des sortierten Unterabschnitts des Arrays verglichen.Die einfachste Eingabe im ung\u00fcnstigsten Fall ist ein Array, das in umgekehrter Reihenfolge sortiert ist. Die Menge aller Worst-Case-Eingaben besteht aus allen Arrays, bei denen jedes Element das kleinste oder zweitkleinste der vor ihm liegenden Elemente ist. In diesen F\u00e4llen scannt und verschiebt jede Iteration der inneren Schleife den gesamten sortierten Unterabschnitt des Arrays, bevor das n\u00e4chste Element eingef\u00fcgt wird. Dies gibt der Einf\u00fcgesortierung eine quadratische Laufzeit (dh O (n2)).Der Durchschnittsfall ist auch quadratisch,[4] Dies macht das Einf\u00fcgen einer Sortierung zum Sortieren gro\u00dfer Arrays unpraktisch. Die Einf\u00fcgungssortierung ist jedoch einer der schnellsten Algorithmen zum Sortieren sehr kleiner Arrays, sogar schneller als die Quicksortierung. In der Tat verwenden gute Quicksort-Implementierungen die Einf\u00fcgesortierung f\u00fcr Arrays, die kleiner als ein bestimmter Schwellenwert sind, auch wenn sie als Teilprobleme auftreten. Der genaue Schwellenwert muss experimentell bestimmt werden und h\u00e4ngt von der Maschine ab, liegt jedoch \u00fcblicherweise bei zehn.Beispiel: Die folgende Tabelle zeigt die Schritte zum Sortieren der Sequenz {3, 7, 4, 9, 5, 2, 6, 1}. In jedem Schritt wird der betrachtete Schl\u00fcssel unterstrichen. Der Schl\u00fcssel, der im vorherigen Schritt verschoben wurde (oder an Ort und Stelle belassen wurde, weil er der bisher gr\u00f6\u00dfte war), ist mit einem Sternchen markiert.3 7 4 9 5 2 6 13* 7 4 9 5 2 6 13 7* 4 9 5 2 6 13 4* 7 9 5 2 6 13 4 7 9* 5 2 6 13 4 5* 7 9 2 6 12* 3 4 5 7 9 6 12 3 4 5 6* 7 9 11* 2 3 4 5 6 7 9Beziehung zu anderen Sortieralgorithmen[edit]Die Einf\u00fcgesortierung ist der Auswahlsortierung sehr \u00e4hnlich. Wie bei der Auswahlsortierung nach k geht durch das Array, das erste k Elemente sind in sortierter Reihenfolge. Der grundlegende Unterschied zwischen den beiden Algorithmen besteht jedoch darin, dass die Einf\u00fcgesortierung vom aktuellen Schl\u00fcssel r\u00fcckw\u00e4rts scannt, w\u00e4hrend die Auswahlsortierung vorw\u00e4rts scannt. Dies f\u00fchrt zu einer Auswahlsortierung, bei der die ersten k Elemente zum k kleinste Elemente der unsortierten Eingabe, w\u00e4hrend sie beim Einf\u00fcgen einfach die ersten sind k Elemente der Eingabe.Der Hauptvorteil der Einf\u00fcgesortierung gegen\u00fcber der Auswahlsortierung besteht darin, dass die Auswahlsortierung immer alle verbleibenden Elemente scannen muss, um das absolut kleinste Element im unsortierten Teil der Liste zu finden, w\u00e4hrend die Einf\u00fcgungssortierung nur einen einzigen Vergleich erfordert, wenn die (k + 1) -st Element ist gr\u00f6\u00dfer als das k-th Element; Wenn dies h\u00e4ufig zutrifft (z. B. wenn das Eingabearray bereits sortiert oder teilweise sortiert ist), ist die Einf\u00fcgesortierung im Vergleich zur Auswahlsortierung deutlich effizienter. Im Durchschnitt (unter der Annahme des Ranges der (k + 1) -st Elementrang ist zuf\u00e4llig), Einf\u00fcgungssortierung erfordert das Vergleichen und Verschieben der H\u00e4lfte der vorherigen k Elemente, was bedeutet, dass die Einf\u00fcgesortierung im Durchschnitt etwa halb so viele Vergleiche wie die Auswahlsortierung durchf\u00fchrt.Im schlimmsten Fall f\u00fcr die Einf\u00fcgesortierung (wenn das Eingabearray umgekehrt sortiert ist) f\u00fchrt die Einf\u00fcgungssortierung genauso viele Vergleiche durch wie die Auswahlsortierung. Ein Nachteil der Einf\u00fcgesortierung gegen\u00fcber der Auswahlsortierung besteht jedoch darin, dass mehr Schreibvorg\u00e4nge erforderlich sind, da bei jeder Iteration das (k + 1) -stes Element in den sortierten Teil des Arrays erfordert viele Elementwechsel, um alle folgenden Elemente zu verschieben, w\u00e4hrend f\u00fcr jede Iteration der Auswahlsortierung nur ein einziger Austausch erforderlich ist. Im Allgemeinen schreibt die Einf\u00fcgesortierung in das Array O (n2) mal, w\u00e4hrend Auswahlsortierung nur O (n) mal. Aus diesem Grund kann eine Auswahlsortierung in F\u00e4llen vorzuziehen sein, in denen das Schreiben in den Speicher erheblich teurer ist als das Lesen, z. B. mit einem EEPROM oder einem Flash-Speicher.W\u00e4hrend einige Divide-and-Conquer-Algorithmen wie Quicksort und Mergesort die Einf\u00fcgesortierung f\u00fcr gr\u00f6\u00dfere Arrays \u00fcbertreffen, sind nicht rekursive Sortieralgorithmen wie Einf\u00fcgungssortierung oder Auswahlsortierung f\u00fcr sehr kleine Arrays im Allgemeinen schneller (die genaue Gr\u00f6\u00dfe variiert jedoch je nach Umgebung und Implementierung liegt typischerweise zwischen 7 und 50 Elementen). Daher ist eine n\u00fctzliche Optimierung bei der Implementierung dieser Algorithmen ein hybrider Ansatz, bei dem der einfachere Algorithmus verwendet wird, wenn das Array auf eine kleine Gr\u00f6\u00dfe aufgeteilt wurde.[1]Varianten[edit]D. L. Shell hat den Algorithmus erheblich verbessert; Die ge\u00e4nderte Version hei\u00dft Shell-Sortierung. Der Sortieralgorithmus vergleicht Elemente, die durch einen Abstand getrennt sind, der bei jedem Durchgang abnimmt. Die Shell-Sortierung hat die Laufzeiten in der praktischen Arbeit deutlich verbessert, wobei zwei einfache Varianten O erfordern (n3\/2) und O (n4\/3) Laufzeit.[5][6]Wenn die Kosten f\u00fcr Vergleiche die Kosten f\u00fcr Swaps \u00fcbersteigen, wie dies beispielsweise bei durch Referenz gespeicherten Zeichenfolgenschl\u00fcsseln oder bei menschlicher Interaktion der Fall ist (z. B. bei der Auswahl eines nebeneinander angezeigten Paares), verwenden Sie bin\u00e4re Einf\u00fcgungssortierung[citation needed] kann zu einer besseren Leistung f\u00fchren. Die Sortierung der bin\u00e4ren Einf\u00fcgung verwendet eine bin\u00e4re Suche, um die richtige Position zum Einf\u00fcgen neuer Elemente zu bestimmen, und f\u00fchrt daher \u2308log aus2 n\u2309 Vergleiche im schlimmsten Fall, n\u00e4mlich O (n Log n). Der Algorithmus als Ganzes hat immer noch eine Laufzeit von O (n2) im Durchschnitt aufgrund der Reihe von Swaps, die f\u00fcr jede Einf\u00fcgung erforderlich sind.Die Anzahl der Swaps kann reduziert werden, indem die Position mehrerer Elemente vor dem Verschieben berechnet wird. Wenn beispielsweise die Zielposition zweier Elemente berechnet wird, bevor sie in die richtige Position verschoben werden, kann die Anzahl der Swaps f\u00fcr zuf\u00e4llige Daten um etwa 25% reduziert werden. Im Extremfall funktioniert diese Variante \u00e4hnlich wie die Zusammenf\u00fchrungssortierung.Eine Variante namens bin\u00e4re Zusammenf\u00fchrungssortierung verwendet a bin\u00e4re Einf\u00fcgungssortierung um Gruppen von 32 Elementen zu sortieren, gefolgt von einer endg\u00fcltigen Sortierung mithilfe der Zusammenf\u00fchrungssortierung. Es kombiniert die Geschwindigkeit der Einf\u00fcgesortierung bei kleinen Datens\u00e4tzen mit der Geschwindigkeit der Zusammenf\u00fchrungssortierung bei gro\u00dfen Datens\u00e4tzen.[7]Um zu vermeiden, dass f\u00fcr jede Einf\u00fcgung eine Reihe von Swaps durchgef\u00fchrt werden muss, kann die Eingabe in einer verkn\u00fcpften Liste gespeichert werden, sodass Elemente in konstanter Zeit in die Liste oder aus der Liste heraus gesplei\u00dft werden k\u00f6nnen, wenn die Position in der Liste bekannt ist. Das Durchsuchen einer verkn\u00fcpften Liste erfordert jedoch das sequentielle Folgen der Verkn\u00fcpfungen zur gew\u00fcnschten Position: Eine verkn\u00fcpfte Liste hat keinen wahlfreien Zugriff und kann daher keine schnellere Methode wie die bin\u00e4re Suche verwenden. Daher ist die f\u00fcr die Suche erforderliche Laufzeit O (n) und die Zeit zum Sortieren ist O (n2). Wenn eine komplexere Datenstruktur (z. B. Heap oder Bin\u00e4rbaum) verwendet wird, kann die f\u00fcr das Suchen und Einf\u00fcgen erforderliche Zeit erheblich reduziert werden. Dies ist die Essenz der Heap-Sortierung und der bin\u00e4ren Baumsortierung.Im Jahr 2006 ver\u00f6ffentlichten Bender, Martin Farach-Colton und Mosteiro eine neue Variante der Insertionssorte namens Bibliothek sortieren oder Einf\u00fcgungssortierung mit L\u00fccken Dadurch bleibt eine kleine Anzahl nicht verwendeter Leerzeichen (dh “L\u00fccken”) im gesamten Array verteilt. Der Vorteil ist, dass Einf\u00fcgungen nur Elemente verschieben m\u00fcssen, bis eine L\u00fccke erreicht ist. Die Autoren zeigen, dass dieser Sortieralgorithmus mit hoher Wahrscheinlichkeit in O (n Log n) Zeit.[8]Wenn eine Sprungliste verwendet wird, wird die Einf\u00fcgezeit auf O (Protokoll) reduziert n) und Swaps werden nicht ben\u00f6tigt, da die \u00dcberspringliste in einer verkn\u00fcpften Listenstruktur implementiert ist. Die endg\u00fcltige Laufzeit f\u00fcr das Einf\u00fcgen w\u00e4re O (n Log n).Liste Einf\u00fcgesortierung ist eine Variante der Einf\u00fcgesortierung. Es reduziert die Anzahl der Bewegungen.[citation needed]Listeneinf\u00fcgungssortiercode in C.[edit]Wenn die Elemente in einer verkn\u00fcpften Liste gespeichert sind, kann die Liste mit O (1) zus\u00e4tzlichem Speicherplatz sortiert werden. Der Algorithmus beginnt mit einer anfangs leeren (und daher trivial sortierten) Liste. Die Eingabeelemente werden einzeln aus der Liste entfernt und dann an der richtigen Stelle in der sortierten Liste eingef\u00fcgt. Wenn die Eingabeliste leer ist, hat die sortierte Liste das gew\u00fcnschte Ergebnis.struct LIST * SortList1(struct LIST * pList) { \/\/ zero or one element in list if (pList == NULL || pList->pNext == NULL) return pList; \/\/ head is the first element of resulting sorted list struct LIST * head = NULL; while (pList != NULL) { struct LIST * current = pList; pList = pList->pNext; if (head == NULL || current->iValue iValue) { \/\/ insert into the head of the sorted list \/\/ or as the first element into an empty sorted list current->pNext = head; head = current; } else { \/\/ insert current element into proper position in non-empty sorted list struct LIST * p = head; while (p != NULL) { if (p->pNext == NULL || \/\/ last element of the sorted list current->iValue pNext->iValue) \/\/ middle of the list { \/\/ insert into middle of the sorted list or as the last element current->pNext = p->pNext; p->pNext = current; break; \/\/ done } p = p->pNext; } } } return head;}Der folgende Algorithmus verwendet einen nachgestellten Zeiger[9] zum Einf\u00fcgen in die sortierte Liste. Eine einfachere rekursive Methode erstellt die Liste jedes Mal neu (anstatt zu splei\u00dfen) und kann O verwenden (n) Stapelplatz.struct LIST{ struct LIST * pNext; int iValue;};struct LIST * SortList(struct LIST * pList){ \/\/ zero or one element in list if (!pList || !pList->pNext) return pList; \/* build up the sorted array from the empty list *\/ struct LIST * pSorted = NULL; \/* take items off the input list one by one until empty *\/ while (pList != NULL) { \/* remember the head *\/ struct LIST * pHead = pList; \/* trailing pointer for efficient splice *\/ struct LIST ** ppTrail = &pSorted; \/* pop head off list *\/ pList = pList->pNext; \/* splice head into sorted list at proper place *\/ while (!(*ppTrail == NULL || pHead->iValue iValue)) { \/* does head belong here? *\/ \/* no - continue down the list *\/ ppTrail = &(*ppTrail)->pNext; } pHead->pNext = *ppTrail; *ppTrail = pHead; } return pSorted;}Verweise[edit]^ ein b c d Bentley, Jon (2000), Perlen programmieren, ACM Press \/ Addison-Wesley, pp. 107-109^ Sedgewick, Robert (1983), AlgorithmenAddison-Wesley, pp. 95ff, ISBN 978-0-201-06672-2.^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990], “Abschnitt 2.1: Einf\u00fcgesortierung”, Einf\u00fchrung in Algorithmen (3. Aufl.), MIT Press und McGraw-Hill, S. 16\u201318, ISBN 0-262-03384-4. Siehe insbesondere S. 18.^ Schwarz, Keith. “Warum ist die Einf\u00fcgungssortierung \u0398 (n ^ 2) im Durchschnitt? (Antwort mit” templatetypedef “)”. Paket\u00fcberfluss.^ Frank, RM; Lazarus, RB (1960). “Ein Hochgeschwindigkeits-Sortierverfahren”. Mitteilungen der ACM. 3 (1): 20\u201322. doi:10.1145 \/ 366947.366957.^ Sedgewick, Robert (1986). “Eine neue Obergrenze f\u00fcr Shellsort”. Journal of Algorithms. 7 (2): 159\u2013173. doi:10.1016 \/ 0196-6774 (86) 90001-5.^ “Bin\u00e4re Zusammenf\u00fchrungssortierung”^ Bender, Michael A.; Farach-Colton, Mart\u00edn; Mosteiro, Miguel A. (2006), “Insertion sort is \u00d6((n Log n) “, Theorie der Computersysteme, 39 (3): 391\u2013397, arXiv:cs \/ 0407003, doi:10.1007 \/ s00224-005-1237-z, HERR 2218409^ Hill, Curt (Hrsg.), “Trailing Pointer Technique”, Euler, Valley City State Universityabgerufen 22. September 2012.Weiterf\u00fchrende Literatur[edit]Externe Links[edit] (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki11\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki11\/2020\/12\/24\/einfugesortierung-wikipedia\/#breadcrumbitem","name":"Einf\u00fcgesortierung – Wikipedia"}}]}]