QuickSort jest jednym z najczęściej używanych algorytmów
sortowania. Według wielu źródeł jest to najszybszy sposób
sortowania dla losowych wybranych danych.
Jego konstrukcja jest oparta na zasadzie "dziel i zwyciężaj"
lub inaczej "dziel i rządź". Tablica do posortowania zostaje
w specjalny sposób podzielona na dwie części, po czym obie
części są sortowane niezależnie.
Poważnymi wadami tego rozwiązania jest jego koszt O(n2)
i niestabilność. Wadą też jest rekursja tłumaczona na operacje
na stosie. W Quicksorcie złożoność pamięciowa związana jest
z koniecznością implementacji stosu.
Zauważono, że oba wywołania rekurencyjne w procedurze quicksort
są niezależne, tak, więc mogą być wywołane w dowolnej kolejności.
Ponieważ wywołania te znajdują się na końcu jedno z nich może być
zastąpione interacją a na stosie zamiast miejsc powrotu z wywołań
rekurencujnych można przechowywać tylko parametry wywołania,
które ma być wykonanejako następne.
Po wprowadzeniu tych zmian powstał algorytm
"Quicksort z małym stosem". Polega on na tym, że na stosie będą
znajdować się pary indeksów [i, j] ( końce nieposortowanego ciągu)
określające parametry wywołania algorytmu QuickSort, które trzeba
jeszcze wykonać.
Przy realizacji wywołania quicksort(l, r) (gdzie l to indeks
pierwszego a r ostatniego elementu podciągu) z dwóch wywołań
rekurencyjnych będziemy umieszczać na stosie większy z podciągów
otrzymanych w wyniku podziału (a ściślej jego końce) pozostawiając
mniejszy do przetwarzania w kolejnej iteracji.
Podciągi te nazywają się podciągami bratnimi. Niech s1,s2,...,sk
będą długościami podciągów na stosie a i1,i2,...,ik rozmiarami ich
bratnich podciągów. Przyjmijmy i0 = n. Zauważmy, że podciąg
o długości ij, gdzie j < k został podzielony na dwa podciągi:
jeden o długości sj+i umieszczony na stosie i drugi
o długości ij+1 przetwarzany w kolejnej interacji jest równy
ij = (sj+1) + (ij+1) +1 oraz że sj+1 ł ij+1.
Zachodzi wówczas:
a) ;
b) .
Stosując indukcje, łatwo można pokazać, że

dla 1Ł j Ł k
co dowodzi, że maksymalna głębokość stosu jest ograniczona przez
log n. Mamy zatem S(n) = O(log n) jest to dużo mniej niż w przypadku
algorytmu QuickSort z użyciem rekursji.


void QuickSortMalyStos(long *a, int n)
{
#define MAX_STOS 100

/* Zainicjowanie struktury służącej jako stos gdzie
"c" - to indeks pierwszego a "d" - ostatniego elementu
w nieposortowanym ciągu */
struct para {int c, d;} St[MAX_STOS];
int ile_na_stosie = 0;

int i, j, l, r;
long v, x;
// sprawdza czy ilość elementów w tablicy jest większa od jednego
if(n>1)
{

/* na elementy st[0].x przypisuje wartości ostatniego i pierwszego
indeksu ciągu wejściowego */
St[0].c = 0; St[0].d = n-1;

ile_na_stosie = 1;

do
{
/* zdejmuje ze stosu indeksy pierwszego i ostatniego elementu,
kolejnego nieposortowany podciągu */

ile_na_stosie--;
l = St[ile_na_stosie].c;
// l to indeks pierwszego elementu danego podciągu

r = St[ile_na_stosie].d;
// l to indeks ostatniego elementu danego podciągu

/* początek partrition */
while(l{
v = a[l]; // przypisanie na "v" pierwszego elementu w danym podciągu
i = l;
j = r+1;

do
{
do
i++;

/* przeszukuje tablice do momentu, gdy znajdzie pierwszy
element nie mniejszy od a[l] */
while((i<=r) && (a[i] do

/* przeszukuje tablice do momentu, gdy znajdzie pierwszy
element nie większy od a[l] */
j--;
while(a[j]>v);

/* jeżeli poniższy warunek jest spełniony to zamieni miejscami
elementy na które wskazują "i" i "j" */
if(i {
x =a[i];
a[i] = a[j];
a[j] = x;
}

}

/* jeżeli poniższy warunek jest spełniony to zamieni miejscami
elementy pierwszy w danym podciągu
z elementem na o indeksie "j" */
while(i a[l] = a[j];
a[j] = v;


/* sprawdza który z bratnich podciągów jest dłuższy i jego końce
wpisuje na stos a mniejszy pozostawia
do przetworzenia w kolejnej iteracji. */
if((j-l) < (r-j))
{
St[ile_na_stosie].c = j+1;
St[ile_na_stosie].d = r;
ile_na_stosie++;
r = j-1;
}
else
{
St[ile_na_stosie].c = l;
St[ile_na_stosie].d = j-1;
ile_na_stosie++;
l = j+1;
}
}
}
while(ile_na_stosie>0);
}
}