Sortowanie przez wybór to prosty algorytm sortowania, który polega na wielokrotnym wyszukiwaniu najmniejszego albo największego elementu w nieposortowanej części zbioru i przenoszeniu go na właściwą pozycję.
Zasada działania
Dla sortowania rosnącego algorytm działa następująco:
- Znajdź najmniejszy element w całej tablicy.
- Zamień go z elementem na pierwszej pozycji.
- Następnie znajdź najmniejszy element w pozostałej, nieposortowanej części tablicy.
- Zamień go z elementem na drugiej pozycji.
- Powtarzaj proces aż do uporządkowania całej tablicy.
Przykład
Dla tablicy:
[5, 2, 4, 1]
Kolejne kroki mogą wyglądać tak:
[1, 2, 4, 5] // znaleziono 1 i zamieniono z 5
[1, 2, 4, 5] // 2 jest już na właściwym miejscu
[1, 2, 4, 5] // 4 jest już na właściwym miejscu
Cechy algorytmu
- jest prosty do zrozumienia i zaimplementowania,
- wykonuje mało zamian w porównaniu z sortowaniem bąbelkowym,
- ma złożoność czasową O(n²),
- zwykle nie jest stosowany dla dużych zbiorów danych,
- w podstawowej wersji nie jest algorytmem stabilnym.
Różnica względem sortowania bąbelkowego
Sortowanie bąbelkowe porównuje sąsiednie elementy i zamienia je miejscami. Sortowanie przez wybór najpierw wyszukuje najmniejszy element w nieposortowanej części, a dopiero potem wykonuje zamianę.