Konrad Szczęśniak - IT Blog

Jako zadanie dodatkowe na Podstawach Programowania była możliwość zrobienia algorytmu szybkiego sortowania w wersji iteracyjnej opartej na strukturze stosu. Celem takiego zabiegu jest usunięcie wielu wywołań rekurencyjnych funkcji sortującej. Implementacja oraz zasada działania znajduje się w dalszej części artykułu.

Standardowy QuickSort w ANSI C wygląda tak:

void quicksort(int *tab, int left, int right) {int i,j;
int x;
x = tab[(left+right)/2];
i=left;
j=right;
do {
while(tab[i]<x) ++i;
while(tab[j]>x) –j;
if(i<=j) {
int tmp;
tmp = tab[i];
tab[i] = tab[j];
tab[j] = tmp;
++i;
–j;
}
} while(i<j);
if(left<j) quicksort(tab,left,j);
if(right>i) quicksort(tab,i,right);
}

Nie będę tłumaczył kodu zwykłego QuickSorta, gdyż można go znaleść chociażby na wikipedii. Jak widać w ostatnich linijkach znajdują się wywołania rekurencyjne funkcji, by je zlikwidować użyjemy prostej struktury stosu.

Zasada działania

Gdy wywołamy pierwszy raz główną funkcję programu po ciągu instrukcji ta sama funkcja wywoła siebie dwa razy i będzie dalej działała na dwóch mniejszych fragmentach tablicy, które później znowu zostaną podzielone. W tym wypadku każda z tych dwóch części jest od siebie niezależna (tzn. działając na jednej nie obchodzi nas co jest w drugiej). Idąc dalej tym tropem możemy odłożyć sobie sortowanie jednej części i pozostać w tej drugiej.

W przypadku naszego programu cały algorytm obejmiemy pętelką while, która będzie się wykonywać do czasu aż na naszym stosie zabraknie danych do obróbki. Sam element stosu będzie zawierał początkowy i końcowy indeks części która ma być później przerobiona.

Zabierzmy się zatem do realizacji stosu, użyjemy tu 3 funkcji: pop służącej do zdejmowania elementu ze stosu, push dzięki której będziemy odkładać elementy na stos i funkcji czyPusty zwracającej 0 jeśli stos jest pusty lub 1 jeśli coś znajduje się na nim.

Element stosu zdefiniujemy tak:

struct stos {
int lewyIndeks;
int prawyIndeks;
struct stos *nast;
};

Zainicjalizujemy wskaźnik globalny trzymający adres szczytowego elementu stosu

struct stos *glowa=NULL;

I zajmiemy się definicją funkcji stosowych

int czyPusty() {
if(glowa==NULL) return 0;
else return 1;
}

Oczywiście stos jest pusty tylko wtedy gdy wskaźnik glowa jest równy wartości NULL

void push(int lewy, int prawy) {
struct stos *tmp;
tmp = (struct stos *)malloc(sizeof(struct stos));
tmp->lewyIndeks=lewy;
tmp->prawyIndeks=prawy;
if(glowa==NULL) tmp->nast=NULL;
else tmp->nast=glowa;
glowa=tmp;
}

Alokujemy miejsce w pamięci na nowy element, przypisujemy mu odpowiednie wartości, a następnie wrzucamy go na stos.

void pop(int *lewy, int *prawy) {
*lewy=glowa->lewyIndeks;
*prawy=glowa->prawyIndeks;
struct stos *tmp;
tmp=glowa;
glowa=glowa->nast;
free(tmp);
}

Tutaj wysyłamy wartości szczytowego elementu stosu do zmiennych podanych w argumentach funkcji oraz usuwamy szczytowy element ze stosu.

Mający wszystkie niezbędne funkcji należy tylko zmodyfikować funkcję sortującą

void quicksort(int *tab) {
int i,j,lewy,prawy;
int x;
while(czyPusty()==1) {
pop(&lewy,&prawy);
x = tab[(lewy+prawy)/2];
i=lewy;
j=prawy;
do {
while(tab[i]<x) ++i;
while(tab[j]>x) –j;
if(i<=j) {
int tmp;
tmp = tab[i];
tab[i] = tab[j];
tab[j] = tmp;
++i;
–j;
}
} while(i<j);
if(prawy>i) push(i,prawy);
if(lewy<j) push(lewy,j);
}
}

Jak widzimy na początku pętli while zamiast pobierać wartości lewy i prawy z argumentów funkcji pobieramy je ze stosu, a na końcu tej samej pętli zamiast wywoływać rekurencyjnie funkcję z innymi parametrami to odkładamy je na stos.

Przed uruchomieniem funkcji należy odłożyć na stos krańcowe indeksy tablicy, którą chcemy posortować.