Python programa, skirta atrankos rūšiavimui
Pasirinkimo rūšiavimo algoritmas rūšiuoja masyvą, pakartotinai surasdamas minimalų elementą (atsižvelgiant į didėjančią tvarką) iš nerūšiuotos dalies ir įtraukdamas jį į pradžią. Algoritmas tam tikrame masyve palaiko dvi pogrupes.
Python programa, skirta atrankos rūšiavimui
Pateiktas Python kodas parodo pasirinkimo rūšiavimo algoritmą. Pasirinkimo rūšiavimo laiko sudėtingumas yra O(n^2). Kiekvienoje iteracijoje kodas suranda minimalaus elemento indeksą nerūšiuotoje masyvo dalyje ir pakeičia jį dabartinio indekso elementu. Tai palaipsniui rūšiuoja masyvą iš kairės į dešinę. Pavyzdyje inicijuojamas masyvas, pritaikoma funkcija selectSort, kad jis būtų rūšiuojamas, o tada išspausdinamas surūšiuotas masyvas didėjančia tvarka. Surūšiuotas masyvas gaunamas pakartotinai surandant mažiausią elementą nerūšiuotoje dalyje ir įdedant jį į teisingą padėtį, todėl gaunamas tvarkingas masyvas: [-202, -97, -9, -2, 0, 11, 45, 88, 747].
Python3
# Selection sort in Python> # time complexity O(n*n)> #sorting by finding min_index> def> selectionSort(array, size):> > > for> ind> in> range> (size):> > min_index> => ind> > for> j> in> range> (ind> +> 1> , size):> > # select the minimum element in every iteration> > if> array[j] min_index = j # swapping the elements to sort the array (array[ind], array[min_index]) = (array[min_index], array[ind]) arr = [-2, 45, 0, 11, -9,88,-97,-202,747] size = len(arr) selectionSort(arr, size) print('The array after sorting in Ascending Order by selection sort is:') print(arr)> |
Išvestis
The array after sorting in Ascending Order by selection sort is: [-202, -97, -9, -2, 0, 11, 45, 88, 747]
Laiko sudėtingumas : O (n 2 ).
Pagalbinė erdvė : O(1).
Peržiūrėkite visą straipsnį apie Pasirinkimas Rūšiuoti daugiau detalių!
