Sortowanie przez scalanie należy do algorytmów, które wykorzystują metodę "dziel i zwyciężaj". Złożoność algorytmu wynosi $$n\cdot log\ n$$, a więc jest on znacznie wydajniejszy niż sortowanie bąbelkowe, przez wstawianie czy przez selekcję, gdzie złożoność jest kwadratowa. Żeby zrozumieć zasadę działania przyjrzyjmy się najpierw dwóm posortowanym tablicom:
tablica 1: 2 3 7 9 10
tablica 2: 1 3 4 8 11
Zauważmy, że możemy liniowo scalić te dwa ciągi liczb i uzyskać jedną posortowaną tablicę postępując ze schematem:
- ustawiamy liczniki na początki tablic posortowanych,
- następnie porównujemy elementy i mniejszy lub równy element wskakuje jako pierwszy w scalonej tablicy,
- zwiększamy licznik w tej tablicy, z której "zabraliśmy element",
- czynność powtarzamy aż do wyczerpania danych z obu tablic.
A więc najpierw musimy doprowadzić do sytuacji, gdzie będziemy mieli dwie posortowane tablice. Dzielimy nasz zbiór liczb na dwie części, następnie każdą z nich także dzielimy na dwie części, czynność powtarzamy do momentu otrzymania podtablic jednoelementowych (wykonujemy to rekurencyjnie). Ponieważ zbiór jednoelementowy jest już posortowany możemy przejść do scalania. W ten sposób powstają nam coraz to większe posortowane zbiory, aż w rezultacie otrzymamy oczekiwany efekt - ciąg posortowanych elementów.
Zalety algorytmu
- prostota implementacji
- wydajność
- stabilność
- algorytm sortuje zbiór n-elementowy w czasie proporcjonalnym do liczby $$n log n$$ bez względu na rodzaj danych wejściowych
Wady algorytmu
- podczas scalania potrzebny jest dodatkowy obszar pamięci przechowujący kopie podtablic do scalenia
Schemat:
Implementacja algorytmu przez scalanie:
//www.algorytm.edu.pl
#include<iostream>
#include<cstdlib>
using namespace std;
int *pom; //tablica pomocnicza, potrzebna przy scalaniu
//scalenie posortowanych podtablic
void scal(int tab[], int lewy, int srodek, int prawy)
{
int i = lewy, j = srodek + 1;
//kopiujemy lewą i prawą część tablicy do tablicy pomocniczej
for(int i = lewy;i<=prawy; i++)
pom[i] = tab[i];
//scalenie dwóch podtablic pomocniczych i zapisanie ich
//we własciwej tablicy
for(int k=lewy;k<=prawy;k++)
if(i<=srodek)
if(j <= prawy)
if(pom[j]<pom[i])
tab[k] = pom[j++];
else
tab[k] = pom[i++];
else
tab[k] = pom[i++];
else
tab[k] = pom[j++];
}
void sortowanie_przez_scalanie(int tab[],int lewy, int prawy)
{
//gdy mamy jeden element, to jest on już posortowany
if(prawy<=lewy) return;
//znajdujemy srodek podtablicy
int srodek = (prawy+lewy)/2;
//dzielimy tablice na częsć lewą i prawa
sortowanie_przez_scalanie(tab, lewy, srodek);
sortowanie_przez_scalanie(tab, srodek+1, prawy);
//scalamy dwie już posortowane tablice
scal(tab, lewy, srodek, prawy);
}
int main()
{
int *tab,
n; //liczba elementów tablicy
cin>>n;
tab = new int[n]; //przydzielenie pamięci na tablicę liczb
pom = new int[n]; //przydzielenie pamięci na tablicę pomocniczą
//wczytanie elementów tablicy
for(int i=0;i<n;i++)
cin>>tab[i];
//sortowanie wczytanej tablicy
sortowanie_przez_scalanie(tab,0,n-1);
//wypisanie wyników
for(int i=0;i<n;i++)
cout<<tab[i]<<" ";
system("pause");
return 0;
}
|
Nieco szybsza wersja funkcji scalającej:
//scalenie posortowanych podtablic
void scal(int tab[], int lewy, int srodek, int prawy)
{
int i, j;
//zapisujemy lewą częsć podtablicy w tablicy pomocniczej
for(i = srodek + 1; i>lewy; i--)
pom[i-1] = tab[i-1];
//zapisujemy prawą częsć podtablicy w tablicy pomocniczej
for(j = srodek; j<prawy; j++)
pom[prawy+srodek-j] = tab[j+1];
//scalenie dwóch podtablic pomocniczych i zapisanie ich
//we własciwej tablicy
for(int k=lewy;k<=prawy;k++)
if(pom[j]<pom[i])
tab[k] = pom[j--];
else
tab[k] = pom[i++];
}
|