Sortowanie przez scalanie

powrót

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:

//algorytm.edu.pl
#include<iostream>
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]<<" ";
	
	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++];
}