Datenstruktur und Algorithmen Einfügungssortierung

Dies ist ein Vergleichs-basierter Sortieralgorithmus. Hier wird eine Unterliste gepflegt, die immer sortiert ist. Beispielsweise wird der untere Teil eines Arrays zum Sortieren beibehalten. Ein Element, das in diese sortierte Unterliste 'eingefügt' werden soll, muss seinen geeigneten Platz finden und dann dort eingefügt werden. Daher der Name,insertion sort.

Das Array wird nacheinander durchsucht und unsortierte Elemente werden verschoben und in die sortierte Unterliste (im selben Array) eingefügt. Dieser Algorithmus ist nicht für große Datenmengen geeignet, da seine durchschnittliche und Worst-Case-Komplexität Ο (n ² ) beträgt , wobein ist die Anzahl der Elemente.

Wie funktioniert die Einfügungssortierung?

Wir nehmen ein unsortiertes Array für unser Beispiel.

Die Einfügesortierung vergleicht die ersten beiden Elemente.

Es zeigt sich, dass sowohl 14 als auch 33 bereits in aufsteigender Reihenfolge sind. Derzeit befindet sich 14 in einer sortierten Unterliste.

Die Einfügesortierung wird fortgesetzt und vergleicht 33 mit 27.

Und stellt fest, dass 33 nicht in der richtigen Position ist.

Es tauscht 33 gegen 27. Es prüft auch alle Elemente der sortierten Unterliste. Hier sehen wir, dass die sortierte Unterliste nur ein Element 14 hat und 27 größer als 14 ist. Daher bleibt die sortierte Unterliste nach dem Austausch sortiert.

Inzwischen haben wir 14 und 27 in der sortierten Unterliste. Als nächstes vergleicht es 33 mit 10.

Diese Werte sind nicht in einer sortierten Reihenfolge.

Also tauschen wir sie aus.

Durch das Austauschen werden jedoch 27 und 10 unsortiert.

Daher tauschen wir sie auch aus.

Wieder finden wir 14 und 10 in einer unsortierten Reihenfolge.

Wir tauschen sie wieder. Am Ende der dritten Iteration haben wir eine sortierte Unterliste von 4 Elementen.

Dieser Vorgang wird fortgesetzt, bis alle unsortierten Werte in einer sortierten Unterliste behandelt sind. Nun werden wir einige Programmieraspekte der Einfügesortierung sehen.

Algorithmus

Jetzt haben wir ein umfassenderes Bild davon, wie diese Sortiertechnik funktioniert, sodass wir einfache Schritte ableiten können, mit denen wir eine Einfügesortierung erreichen können.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Pseudocode

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

Klicken Sie hier , um Informationen zur Implementierung der Einfügesortierung in der Programmiersprache C zu erhalten .