Program Python za razvrščanje z vstavljanjem
Razvrščanje z vstavljanjem je preprost algoritem za razvrščanje, ki deluje tako, kot razvrščamo igralne karte v rokah.
Program Python za razvrščanje z vstavljanjem
Funkcija insertionSort kot vhod sprejme matriko arr. Najprej izračuna dolžino niza (n). Če je dolžina 0 ali 1, se funkcija takoj vrne, saj se matrika z 0 ali 1 elementom šteje za že razvrščeno.
Pri nizih z več kot enim elementom funkcija nadaljuje s ponavljanjem po nizu, začenši z drugim elementom. Vzame trenutni element (ki ga imenujemo ključ) in ga primerja z elementi v razvrščenem delu matrike, ki je pred njim. Če je ključ manjši od elementa v razvrščenem delu, funkcija premakne ta element v desno in ustvari prostor za ključ. Ta postopek se nadaljuje, dokler ni najden pravilni položaj za ključ, nato pa se v ta položaj vstavi.
Navedeni primer prikazuje postopek razvrščanja z uporabo algoritma za razvrščanje z vstavljanjem. Začetna matrika [12, 11, 13, 5, 6] je podvržena funkciji insertionSort. Po razvrščanju mora biti polje [5, 6, 11, 12, 13]. Koda natisne razvrščeno matriko kot končni rezultat.
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)> |
Izhod:
Sorted array is: [5, 6, 11, 12, 13]
Časovna zahtevnost: O(N 2 )
Pomožni prostor: O(1)
Oglejte si celoten članek Razvrščanje vstavljanja za več podrobnosti!
