INF.04Algorytmika i Struktury Danych
Sortowanie przez wybieranie (Selection Sort)
Algorytm sortowania polegający na znajdowaniu najmniejszego elementu w nieposortowanej części tablicy i zamianie go z elementem na początku.
Zasada działania:
W każdym kroku algorytm przeszukuje nieposortowaną część tablicy w poszukiwaniu elementu minimalnego, po czym zamienia go z pierwszym elementem nieposortowanego fragmentu.
Złożoność:
- Czasowa: Zawsze O(n²) (wykonuje stałą liczbę porównań (n(n-1) / 2) niezależnie od początkowego uporządkowania danych).
- Liczba zamian (swaps): Maksymalnie n-1 zamian (przydatne, gdy koszt zapisu w pamięci jest bardzo wysoki).
- Pamięciowa: O(1) (w miejscu).
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Sortowanie przez wybieranie (Selection Sort) lub rozpocznij trening.