Sortowanie przez wybieranie
Znajduje najmniejszą z pozostałych wartości i zamienia ją miejscami z pierwszą nieposortowaną. Zamian robi bardzo mało, ale porównań zawsze tyle samo.
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- nie
- tak
Najlepszy przypadek: jak czas rośnie z rozmiarem listy n, gdy dane są dla tego algorytmu najłatwiejsze.
Średni: jak czas zwykle rośnie z n. Przy n² dwa razy więcej wartości sortuje się około czterech razy dłużej; n log n rośnie dużo wolniej.
Najgorszy przypadek: jak rośnie czas przy najtrudniejszych danych. Ważny, gdy sortowanie nigdy nie może zwolnić.
Pamięć: ile dodatkowej pamięci potrzeba poza listą. 1 to kilka zmiennych, n to kopia listy.
Stabilny: dwie równe wartości zachowują pierwotną kolejność. Ważne przy sortowaniu rekordów według jednego pola.
Bez dodatkowej pamięci: sortuje w samej liście, bez drugiej listy.
- porównywanie
- przenoszenie
- bieżące minimum
- na właściwym miejscu
Spróbuj: Wybierz listę odwróconą. Porównań jest dokładnie tyle samo co dla każdej innej listy.
Jak to działa
Przejrzyj nieposortowaną część i znajdź najmniejszą wartość. Zamień ją miejscami z pierwszą nieposortowaną, a kolejna wartość trafi na właściwe miejsce. Sprawdzane są zawsze wszystkie pozostałe wartości, nawet gdy lista jest już posortowana.
Kiedy warto go użyć
Przydaje się, gdy przenoszenie danych jest kosztowne, a odczyt tani, bo na każdym miejscu robi najwyżej jedną zamianę. Poza tym zwykle lepiej wybrać sortowanie przez wstawianie.