Invoegsortering is een eenvoudig sorteeralgoritme dat werkt zoals we speelkaarten in onze handen sorteren.
Python-programma voor invoegsortering
De functie insertionSort neemt een array arr als invoer. Het berekent eerst de lengte van de array (n). Als de lengte 0 of 1 is, retourneert de functie onmiddellijk omdat een array met 0 of 1 element als reeds gesorteerd wordt beschouwd.
Voor arrays met meer dan één element itereert de functie over de array, beginnend bij het tweede element. Het neemt het huidige element (ook wel de sleutel genoemd) en vergelijkt dit met de elementen in het gesorteerde gedeelte van de array die eraan voorafgaan. Als de sleutel kleiner is dan een element in het gesorteerde gedeelte, verschuift de functie dat element naar rechts, waardoor er ruimte ontstaat voor de sleutel. Dit proces gaat door totdat de juiste positie voor de sleutel is gevonden en deze vervolgens in die positie wordt geplaatst.
Het gegeven voorbeeld demonstreert het sorteerproces met behulp van het invoegsorteeralgoritme. De initiële array [12, 11, 13, 5, 6] wordt onderworpen aan de insertionSort-functie. Na het sorteren moet de array [5, 6, 11, 12, 13] zijn. De code drukt de gesorteerde array af als de uiteindelijke uitvoer.
git alles toevoegen
Python
int in tekenreeks
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)> |
>
>
Uitgang:
Sorted array is: [5, 6, 11, 12, 13]>
Tijdcomplexiteit: O(N2)
Hulpruimte: O(1)
Raadpleeg het volledige artikel op Invoegsortering voor meer details!