Sortowanie przez wstawianie – algorytm i implementacja w C++

Jednym z podstawowych algorytmów, które musi znać każdy z początkujących programistów, jest sortowanie przez wstawianie (insertion sort). Ten właśnie algorytm oraz jego implementację, poznamy w tej części „Piątku z sortowaniem”.

Jak to działa?

Zasada funkcjonowania tego algorytmu przedstawia się w następujący sposób. Każdą iterację zaczynamy od wybrania elementu (startując od pierwszego miejsca w tablicy), który będziemy przyrównywać, do elementów znajdujących się na pozycjach poprzedzających. Jeżeli element znajdujący się przed wybranym przez nas elementem jest większy, przesuwamy się o jedno miejsce wstecz.

Robimy tak, aż do momentu, gdy znajdziemy się na pozycji, w której element poprzedzający jest mniejszy, lub dojdziemy do początku tablicy. Wybrany element wstawiamy na tą właśnie pozycję. Wszystkie elementy, znajdujące się przed jego wcześniejszą pozycją, przesuwamy o jedną pozycję w głąb tablicy. Następnie powtarzamy ten proces, dla kolejnych elementów w tablicy, aż rozpatrzymy ostatni jej element.

Karciany porządek

Zasady działania tego sortowania, mogą brzmieć nieco chaotycznie, lecz każdy z nas może zobrazować sobie działanie tego algorytmu, na prostej sytuacji z życia codziennego. Wyobraźmy sobie, że podczas gry w karty dobraliśmy właśnie króla, piątkę, damę, dwójkę i dziewiątkę.

By za każdym razem nie szukać kart w swojej ręce, chcemy je posortować. Na początku bierzemy więc piątkę i przekładamy ją na sam początek. Króla zastawiamy na miejscu, ponieważ piątka która znajduje się przed nim, ma
mniejszą wartość. Kolejna, przeniesiona zostaje dama. Ląduje na miejscu między piątką, a królem. W następnym kroku bierzemy dwójkę i przenosimy ją na sam początek, po czym dziewiątkę wstawiamy pomiędzy piątkę i damę.

Poniżej zobaczycie wizualizację procesu sortowania przez wstawianie, na przykładzie omówionym powyżej:

W taki sposób posortowaliśmy właśnie wszystkie karty na naszej ręce. Czy to nie proste? Ponoć, to właśnie sposób w jaki ludzie układają karty w ręce podczas gry, był inspiracją dla tego algorytmu.

Sortowanie przez wstawianie – Implementacja w C++

grupa wsparcia matura z informatyki

Złożoność

Algorytm sortowania przez wstawianie, tak jak większość prostszych algorytmów, posiada złożoność rzędu O(n2). Taka wartość złożoności czasowej nie należy do najniższych i jest identyczna, jak algorytmu sortowania bąbelkowego.

Nie mniej jednak, algorytm ten ma swoje zalety. Oprócz łatwej implementacji, radzi on sobie bardzo dobrze z niedużymi tablicami. Ponadto algorytm ten, w przeciwieństwie algorytmu sortowania przez wybór, jest algorytmem stabilnym. Co to jednak oznacza?

Algorytmy stabilne cechują się tym, że jeśli w zbiorze znajdowały się elementy o identycznej wartości, to po posortowaniu tego zbioru będą ustawione w takiej samej kolejności, jaką miały w zbiorze nieposortowanym. Przykładowo mając zbiór [3, 2a, 5, 2b, 1], po posortowaniu go algorytmem niestabilnym, możemy otrzymać: [1, 2b, 2a, 3, 5]. Korzystając z algorytmu stabilnego, zawsze otrzymamy następujący zbiór: [1, 2a, 2b, 3, 5].

Podsumowanie

Znając już zasadę działania oraz przykładową implementację, wykonaliście kolejny krok, w kierunku pełnego przygotowania do matury z informatyki. Jeśli chcecie poznać kolejne algorytmy sortowania oraz ich implementację, zapraszam was za tydzień na kolejną część „Piątku z sortowaniem”. Ukarze się on, jak zwykle, na waszym ulubionym serwisie binarnie.pl 😉.

You Might Also Like
2 komentarze
Dodaj komentarz