Valintalajittelualgoritmi lajittelee taulukon etsimällä toistuvasti (nousevassa järjestyksessä) minimielementin lajittelemattomasta osasta ja sijoittamalla sen alkuun. Algoritmi ylläpitää kahta alitaulukkoa tietyssä taulukossa.
Python-ohjelma valintalajitteluun
Toimitettu Python-koodi esittelee Selection Sort -algoritmin. Valintalajittelun aikamonimutkaisuus on O(n^2). Jokaisessa iteraatiossa koodi löytää minimielementin indeksin taulukon lajittelemattomasta osasta ja vaihtaa sen nykyisen indeksin elementin kanssa. Tämä lajittelee taulukon vähitellen vasemmalta oikealle. Esimerkki alustaa taulukon, lajittelee sen käyttämällä selectSort-funktiota ja tulostaa sitten lajitellun taulukon nousevassa järjestyksessä. Lajiteltu matriisi saadaan etsimällä toistuvasti lajittelemattoman osan pienin elementti ja asettamalla se oikeaan paikkaan, jolloin saadaan järjestetty taulukko: [-202, -97, -9, -2, 0, 11, 45, 88, 747].
Python 3
# 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)> |
>
>Lähtö
The array after sorting in Ascending Order by selection sort is: [-202, -97, -9, -2, 0, 11, 45, 88, 747]>
Aika monimutkaisuus : Päällä2).
Aputila : O(1).
Katso täydellinen artikkeli aiheesta Valinta Lajittele Lisätietoja!