Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

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 {tex}n\cdot log\ n{/tex}, 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.

 scalanie 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 {tex}n log n{/tex} 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:

sortowanie przez scalanie

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