Sortowanie przez wstawianie

Wprowadzenie

Sortowanie przez wstawienie (insertion sort) to algorytm, którego czas działania wynosi O(n²). Jest on skuteczny dla małej ilości danych. Jest to jeden z prostszych i jeden z bardziej znanych algorytmów sortowania. Jest on stabilny i nie wymaga dodatkowej pamięci (działa w miejscu). Często stosujemy go podczas gry w karty, biorąc je ze stołu. Biorąc po jednej karcie ze stołu wstawiamy ją w odpowiednie miejsce do kart, które mamy w ręce.

Przykład

Rozważmy jakiś przykład. Weźmy następujący ciąg liczb do posortowania:

Możemy sobie wyobrazić, że liczby po prawej stronie to nasze karty na stole, które będziemy po kolei brać, a te, które są po lewej (na razie nie mamy żadnej) to karty, które trzymamy w ręce. Przypominam, że każdą kartę, którą bierzemy ze stołu wstawiamy w odpowiednie miejsce wśród kart, które mamy w ręce tak, aby były one posortowane.

Tak więc bierzemy pierwszą liczbę (w tym wypadku jest to 3) i przenosimy ją na lewą stronę. Nie musimy nic poza tym robić, ponieważ po lewej stronie nie ma żadnych liczb. W ten sposób otrzymujemy:

Teraz bierzemy kolejną liczbę z lewej strony, czyli 0 i wstawiamy w odpowiednią pozycję po lewej stronie. Ponieważ 0 jest mniejsze od 3, więc wstawiamy je przed tą liczbę:

Podobnie postępujemy z liczbą 9. Ponieważ jest ona największa z tych po lewej, więc wstawiamy ją na końcu:

Następnie wstawiamy pierwszą liczbę w ciągu po prawej, czyli 5 w odpowiednie miejsce w ciągu po lewej. Odpowiednie miejsce dla tej liczby to pozycja między liczbami 3 i 9:

Postępując podobnie jak wyżej z 1 wstawiamy ją po lewej stronie między 0 a 3:

Tak samo dla liczby 7 - wstawiamy ją między liczby 5 i 9:

Na sam koniec wstawiamy ostatnią z liczb - 6 do ciągu po lewej stronie między 5 a 7:

Algorytm sortowania przez wstawianie najlepiej jest zaimplementować na strukturach danych zwanych listami, są one bowiem w tym przypadku bardziej elastyczne. Implementacja na tablicach może być mało efektywna ze względu na konieczność przesuwania danych w tychże tablicach.

<< Powrót na stonę główną