Sortowanie przez wstawianie
Buduje posortowaną część po lewej stronie, dokładając po jednej wartości. Każdą kolejną wartość wyjmuje i przesuwa w lewo, dopóki nie natrafi na mniejszą.
- najlepszy Ω(n)
- średni Θ(n²)
- najgorszy O(n²)
- pamięć O(1)
- stabilny
- bez dodatkowej pamięci
Co to znaczy?
- 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
- w ręku
- posortowana część
- na właściwym miejscu
Naciśnij Odtwórz, a linie pokażą, jak rośnie koszt
Naciśnij Odtwórz albo przechodź przez algorytm krok po kroku.
Spacja: odtwórz lub wstrzymaj. Strzałki lewo/prawo: krok. Home i End: przeskocz.
Spróbuj: Wybierz listę prawie posortowaną. Prawie nic się nie przesuwa, więc sortowanie kończy się po bardzo niewielu krokach.
Jak to działa
Lewa część jest zawsze posortowana. Wyjmij kolejną wartość. Wszystkie większe od niej wartości z posortowanej części przesuń o jedno miejsce w prawo, a wyjętą wartość włóż w powstałą lukę. Tak właśnie wiele osób układa karty w ręce.
Kiedy warto go użyć
Dobry wybór dla krótkich list i list prawie posortowanych, na których działa bardzo szybko. Biblioteki sortujące korzystają z niego przy małych fragmentach listy, wewnątrz szybszych metod.