Sortowanie przez wybór (selection sort)
Wprowadzenie
Sortowanie przez wybór jest w zasadzie jednym z najprostszych do zrozumienia i zaimplementowania w danym języku programowania algorytmem sortowania.
Sprecyzujmy warunki sortowania:
Dane: n elementów oznaczonych x[1], x[2], x[3], ..., x[n] oraz operator porównania
tych elementów, za pomocą którego możemy stwierdzić który z dwóch porównywanych elementów jest mniejszy, a który większy.
Wynik: n elementów uporządkowanych w taki sposób, że pierwszy element jest najmniejszy w sensie
operatora porównania elementów, a ostatni jest elementem największym w sensie tego samego operatora.
Algorytm w postaci listy kroków
-
Dla i od 1 do n-1 wykonaj:
- Wśród elementów x[i], ..., x[n] znajdź takie k, że x[k] jest elementem najmniejszym w sensie pewnego operatora użytego do porównywania elementów
- Zamień miejscami elementy x[i] i x[k]
- Elementy są już posortowane - zakończ algorytm
Jeśli nie wiesz jak zrealizować wyszukiwanie najmniejszego elementu w zbiorze, czyli tę część algorytmu: Wśród elementów x[i], ..., x[n] znajdź takie k, że x[k] jest elementem najmniejszym (...), przeczytaj koniecznie artykuł zatytułowany Wyszukiwanie elementu minimalnego.
Analiza algorytmu
Mimo, że algorytm jest dosyć prosty, oto wyjaśnienie. Za pierwszym razem wyszukujemy najmniejszy element wśród wszystkich danych elementów i po jego znalezieniu zamieniamy go z elementem który znajdował się na pierwszym miejscu naszych elementów.
Teraz nie zajmujemy się już pierwszym elementem, gdyż jest on ustawiony we właściwym miejscu, czyli pomniejszamy nasz zbiór elementów do przeszukiwania o jeden. Wyszukujemy najmniejszy element wśród naszego nowego zbioru i znów dokonujemy zamian.
Czynność powtarzamy do aż w naszym zbiorze elementów do przeszukiwania pozostaną tylko dwa elementy. Wtedy wykonujemy ostatnie wyszukiwanie.
Nie ma natomiast sensu już nic robić, gdy w zbiorze pozostanie jeden element, gdyż wiadomo, że jest on już dobrze ustawiony. Dlatego też zwróć uwagę, że w głównej pętli zmienna i zmienia się od 1 do n-1 a nie zmienia się ona od 1 do n.
