Sortowanie przez wstawianie – co to jest, schemat blokowy oraz implementacja

Algorytmy sortujące okazują się fundamentem jeśli chodzi o naukę programowania. Pozwalają opanować wiele ciekawych rozwiązań stosowanych w kodach aplikacji. Jednym z podstawowych algorytmów sortujących, który każdy uczeń informatyki czy uczestnik korepetycji z informatyki powinien znać, jest sortowanie przez wstawianie.

Co to jest sortowanie przez wstawianie?

Sortowanie przez wstawianie (insertion sort) to algorytm wstawiający kolejne elementy na odpowiednie miejsca do posortowanej części zbioru danych. Pierwszy element jest uznawany za uporządkowany, następnie bierze się pod uwagę drugi i ustawia się go przed lub po pierwszej wartości. Każdy kolejny cykl wygląda podobnie, następne elementy są porównywane z uporządkowanymi wartościami i wstawiane na odpowiednie miejsca. Okazuje się efektywny dla niewielkiej ilości danych. Co ciekawe, jest wykorzystywany jako część zaawansowanego algorytmu sortującego Shella.

Na czym polega sortowanie przez wstawianie – Przykład

Tak naprawdę sortowanie przez wstawianie to intuicyjna metoda sortowania. Zasada działania tego algorytmu znajduje odzwierciedlenie przy sortowaniu kart, więc zdołasz ją szybko zrozumieć.

Poniżej znajdziesz proces sortowania przez wstawianie tablicy o ilości elementów n = 5. Początkowy zbiór danych prezentuje się tak:

4 2 5 1 3

Z automatu uznaje się pierwszą liczbę za posortowaną. Dlatego też sortowanie rozpoczyna się od drugiej wartości.

4 2 5 1 3

(4 2) 5 1 3 – nawiasy oznaczają porównywane liczby

Druga liczba jest porównywana z pierwszą (a więc z częścią posortowaną), a skoro 2 jest mniejsze od 4, to następuje zamiana miejsc (sortujemy rosnąco).

2 4 5 1 3

2 4 5 1 3

2 (4 5) 1 3

2 4 5 1 3

Kolejny cykl porównywania, bierze pod uwagę liczbę 5 i porównuje ją z częścią posortowaną, w tym przypadku z 4. Jako, że 5 jest większe od 4, obie liczby pozostają na swoim miejscu.

2 4 5 1 3

2 4 (5 1) 3

W tym momencie następuje kolejny cykl i bierze się pod uwagę następny nieposortowany element, a więc 1. Po porównaniu z najbliższym elementem z części posortowanej, okazuje się, że 1 jest mniejsze od 5. Dlatego następuje zamiana ich miejsc.

2 4 1 5 3

2 (4 1) 5 3

2 1 4 5 3

Teraz porównuje się 1 z liczbą 4. Ponownie okazuje się, że wartość jest mniejsza, więc ulegają one zamianie.

2 1 4 5 3

(2 1) 4 5 3

1 2 4 5 3

Kolejne porównanie, czyli 1 z wartością 2. Liczba jest mniejsza, także następuje zamiana. Skoro nie ma kolejnych liczb do porównania, następuje koniec tego cyklu.

1 2 4 5 3

1 2 4 (5 3)

1 2 4 3 5

Ostatni już cykl, bierze pod uwagę liczbę 3. Po porównaniu z wartością 5, okazuje się, że jest mniejsza, więc następuje zamiana.

1 2 4 3 5

1 2 (4 3) 5

1 2 3 4 5

Kolejne porównanie wskazuje, że 3 jest mniejsze od 4, także oznacza to kolejną zamianę liczb.

1 2 3 4 5

1 (2 3) 4 5

1 2 3 4 5

W tym momencie, algorytm porównuje 3 oraz 2, jako że liczba 3 jest większa, pozostaje ona na swoim miejscu. Sortowanie przez wstawianie jest w tym miejscu zakończone, po czterech cyklach (ilość cykli jest zawsze mniejsza o jeden od ilości sortowanych danych).

Jak widać proces sortowania jest prosty, możesz śmiało z niego korzystać w przypadku niewielkich zbiorów danych.

Ważne!

W przedstawionym tłumaczeniu oraz gifie przedstawiane jest uproszczenie dla łatwiejszego zrozumienia tego sortowania. W ramach kodu zapisuje się aktualnie zmienianą liczbę do dodatkowej zmiennej, a następnie sprawdza się czy jest mniejsza od poprzednich wartości (po lewej), dopiero gdy znajdzie się odpowiednie miejsce, wstawia się tam tę liczbę. Z kolei na gifie oraz przykładzie, liczba jest ciągle zamieniana z mniejszymi od niej. Zmniejsza się więc liczbę operacji (wartość jest zapisywana tylko raz, w miejsce w którym powinna być).

Zalety i wady – sortowanie przez wstawianie

Zrozumienie zalet oraz wad danego algorytmu, pozwala znacznie łatwiej określić jego użyteczność w ramach tworzonego kodu.

Zalety:

• Prostota – z łatwością go zrozumiesz i zaimplementujesz,
• Idealny do małych zbiorów danych – w przypadku niewielkiej ilości danych, jego wydajność jest wysoka,
• Stabilny – elementy o identycznej wartości, pozostają na swoich miejscach względem siebie.

Wady:

• Nie nadaje się do dużych zbiorów danych – jego wydajność wtedy zauważalnie spada.

Sortowanie przez wstawianie – Jak zrobić implementację algorytmu?

Utworzenie implementacji sortowania przez wstawianie nie jest trudne. Poniższe opisy pozwolą Ci zrozumieć w jaki sposób działa, dzięki czemu zastosowanie go w przypadku poszczególnych programów okaże się łatwiejsze.

Sortowanie przez wstawianie – Schemat blokowy i pseudokod

Opis sortowania przez wstawianie – Pseudokod

• 1 linia – Rozpoczęcie funkcji i przyjęcie argumentów tablica (lista danych) oraz n (ilość sortowanych elementów).
• 2 linia – Pętla iteruje przez elementy tablicy, zaczynając od drugiego elementu (o indeksie 2) aż do ostatniego elementu (o indeksie n).
• 3 linia – Aktualny element tablicy, o indeksie i, jest zapisywany w zmiennej tymczasowej temp.
• 4 linia – Zmienna j przyjmuje wartość (i – 1), którą wykorzystamy do porównania w linii 5 (w pętli dopóki, czyli odpowiedniku while) aktualnego elementu z poprzednim.
• 5 linia – Pętla dopóki (while) sprawdza, czy indeks j jest większy od zera oraz czy wartość tablicy[j] jest większa niż wartość temp.
• 6 linia – Jeśli warunki są spełnione, to przesuwamy element w tablicy o jedno miejsce w prawo, aby zrobić miejsce dla elementu temp.
• 7 linia – Zmniejszamy wartość j o 1, aby porównać temp z poprzednim elementem.
• 8 linia – Po zakończeniu pętli dopóki (while), aktualny element temp jest wstawiany na właściwe miejsce w posortowanej części tablicy.

Sortowanie przez wstawianie – Python, C++ i Java

Sortowanie przez wstawianie dla zaawansowanych – złożoność obliczeniowa

Złożoność algorytmu sortowanie przez wstawianie wynosi O(n²).

Wynika to ze względu na wstawienie dwóch pętli przechodzących po tablicy. Jednak warto zauważyć, że jest on częściej używany niż sortowanie bąbelkowe czy przez wybieranie. Dlaczego, skoro wszystkie trzy algorytmy mają podobną złożoność?

Otóż popatrz na sytuację, gdy nasza tablica przed wykonaniem algorytmu jest już poprawnie ułożona. Sortowanie przez wybieranie jak i sortowanie bąbelkowe będą w całości wykonywać obie pętle zawarte w ich kodzie, przez co układanie posortowanej już tablicy będzie miało nadal złożoność kwadratową. Aby temu zapobiec, należy umieścić w kodzie specjalne zabezpieczenie, które dla danych posortowanych nie wykona niepotrzebnych operacji.

Co w przypadku sortowania przez wstawianie? Łatwo zauważyć, że jeśli chcesz dla uogólnienia problemu uporządkować trzeci element z pierwszymi dwoma, to skoro tablica jest posortowana to pętla zatrzyma się po pierwszym porównaniu trzeciego elementu z drugim i nie będzie iść dalej w głąb tablicy. Co z tego wynika?

Jeśli każdy element w tablicy będziemy porównywać tylko raz z jego poprzednikiem to okaże się, że w takim przypadku będziemy mieli złożoność rzędu O(n) (czyli liniową).

Jest to diametralna różnica oraz przewaga sortowania przez wstawianie nad sortowaniem bąbelkowym i przez wybieranie. Co więcej, warto również wspomnieć, że ten algorytm jest też używany do przyspieszenia działania szybkiego sortowania. Gdy w tablicy jest mało elementów (z reguły określa się to na około 20) to wtedy zastępuje się sortowanie szybkie sortowaniem przez wstawianie, ponieważ działa szybciej, szczególnie w optymistycznym przypadku podania tablicy uporządkowanej lub prawie uporządkowanej zadziała najlepiej. Oczywiście istnieje także pesymistyczny przypadek, czyli podanie do sortowania elementów ułożonych malejąco.

Sortowanie przez wstawianie to z pewnością jeden z prostszych rodzajów algorytmów, który okazuje się idealny dla początkujących. Zrozumienie w jaki sposób działa pomaga szybciej opanować podobne rozwiązania, a przy tym jest wstępem do bardziej zaawansowanych algorytmów sortujących (np. shella). W przypadku małych zbiorów liczb to metoda z której warto skorzystać.

Najczęściej zadawane pytania o sortowanie przez wstawianie

Wpisy, które mogą Cię zainteresować: