Python-program for innsettingssortering
Innsettingssortering er en enkel sorteringsalgoritme som fungerer slik vi sorterer spillkort i hendene våre.
Python-program for innsettingssortering
InsertionSort-funksjonen tar en array arr som input. Den beregner først lengden på matrisen (n). Hvis lengden er 0 eller 1, returnerer funksjonen umiddelbart ettersom en matrise med 0 eller 1 element anses som allerede sortert.
For matriser med mer enn ett element, fortsetter funksjonen med å iterere over matrisen fra det andre elementet. Den tar det gjeldende elementet (referert til som nøkkelen) og sammenligner det med elementene i den sorterte delen av matrisen som går foran det. Hvis nøkkelen er mindre enn et element i den sorterte delen, flytter funksjonen dette elementet til høyre, og skaper plass til nøkkelen. Denne prosessen fortsetter til riktig posisjon for nøkkelen er funnet, og den settes deretter inn i den posisjonen.
Det medfølgende eksemplet demonstrerer sorteringsprosessen ved å bruke innsettingssorteringsalgoritmen. Den innledende matrisen [12, 11, 13, 5, 6] utsettes for funksjonen insertionSort. Etter sortering skal matrisen være [5, 6, 11, 12, 13]. Koden skriver ut den sorterte matrisen som den endelige utgangen.
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)> |
Produksjon:
Sorted array is: [5, 6, 11, 12, 13]
Tidskompleksitet: O(N 2 )
Hjelpeområde: O(1)
Vennligst se fullstendig artikkel om Innsettingssortering for flere detaljer!
