insertion sort c with examples
Ein detaillierter Blick auf die Einfügungssortierung mit klassischen Beispielen.
Die Einfügesortierung ist eine Sortiertechnik, die so betrachtet werden kann, dass wir Karten zur Hand spielen. Die Art und Weise, wie wir eine Karte in ein Deck einlegen oder entfernen, funktioniert ähnlich.
Die Einfügungssortierungsalgorithmus-Technik ist effizienter als die Blasensortierungs- und Auswahlsortiertechniken, jedoch weniger effizient als die anderen Techniken wie Quicksort- und Zusammenführungssortierung.
=> Lesen Sie hier die besten C ++ - Schulungsanleitungen.
Was du lernen wirst:
- Überblick
- Allgemeiner Algorithmus
- Pseudocode
- Illustration
- C ++ Beispiel
- Java-Beispiel
- Komplexitätsanalyse des Einfügungssortierungsalgorithmus
- Fazit
- Literatur-Empfehlungen
Überblick
Bei der Einfügesortiertechnik beginnen wir mit dem zweiten Element und vergleichen es mit dem ersten Element und platzieren es an einer geeigneten Stelle. Dann führen wir diesen Prozess für die nachfolgenden Elemente durch.
Wir vergleichen jedes Element mit allen vorherigen Elementen und platzieren oder fügen das Element an der richtigen Position ein. Die Einfügungssortiertechnik ist für Arrays mit einer geringeren Anzahl von Elementen praktikabler. Es ist auch nützlich, um verknüpfte Listen zu sortieren.
Verwendung von Torrent-Dateien nach dem Download
Verknüpfte Listen haben einen Zeiger auf das nächste Element (bei einer einfach verknüpften Liste) und einen Zeiger auf das vorherige Element (bei einer doppelt verknüpften Liste). Daher wird es einfacher, eine Einfügesortierung für eine verknüpfte Liste zu implementieren.
Lassen Sie uns in diesem Tutorial alles über das Sortieren von Einfügungen erfahren.
Allgemeiner Algorithmus
Schritt 1 : Wiederholen Sie die Schritte 2 bis 5 für K = 1 bis N-1
Schritt 2 : setze temp = A (K)
Schritt 3 : setze J = K - 1
Schritt 4 : Wiederholen, während temp<=A(J)
setze A (J + 1) = A (J)
setze J = J - 1
(Ende der inneren Schleife)
Schritt 5 : setze A (J + 1) = temp
(Ende der Schleife)
Schritt 6 : Ausfahrt
Daher beginnen wir bei der Einfügesortiertechnik mit dem zweiten Element, da wir davon ausgehen, dass das erste Element immer sortiert ist. Dann vergleichen wir vom zweiten bis zum letzten Element jedes Element mit allen vorherigen Elementen und bringen dieses Element an die richtige Position.
Pseudocode
Der Pseudocode für die Einfügesortierung ist unten angegeben.
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element whilefreePosition> 0 and array(freePosition -1) >insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedureOben ist der Pseudocode für die Einfügesortierung angegeben. Als nächstes werden wir diese Technik im folgenden Beispiel veranschaulichen.
Illustration
Das zu sortierende Array lautet wie folgt:
Jetzt vergleichen wir für jeden Durchgang das aktuelle Element mit allen vorherigen Elementen. Im ersten Durchgang beginnen wir also mit dem zweiten Element.
Wie spiele ich SWF-Dateien ab?
Daher benötigen wir N Durchgänge, um ein Array mit N Elementen vollständig zu sortieren.
Die obige Abbildung kann in tabellarischer Form zusammengefasst werden:
| Bestehen | Unsortierte Liste | Vergleich | Sortierte Liste |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12.3} | {3,12,5,10,8,1} |
| zwei | {3,12,5,10,8,1} | {3,12,5} | {3,5,12,10,8,1} |
| 3 | {3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| 4 | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| 5 | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| 6 | {} | {} | {1,3,5,8,10,12} |
Wie in der obigen Abbildung gezeigt, beginnen wir mit der 2ndElement, da wir davon ausgehen, dass das erste Element immer sortiert ist. Wir beginnen also mit dem Vergleich des zweiten Elements mit dem ersten und tauschen die Position aus, wenn das zweite Element kleiner als das erste ist.
Dieser Vergleichs- und Austauschprozess positioniert zwei Elemente an ihren richtigen Stellen. Als nächstes vergleichen wir das dritte Element mit seinen vorherigen (ersten und zweiten) Elementen und führen das gleiche Verfahren aus, um das dritte Element an der richtigen Stelle zu platzieren.
Auf diese Weise platzieren wir für jeden Durchgang ein Element an seiner Stelle. Für den ersten Durchgang platzieren wir das zweite Element an seiner Stelle. Um N Elemente an ihrer richtigen Stelle zu platzieren, benötigen wir im Allgemeinen N-1-Durchgänge.
Als Nächstes werden wir die Implementierung der Insertion-Sortiertechnik in C ++ demonstrieren.
C ++ Beispiel
#include using namespace std; int main () { int myarray(10) = { 12,4,3,1,15,45,33,21,10,2}; cout<<'
Input list is
'; for(int i=0;i<10;i++) { cout < Ausgabe:
Eingabeliste ist
12 4 3 1 15 45 33 21 10 2
Sortierte Liste ist
1 2 3 4 10 12 15 21 33 45
Als nächstes sehen wir die Java-Implementierung der Insertion-Sortiertechnik.
Java-Beispiel
public class Main { public static void main(String() args) { int() myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } for(int k=1; k=0 && temp <= myarray(j)) { myarray(j+1) = myarray(j); j = j-1; } myarray(j+1) = temp; } System.out.println('
sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } } } Ausgabe:
Liste der Elemente eingeben…
12 4 3 1 15 45 33 21 10 2
sortierte Liste der Elemente…
1 2 3 4 10 12 15 21 33 45
In beiden Implementierungen können wir sehen, dass wir mit dem Sortieren von 2 beginnenndElement des Arrays (Schleifenvariable j = 1) und vergleichen Sie das aktuelle Element wiederholt mit allen vorherigen Elementen und sortieren Sie das Element, um es an der richtigen Position zu platzieren, wenn das aktuelle Element nicht mit allen vorherigen Elementen in Ordnung ist.
Die Einfügesortierung funktioniert am besten und kann in weniger Durchgängen abgeschlossen werden, wenn das Array teilweise sortiert ist. Wenn die Liste jedoch größer wird, nimmt ihre Leistung ab. Ein weiterer Vorteil der Einfügesortierung besteht darin, dass es sich um eine stabile Sortierung handelt, dh, die Reihenfolge der gleichen Elemente in der Liste wird beibehalten.
Komplexitätsanalyse des Einfügungssortierungsalgorithmus
Nach dem Pseudocode und der obigen Abbildung ist die Einfügesortierung der effiziente Algorithmus im Vergleich zur Blasensortierung oder Auswahlsortierung. Anstatt for-Schleife und aktuelle Bedingungen zu verwenden, wird eine while-Schleife verwendet, die beim Sortieren des Arrays keine zusätzlichen Schritte mehr ausführt.
Selbst wenn wir das sortierte Array an die Insertion-Sortiertechnik übergeben, wird die äußere for-Schleife ausgeführt, wodurch n Schritte erforderlich sind, um ein bereits sortiertes Array zu sortieren. Dies macht die beste zeitliche Komplexität der Einfügesortierung zu einer linearen Funktion von N, wobei N die Anzahl der Elemente in dem Array ist.
VPN für kodi
Daher sind die verschiedenen Komplexitäten für die Insertion-Sortiertechnik unten angegeben:
Zeitkomplexität im schlimmsten Fall O (n 2) Best-Case-Zeitkomplexität Auf) Durchschnittliche Zeitkomplexität O (n 2) Raumkomplexität O (1)
Trotz dieser Komplexität können wir immer noch den Schluss ziehen, dass die Einfügungssortierung im Vergleich zu anderen Sortiertechniken wie Blasensortierung und Auswahlsortierung der effizienteste Algorithmus ist.
Fazit
Die Einfügungssortierung ist die effizienteste aller drei bisher diskutierten Techniken. Hier nehmen wir an, dass das erste Element sortiert ist, vergleichen dann jedes Element wiederholt mit allen vorherigen Elementen und platzieren das aktuelle Element an der richtigen Position im Array.
In diesem Tutorial haben wir bei der Erörterung der Einfügesortierung festgestellt, dass wir die Elemente mit einem Inkrement von 1 vergleichen und sie auch zusammenhängend sind. Diese Funktion erfordert mehr Durchgänge, um die sortierte Liste zu erhalten.
In unserem nächsten Tutorial werden wir uns mit der 'Shell-Sortierung' befassen, die eine Verbesserung gegenüber der Auswahlsortierung darstellt.
Bei der Shell-Sortierung führen wir eine Variable ein, die als 'Inkrement' oder 'Lücke' bezeichnet wird. Dabei teilen wir die Liste in Unterlisten mit nicht zusammenhängenden Elementen auf, die 'Lücke' voneinander haben. Die Shell-Sortierung erfordert im Vergleich zur Insertion-Sortierung weniger Durchgänge und ist außerdem schneller.
In unseren zukünftigen Tutorials lernen wir zwei Sortiertechniken kennen, 'Quicksort' und 'Mergesort', die die Strategie 'Teilen und Erobern' zum Sortieren von Datenlisten verwenden.
=> Sehen Sie sich hier den C ++ - Schulungsleitfaden für Anfänger an.
Literatur-Empfehlungen
- Shell-Sortierung in C ++ mit Beispielen
- Auswahl In C ++ mit Beispielen sortieren
- MongoDB Sort () -Methode mit Beispielen
- Unix-Sortierbefehl mit Syntax, Optionen und Beispielen
- Blasensortierung in C ++ mit Beispielen
- Heap-Sortierung in C ++ mit Beispielen
- Sortierung in C ++ mit Beispielen zusammenführen
- Schnelle Sortierung in C ++ mit Beispielen