Program w Pythonie do sortowania przez wybór
Algorytm sortowania przez wybór sortuje tablicę, wielokrotnie znajdując minimalny element (biorąc pod uwagę kolejność rosnącą) z nieposortowanej części i umieszczając go na początku. Algorytm utrzymuje dwie podtablice w danej tablicy.
Program w Pythonie do sortowania przez wybór
Dostarczony kod Pythona demonstruje algorytm sortowania przez wybór. Sortowanie przez wybór ma złożoność czasową O(n^2). W każdej iteracji kod znajduje indeks minimalnego elementu w nieposortowanej części tablicy i zamienia go z elementem bieżącego indeksu. To stopniowo sortuje tablicę od lewej do prawej. Przykład inicjuje tablicę, stosuje funkcję choiceSort w celu jej posortowania, a następnie drukuje posortowaną tablicę w kolejności rosnącej. Posortowaną tablicę uzyskuje się poprzez wielokrotne odnajdywanie najmniejszego elementu w nieposortowanej części i umieszczanie go we właściwym miejscu, w wyniku czego powstaje uporządkowana tablica: [-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)> |
Wyjście
The array after sorting in Ascending Order by selection sort is: [-202, -97, -9, -2, 0, 11, 45, 88, 747]
Złożoność czasu : NA 2 ).
Przestrzeń pomocnicza :O(1).
Proszę zapoznać się z pełnym artykułem na temat Sortowanie przez wybór po więcej szczegółów!
