C++ - Sortowanie szybkie

W tym poście chciałbym przedstawić algorytm sortowanie szybkiego, zwanego QuickSort.

Opis działania

Jest to rekurencyjny algorytm oparty na metodzie dziel i zwyciężaj. Polega na dzieleniu całej grupy potrzebnej do posortowania na mniejsze części, które będą łatwiejsze do poukładania. Z całej tablicy wybierany jest element główny zwany osią. Jest on ustawiany losowo, nie musi to być element środkowy. Następnie względem niego przemieszczane są elementy większe, na prawą stronę, lub mniejsze, na stronę lewą, od wartości głównej. 

Wywołania rekurencyjne zakończą swoje działanie w momencie gdy rozmiar wybranego fragmentu tablicy będzie wynosił 1.

Program

Implementacja kodu w języku C++ prezentuje się następująco:

1. #include <iostream>
2. #include<cstdlib>
4. using namespace std;
6. //lewa jest to skrajny lewy indeks aktualnego fragmentu tablicy
7. //prawo jest to prawy skrajny indeks aktualnego fragmentu tablicy
8. void sortowanieszybkie(int *tablica, int lewa, int prawa)
9. {
10.     //wpisanie do zmiennej v wartości środkowej,
11.     int v=tablica[(lewa+prawa)/2];
12.     //zmienne pomocnicze
13.     int i, j, x;
14.     //wpisanie wartości skrajnej lewej do zmiennej i
15.     i=lewa;
16.     //wpisanie wartosci skrajnej lewej do zmiennej j
17.     j=prawa;
19.     do
20.     {
21.         //dopoki wartości w tablicy beda mniejsze od v
22.         while(tablica[i]<v)
23.         {
24.             i++;
25.         }
26.         //dopoki wartosci od j
27.         while(tablica[j]>v)
28.         {
29.             j--;
30.         }
31.         //jesli wartosc indeksu i jest mniejsza od indeksu j
32.         if(i<=j)
33.         {
34.             //do zmiennej x przypisywany jest nowy element tablicy
35.             x=tablica[i];
36.             //zamiana elementów
37.             tablica[i]=tablica[j];
38.             tablica[j]=x;
39.             i++;
40.             j++;
41.         }
42.     }while(i<=j);
44.     if(j>lewa)
45.     {
46.         //rekurencyjne wywołanie funkcji
47.         sortowanieszybkie(tablica,lewa,j);
48.     }
49.     if(i<prawa)
50.     {
51.         //rekurencyjne wywołanie funkcji
52.         sortowanieszybkie(tablica, i, prawa);
53.     }
54. }
56. int main()
57. {
58.     int tablica[10] = {7, 8, 2, 90, 56, 12, 67, 99, 94, 34};
59.     int i = 0;
61.     for(i = 0; i<10; i++)
62.     {
63.         cout << tablica[i] << " ,";
64.     }
65.     cout << endl;
67.     sortowanieszybkie(tablica, 0, 9);
69.     for(i = 0; i<10; i++)
70.     {
71.         cout << tablica[i] << " ,";
72.     }
73.     cout << endl;
74.     return 0;
75. }