Insättningssortering är en enkel sorteringsalgoritm som fungerar som vi sorterar spelkort i våra händer.
Python-program för insättningssortering
Funktionen insertionSort tar en array arr som indata. Den beräknar först längden på arrayen (n). Om längden är 0 eller 1, returnerar funktionen omedelbart eftersom en array med 0 eller 1 element anses redan sorterad.
För arrayer med mer än ett element fortsätter funktionen att iterera över arrayen med början från det andra elementet. Den tar det aktuella elementet (kallas nyckeln) och jämför det med elementen i den sorterade delen av arrayen som föregår den. Om nyckeln är mindre än ett element i den sorterade delen, flyttar funktionen det elementet åt höger, vilket skapar utrymme för nyckeln. Denna process fortsätter tills den korrekta positionen för nyckeln hittas, och den sätts sedan in i den positionen.
Det medföljande exemplet visar sorteringsprocessen med hjälp av insättningssorteringsalgoritmen. Den initiala arrayen [12, 11, 13, 5, 6] utsätts för funktionen insertionSort. Efter sortering ska matrisen vara [5, 6, 11, 12, 13]. Koden skriver ut den sorterade matrisen som den slutliga utmatningen.
nätverkstopologier
Pytonorm
datastrukturer i java
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)> |
>
>
Produktion:
Sorted array is: [5, 6, 11, 12, 13]>
Tidskomplexitet: O(N2)
Hjälputrymme: O(1)
Se hela artikeln om Insättningssortering för mer detaljer!