Sortowanie przez wybieranie

Sortowanie przez wybieranie porządkuje listę tak, jak wiele osób układa karty w ręce: znajdź najmniejszą, połóż ją na początku, potem znajdź najmniejszą z pozostałych. Wykonuje dużo porównań, ale bardzo mało zamian, a jego czas działania prawie nie zależy od kolejności listy.

Sortowane słupki różnej wysokości: posortowana część po lewej, wyróżniony najmniejszy pozostały słupek i strzałka pokazująca jego zamianę na właściwe miejsce
Sortowane słupki różnej wysokości: posortowana część po lewej, wyróżniony najmniejszy pozostały słupek i strzałka pokazująca jego zamianę na właściwe miejsce

Idea

Podziel listę na posortowaną część po lewej, na początku pustą, i nieposortowaną część po prawej. Przejrzyj nieposortowaną część i zapamiętaj, gdzie jest jej najmniejsza wartość. Zamień tę wartość z pierwszą nieposortowaną: posortowana część urosła o jeden element. Powtarzaj, aż zostanie jedna wartość, która musi być największa.

Przykład

Weź 5, 1, 4, 2, 8. Pierwszy przebieg sprawdza wszystkie pięć wartości, znajduje 1 jako najmniejszą i zamienia ją z 5: 1, 5, 4, 2, 8. Drugi przebieg sprawdza 5, 4, 2, 8, znajduje 2 i zamienia ją z 5: 1, 2, 4, 5, 8. Trzeci przebieg zastaje 4 już na miejscu, a czwarty zastaje na miejscu 5, więc nic się nie przesuwa. To 4 + 3 + 2 + 1 = 10 porównań i tylko 2 zamiany. Sortowanie bąbelkowe potrzebuje na tej samej liście 4 zamian.

Zawsze tyle samo porównań

Aby mieć pewność, która wartość jest najmniejsza, trzeba sprawdzić każdą pozostałą. Przebieg 1 wykonuje n − 1 porównań, przebieg 2 wykonuje n − 2 i tak dalej aż do 1, co daje razem n(n − 1)/2. Ta liczba nie zależy od listy: posortowana lista kosztuje dokładnie tyle porównań co odwrócona. Sortowanie przez wybieranie nie może skończyć wcześniej, bo przebieg, który zastaje najmniejszą wartość już na początku, nie dowiaduje się niczego o reszcie.

Mało zamian

Każdy przebieg wykonuje najwyżej jedną zamianę, więc sortowanie przez wybieranie nigdy nie wykonuje więcej niż n − 1 zamian, a pomija zamianę, gdy najmniejsza wartość jest już na miejscu. Sortowanie bąbelkowe i sortowanie przez wstawianie wykonują tyle zamian, ile jest par w złej kolejności, czyli nawet około n²/2. Gdy zapis wartości jest dużo droższy niż odczyt dwóch, na przykład w pamięci, która zużywa się przy każdym zapisie, mała liczba zamian jest zaletą.

Nie jest stabilne

Sortowanie jest stabilne, gdy równe wartości zachowują pierwotną kolejność. Sortowanie przez wybieranie takie nie jest, bo zamiana na dużą odległość może przenieść wartość za równą jej wartość. W 2, 2, 1 pierwszy przebieg zamienia pierwszą dwójkę z jedynką, co daje 1, 2, 2 z dwiema dwójkami w odwrotnej kolejności. Wersja, która przesuwa wartości pośrodku zamiast je zamieniać, jest stabilna, ale przenosi znacznie więcej wartości.

Wypróbuj

Otwórz aplikację i naciśnij Odtwórz albo Krok, aby przechodzić po jednym porównaniu. Sprawdzana wartość jest wyróżniona, dotąd najmniejsza wartość ma własny kolor, a każdy przebieg kończy się zamianą do posortowanej części po lewej. Wypróbuj listę posortowaną i odwróconą: porównań jest tyle samo, różnią się tylko zamiany.

Często zadawane pytania

Jaka jest złożoność czasowa sortowania przez wybieranie?

O(n²) w każdym przypadku: dokładnie n(n − 1)/2 porównań dla n wartości, niezależnie od ich kolejności. Wykonuje najwyżej n − 1 zamian i potrzebuje tylko O(1) dodatkowej pamięci.

Czym sortowanie przez wybieranie różni się od bąbelkowego?

Sortowanie bąbelkowe zamienia sąsiadów po drodze i może skończyć wcześniej, gdy przebieg nic nie zamieni. Sortowanie przez wybieranie zapamiętuje tylko, gdzie jest najmniejsza wartość, i wykonuje jedną zamianę na końcu każdego przebiegu. Sortowanie przez wybieranie wykonuje mniej zamian; bąbelkowe jest szybsze dla list prawie posortowanych.

Czy sortowanie przez wybieranie jest stabilne?

Nie. Zamiana może przenieść wartość za inną, równą jej wartość, więc równe wartości mogą zmienić kolejność. Można uczynić je stabilnym, przesuwając wartości zamiast je zamieniać, co kosztuje więcej przesunięć.

Jaki jest związek sortowania przez kopcowanie z sortowaniem przez wybieranie?

Sortowanie przez kopcowanie to sortowanie przez wybieranie z szybszym sposobem znajdowania następnej wartości: trzyma nieposortowaną część w kopcu, więc każdy wybór zajmuje około log n kroków zamiast pełnego przeglądu. To obniża całość do O(n log n).

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj sortowanie przez wybieranie