PYTHON-PROGRAMM FÜR EINFÜGUNGSSORTIERUNG

Insertion Sort ist ein einfacher Sortieralgorithmus, der so funktioniert, wie wir Spielkarten in unseren Händen sortieren.

Die Funktion insertSort verwendet ein Array arr als Eingabe. Zunächst wird die Länge des Arrays (n) berechnet. Wenn die Länge 0 oder 1 beträgt, kehrt die Funktion sofort zurück, da ein Array mit 0 oder 1 Elementen als bereits sortiert betrachtet wird.

Bei Arrays mit mehr als einem Element iteriert die Funktion ab dem zweiten Element über das Array. Es nimmt das aktuelle Element (als Schlüssel bezeichnet) und vergleicht es mit den Elementen im sortierten Teil des Arrays davor. Wenn der Schlüssel kleiner als ein Element im sortierten Teil ist, verschiebt die Funktion dieses Element nach rechts und schafft so Platz für den Schlüssel. Dieser Vorgang wird fortgesetzt, bis die richtige Position für den Schlüssel gefunden ist und er dann an dieser Position eingefügt wird.

Das bereitgestellte Beispiel demonstriert den Sortiervorgang mithilfe des Einfügesortieralgorithmus. Das anfängliche Array [12, 11, 13, 5, 6] wird der Funktion insertSort unterzogen. Nach dem Sortieren sollte das Array [5, 6, 11, 12, 13] sein. Der Code gibt das sortierte Array als endgültige Ausgabe aus.

Python

def> insertionSort(arr):> > n> => len> (arr)> # Get the length of the array> > > if> n <> => 1> :> > return> # If the array has 0 or 1 element, it is already sorted, so return> > for> i> in> range> (> 1> , n):> # Iterate over the array starting from the second element> > key> => arr[i]> # Store the current element as the key to be inserted in the right position> > j> => i> -> 1> > while> j>> => 0> and>

key # Move elements greater than key one position ahead  arr[j+1] = arr[j] # Shift elements to the right  j -= 1  arr[j+1] = key # Insert the key in the correct position   # Sorting the array [12, 11, 13, 5, 6] using insertionSort arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr)>

Ausgabe: