Algorytm selection sort, czyli sortowania przez wybór, można wyprowadzić z definicji problemu sortowania. Zauważmy, że jeśli mamy ustawić elementy ciągu w porządku niemalejącym, to można najpierw wybrać element najmniejszy i umieścić go na początku, za nim umieścić drugi najmniejszy element ciągu, czyli najmniejszy w pozostałym ciągu. W ten sposób należy postępować do momentu, kiedy cały ciąg jest już posortowany. Do opisania tego algorytmu potrzebna jest znajomość algorytmu znajdowania najmniejszego elementu w zbiorze. Teraz należy już tylko podać sposób, w jaki kolejno znajdowane elementy, mają być wstawiane do ciągu wynikowego. Najoszczędniej byłoby robić to w tym samym miejscu, w którym jest zapisany ciąg wejściowy. Aby tego dokonać, należy znaleziony element zamienić z elementem, który zajmuje jego miejsce w posortowanym ciągu. Oznacza to, że po znalezieniu najmniejszego elementu należy zamienić go miejscami z pierwszym elementem ciągu, następnie drugi najmniejszy element zamienić z drugim elementem ciągu itd.
Sposób działania algorytmu sortowania przez wybór został zilustrowany na poniższym rysunku. Zwróćmy uwagę na trzecią iterację. Bieżący najmniejszy element ciągu może się już znajdować na swoim miejscu w ciągu. Sytuacja ta nie jest jednak wyróżniana w tym algorytmie. W takim przypadku element jest zamieniany z samym sobą.
Algorytm sortowania przez wybór (selection sort)
Dane: Liczba naturalna n i ciąg n liczb a1, a2, ..., an.
Wynik: Uporządkowanie tego ciągu liczb niemalejąco.
SelectionSort(n)
for i ← 1 to n-1
k ← index najmniejszego elementu podciągu a[i...n]
a[i] ↔ a[k]
Aby znaleźć postać wyrażenia, które określa liczbę działań (porównań i przestawień elementów) wykonywanych w algorytmie sortowania przez wybór, wystarczy zauważyć, że jest on iteracją algorytmu znajdowania najmniejszego elementu w ciągu, który w kolejnych iteracjach jest coraz krótszy. Liczba przestawień jest równa liczbie iteracji, wynosi więc n-1, zaś liczba porównań jest równa (n-1) + (n-2) + ... + 2 + 1. Wartość tej sumy można obliczyć wieloma sposobami, a wynosi ona: n(n-1)/2
Do głównych zalet przedstawionego algorytmu należą:
Moje namiary: |