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++]; } |