Sortowanie przez wstawianie

Sortowanie przez wstawianie to sposób, w jaki większość ludzi układa karty w ręce: bierzesz kolejną kartę i wsuwasz ją na właściwe miejsce wśród kart, które są już ułożone. Jest wolne dla długich losowych list, ale bardzo szybkie dla krótkich lub prawie posortowanych, dlatego prawdziwe biblioteki sortujące wciąż z niego korzystają.

Sortowane słupki: posortowana część po lewej i jeden słupek wsuwający się do niej wstecz obok większych słupków
Sortowane słupki: posortowana część po lewej i jeden słupek wsuwający się do niej wstecz obok większych słupków

Idea

Utrzymuj początek listy posortowany. Na starcie ta posortowana część to tylko pierwsza wartość. Weź kolejną wartość i porównaj ją z poprzednią. Jeśli poprzednia jest większa, zamień je i porównaj znowu, o jedno miejsce dalej wstecz. Zatrzymaj się, gdy poprzednia wartość nie jest większa albo gdy wartość dotrze na początek. Posortowana część urosła o jedną wartość. Powtarzaj to z każdą wartością aż do końca.

Przykład

Weźmy 5, 1, 4, 2, 8. Przebieg 1 bierze 1: 5 jest większe, więc je zamieniamy, i 1 trafia na początek: 1, 5, 4, 2, 8. Przebieg 2 bierze 4: zamienia się z 5, a potem zatrzymuje na 1: 1, 4, 5, 2, 8. Przebieg 3 bierze 2: zamienia się z 5 i z 4, a potem zatrzymuje na 1: 1, 2, 4, 5, 8. Przebieg 4 bierze 8, które jest już większe od 5, więc wystarczy jedno porównanie. Razem 7 porównań i 4 zamiany. Sortowanie bąbelkowe potrzebuje na tej samej liście 9 porównań, a sortowanie przez wybieranie 10.

Zamian jest tyle, co inwersji

Inwersja to para wartości w złej kolejności. Zamiana dwóch sąsiadów w złej kolejności usuwa dokładnie jedną inwersję, a sortowanie przez wstawianie zamienia tylko takich sąsiadów. Wykonuje więc dokładnie tyle zamian, ile inwersji ma lista początkowa, czyli tyle samo co sortowanie bąbelkowe. Każdy przebieg wykonuje też najwyżej jedno porównanie, które nie prowadzi do zamiany: to, które go kończy. Porównań jest więc tyle, ile inwersji, plus najwyżej n − 1.

Adaptacyjne: szybkie, gdy lista jest prawie posortowana

Ponieważ praca to liczba inwersji plus około n, sortowanie przez wstawianie jest szybkie zawsze, gdy inwersji jest mało. Posortowana lista wymaga n − 1 porównań i żadnych zamian. Lista, w której każda wartość jest tylko kilka pozycji od właściwego miejsca, zajmuje czas bliski n. Tylko lista daleka od posortowanej, na przykład odwrócona z n(n − 1)/2 inwersjami, zajmuje czas proporcjonalny do n². Dla losowej listy średnio wychodzi około n²/4 zamian.

Gdzie się je stosuje

Sortowanie przez wstawianie jest stabilne, nie potrzebuje dodatkowej pamięci i ma bardzo mały narzut. Dla krótkich list pokonuje algorytmy, które na papierze są szybsze. Wiele sortowań w bibliotekach, takich jak Timsort (Python i Java) czy introsort (C++), przełącza się na sortowanie przez wstawianie dla małych fragmentów listy, zwykle do kilkudziesięciu wartości. Pasuje też do danych napływających po jednej wartości, bo każdą nową wartość można wstawić od razu, gdy się pojawi.

Sprawdź w praktyce

Otwórz aplikację i naciśnij Odtwórz albo Krok, aby przechodzić po jednym porównaniu. Wstawiana wartość ma własny kolor, wartość, z którą jest porównywana, jest wyróżniona, a posortowana część jest zielona. Inaczej niż w sortowaniu bąbelkowym i przez wybieranie zielona część nie jest ostateczna: późniejsza, mniejsza wartość wciąż może się do niej wsunąć. Wypróbuj prawie posortowaną listę, aby zobaczyć, jak krótkie są przebiegi, a potem odwróconą.

Często zadawane pytania

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

O(n²) w najgorszym i średnim przypadku oraz O(n) w najlepszym, czyli dla listy już posortowanej. Dokładniej: czas jest proporcjonalny do n plus liczby inwersji. Potrzebuje tylko O(1) dodatkowej pamięci.

Czym różni się sortowanie przez wstawianie od sortowania przez wybieranie?

Sortowanie przez wybieranie przeszukuje całą nieposortowaną część, aby znaleźć najmniejszą wartość, więc zawsze wykonuje n(n − 1)/2 porównań, ale mało zamian. Sortowanie przez wstawianie bierze kolejną wartość tak, jak przychodzi, i przesuwa ją wstecz tylko tak daleko, jak trzeba, więc wykonuje mniej porównań, zwłaszcza dla prawie posortowanych list, ale więcej zamian.

Co to jest binarne sortowanie przez wstawianie?

Wersja, która znajduje miejsce nowej wartości za pomocą wyszukiwania binarnego w posortowanej części, co wymaga około log n porównań zamiast nawet n. Wartości wciąż trzeba przesunąć, aby zrobić miejsce, więc liczba przesunięć i najgorszy przypadek O(n²) pozostają takie same.

Czy sortowanie przez wstawianie jest stabilne?

Tak. Wartość przesuwa się wstecz tylko obok wartości ściśle większych, więc równe wartości zachowują pierwotną kolejność.

Chcesz wypróbować?

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

Wypróbuj sortowanie przez wstawianie