Sortowanie przez scalanie – algorytm i implementacja w C++

Czyżby nadszedł ten najbardziej wyczekiwany dzień tygodnia? Jak sami wiecie, wraz z nim obowiązkowo pojawia się kolejna część „Piątku z sortowaniem”. Po małym „spinoffie” z prezentacją gotowych metod sortowania w C++ i Javie, wracamy do klasyki. Tym razem przyjrzymy się algorytmowi sortowania przez scalanie (merge sort). Jesteście gotowi?

Algorytm

Algorytm sortowania przez scalanie, to kolejny już z algorytmów, który opiera się na zasadzie „dziel i zwyciężaj”. Można wręcz powiedzieć, że wykorzystuje ją w dość bezpośrednim rozumieniu. Główna zasada działania polega na rekurencyjnym dzieleniu tablicy na podtablice. Dzielenie kończymy, w którym, każda z podtablic w danej grupie jest tablicą jednoelementową. Łączymy je kolejno porównując wartości ich elementów. Dokładny przebieg algorytmu wygląda następująco:

Jeśli indeks prawej części tablicy (r) jest większy od indeksu lewej (l) części tablicy wykonaj następujące kroki:

  1. Znajdź środkowy indeks tablicy (m), ze wzoru m=(l+r)/2 (resztę z dzielenia zaokrąglamy w dół)
  2. Wywołaj sortowanie przez scalanie dla podtablicy o indeksach od l do m
  3. Wywołaj sortowanie przez scalanie dla podtablicy o indeksach od m+1 do r
  4. Połącz podtablicę l – m i m+1 – r, przyrównując przy tym ich elementy – Jeśli element lewej tablicy na aktualnej pozycji jest mniejszy od tego na prawej, wstaw go do tablicy docelowej i zwiększ indeks lewej tablicy. W przeciwnym przypadku, wykonaj analogiczne działanie dla prawej tablicy.

Przykład

Aby lepiej zwizualizować sobie zasadę działania algorytmu, prześledźmy prosty przykład. Weźmy zbiór { 4, 2, 8, 6, 5, 1 }. W pierwszej kolejności wyznaczamy indeksy l,r i m:

l = 0
r = 5
m = 2

Następnie dzielimy zbiór wejściowy na dwie podtablice:

L = { 4, 2, 8 }  P = { 6, 5, 1 }

Ponownie wykonujemy kolejne podziały lewej podtablicy, do momentu otrzymania następujących zbiorów:

L = ({ 4 }, { 2 }, { 8 }) P = { 6, 5, 1 }

Łączymy elementy lewej części podzbiorów, ustawiając je w porządku rosnącym:

L = { 2,4,8 } P = { 6, 5, 1 }

Wykonujemy podział dla prawej podtablicy:

L = { 2,4,8 } P = ({ 6 }, { 5 }, { 1 })

Łączymy elementy prawej części podtablicy:

L = { 2,4,8 } P = { 1, 5, 6 }

Łączymy obie podtablice:

{1, 2, 4, 5, 6, 8}

W taki sposób otrzymujemy posortowany zbiór wejściowy. By w pełni zrozumieć zasadę działania algorytmu, spójrzcie na poniższą animację:G

Sortowanie przez scalanie – implementacja w C++

Nieco teorii

Algorytm sortowania, został odkryty przez legendarnego matematyka i informatyka Johna von Neumanna. Jego złożoność czasowa ma wartość O(nlog(n)), co jest bardzo dobrym wynikiem. Jest on bardzo popularny w przypadku sortowania wszelkiego rodzaju list. Możliwe, że wiele z was wykorzystywało go, bez świadomości o jego istnieniu. Jest wykorzystywany m.in. w funkcji Collections.sort() w jęzuku Java.

Podsumowanie

Właśnie wspólnie poznaliśmy zasadę działania sortowania przez scalanie. Znajomość tego popularnego algorytmu, z pewnością przyda Wam się w zrozumieniu wielu funkcji sortowania.

grupa wsparcia matura z informatyki

Ku mojej wielkiej przykrości, muszę ogłosić koniec serii „Piątku z sortowaniem”. Nie oznacza to jednak końca pojawiania się materiałów na binarnie.pl! Szykujemy dla Was wiele ciekawych wpisów, które już niedługo ujrzą światło dzienne. Trzymajcie się i do zobaczenia już niedługo!

You Might Also Like
Dodaj komentarz