Python programa, skirta įterpimo rūšiavimui
Įterpimo rūšiavimas yra paprastas rūšiavimo algoritmas, kuris veikia taip, kaip mes rūšiuojame žaidimo kortas savo rankose.
Python programa, skirta įterpimo rūšiavimui
Funkcija insertionSort kaip įvestį paima masyvą arr. Pirmiausia apskaičiuojamas masyvo ilgis (n). Jei ilgis yra 0 arba 1, funkcija iš karto grįžta, nes masyvas su 0 arba 1 elementu laikomas jau surūšiuotu.
Masyvuose, kuriuose yra daugiau nei vienas elementas, funkcija kartojasi per masyvą, pradedant nuo antrojo elemento. Jis paima dabartinį elementą (vadinamas kaip raktas) ir lygina jį su elementais, esančiais prieš jį surūšiuotoje masyvo dalyje. Jei raktas yra mažesnis nei elementas rūšiuotoje dalyje, funkcija perkelia tą elementą į dešinę, sukurdama vietos raktui. Šis procesas tęsiamas tol, kol randama teisinga rakto padėtis, tada jis įterpiamas į tą padėtį.
Pateiktame pavyzdyje parodytas rūšiavimo procesas naudojant įterpimo rūšiavimo algoritmą. Pradiniam masyvui [12, 11, 13, 5, 6] taikoma įterpimo rūšiavimo funkcija. Po rūšiavimo masyvas turi būti [5, 6, 11, 12, 13]. Kodas išspausdina surūšiuotą masyvą kaip galutinę išvestį.
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>>> |
