Sortowanie przez wybieranie
Z Wikipedii
Sortowanie przez wybieranie - jedna z prostszych metod sortowania o złożoności O(n2). Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.
Algorytm przedstawia się następująco:
- wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy
- zamień wartość minimalną, z elementem na pozycji i
Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu.
Algorytm w zaprezentowanej postaci jest niestabilny, jednakże niewielkim kosztem można uczynić go algorytmem sortującym stabilnie. Aby tego dokonać należy jako warunek wyszukiwania minimum/maksimum zastosować nierówność nieostrą zamiast ostrej.
[edytuj] Przykład
Posortowana zostanie tablica 8-elementowa [9,1,6,8,4,3,2,0]. W tablicy pogrubione zostaną te elementy wśród których wyszukuje się wartość minimalną.
nr iteracji (wartość i) | tablica | minimum |
---|---|---|
0 | [9,1,6,8,4,3,2,0] | 0 |
1 | [0,1,6,8,4,3,2,9] | 1 (element znajduje się na właściwej pozycji) |
2 | [0,1,6,8,4,3,2,9] | 2 |
3 | [0,1,2,8,4,3,6,9] | 3 |
4 | [0,1,2,3,4,8,6,9] | 4 (...) |
5 | [0,1,2,3,4,8,6,9] | 6 |
6 | [0,1,2,3,4,6,8,9] | 8 (...) |
Algorytm można nieco przyspieszyć, gdy tablica jest wypełniana z obu końców, tj. wyszukiwane jest równocześnie minimum i maksimum.