Przerabiamy algorytm QuickSort z wersji rekurencyjnej na nierekurencyjną

Algorytm szybkiego sortowania znany jako QuickSort to jeden z najciekawszych i zarazem doskonale znanych algorytmów sortowania danych. Charakteryzuje się on stosunkowo szybkim działaniem i prostą implementacją. Cała idea jego działania została oparta o zasadę „dziel i zwyciężaj”, a sam algorytm charakteryzuje się średnią złożonością rzędu O(n log n).

Autor: geralt | Public Domain CC0

Zasada działania algorytmu QS została znakomicie zaprezentowana poprzez elementy tańca na jednym z filmików dostępnych w serwisie YouTube:

Podstawowa rekurencyjna wersja algorytmu QuickSort w języku Java oparta o funkcję Partition autorstwa Lomuto prezentuje się tak:

static void QuickSort(int left, int right) {
     if (right <= left)
        return;
     else {
        int q = Partition(left, right);
        QuickSort(left, q - 1);
        QuickSort(q + 1, right);
     }
}

static int Partition(int left, int right) {
    long x = tab[left];
    int i=left;

    for(int j=left+1;j<=right;j++)
        if(tab[j] <= x ) {
            i = i+1;
            swap(i, j);
        }
    swap(i, left);
    return i;
}

static void swap(int i, int j) {
    int tmp = tab[i];
    tab[i] = tab[j];
    tab[j] = tmp;
}

Jak widać podstawowa wersja algorytmu QS jest oparta o rekurencję. Należy jednak zwrócić uwagę iż przy sortowaniu liczb nie ujemnych (większych lub równych 0) można przerobić powyższy algorytm (funkcję QuickSort) tak aby nie zawierała rekurencji ani nie korzystała ze stosu. Oczywiście algorytm ten będzie w dalszym ciągu działał na przykład z innymi wersjami funkcji Partition. My skupimy się tylko i wyłącznie na modyfikacji głównej funkcji całego algorytmu.

Zanim jednak dojdziemy do nierekurencyjnej wersji QuickSort nie opierającej się o stos, spróbujmy pozbyć się rekurencji właśnie używając stosu.

Zaczniemy od tego, żeby zamiast każdego wywołania rekurencyjnego odkładać na stos odpowiednie dane. W naszym przypadku będziemy potrzebowali zapisywać zawartość zmiennej q+1 oraz right (które obecnie przekazujemy przy wywoływaniu rekurencyjnym). Spostrzegawcze osoby zauważyły na pewno iż pominęliśmy zmienną left. Dzieje się tak dlatego, że za każdym wywołaniem rekurencyjnym zawartość tej zmiennej i tak jest wyliczana od nowa więc możemy ją opuścić. Na stos rzucamy również zawartość zmiennej q powiększoną o 1 bo i tak do zmiennej left przypisujemy q + 1 (drugie wywołanie rekurencyjne: QuickSort(q + 1, right)).

Nasza zmieniona funkcja QuickSort ze stosem będzie wyglądała tak:

QuickSort(left, right) {
     /*1*/ if (left>=right) goto3;
     q = Partition(left, right);
     stack.push(q+1,right); //metoda push() odkłada na stos dane
     right = q-1; goto 1;
     /*3*/ if (stack.stackIsEmpty())  goto 4; //metoda stackIsEmpty() sprawdza czy stos jest pusty
     [left, right] = stack.pop();  goto 1; //metoda pop() ściąga ze stosu dane
     /*4*/
}

Oczywiście w Java coś takiego nam się nie skompiluje. Raz, że nie ma czegoś takiego jak goto, dwa tej instrukcji nie powinno się nigdzie używać (nawet w językach, które to obsługują). Pora więc się jej pozbyć. Użyjemy do tego celu instrukcję while:

QuickSort(left, right) {
  while(left < right || !stack.stackIsEmpty()) { //metoda stackIsEmpty sprawdza czy stos jest pusty !stack.stackIsEmpty - stos pełny
    if(left < right) {
       q = Partition(left, right);
       stack.push(q+1, right); //metoda push() odkłada na stos dane
       right = q-1;
    }
    else { 
       [left, right] = stack.pop(); //metoda pop() ściąga ze stosu dane
    }
  }
}

W tym momencie całkowicie pozbyliśmy się rekurencji korzystając ze stosu. Możemy jeszcze ominąć odkładanie na stos wartości zmiennej left obliczając jej dane za pośrednictwem zmiennej right (left = right + 2):

QuickSort(left, right) {
  while(left < right || !stack.stackIsEmpty()) { //metoda stackIsEmpty sprawdza czy stos jest pusty !stack.stackIsEmpty - stos pełny
    if(left < right) {
       q = Partition(left, right);
       stack.push(right); //metoda push() odkłada na stos dane
       right = q-1;
    }
    else {
       left = right + 2;
       right = stack.pop(); //metoda pop() ściąga ze stosu dane
    }
  }
}

Teraz pozostało pozbyć się stosu co zmniejszy złożoność pamięciową do O(1). Oczywiście należy pamiętać, że kod ten będzie działał dla liczb nie ujemnych (większych od 0).

Po ostatnich modyfikacjach na stosie został tylko lewy indeks, który musimy jakoś zaznaczyć w naszej tablicy, którą sortujemy. Jeżeli składa się ona z liczb dodatnich to sprawa jest bardzo prosta, wystarczy tylko liczbę o indeksie left zamienić na ujemną. Teraz w naszej pętli będziemy szukać ujemnej liczby, a kiedy ją znajdziemy będziemy dalej wykonywać resztę operacji.

Nasz ostateczny kod wygląda tak:

QuickSort(int left, int right) {
        int i = 0;
        while(left < right || i > 0)
        {
            if(left < right)
            {
                int q = Partition(left, right);
                tab[right] = -tab[right];
                right = q - 1;
                i++;
            }
            else
            {
                right = left = right + 2;

                while(right < tab.length)
                    if(tab[right] < 0)
                    {
                        tab[right] = -tab[right];
                        break;
                    }
                    else
                        right++;
                i--;
            }
        }
}

Cały program wygląda tak (oczywiście działa on dla liczb nie ujemnych):

import java.util.Scanner;

public class Main {

    static Scanner s = new Scanner(System.in);
    static int[]tab = new int[8];

    public static void main(String[] args) {

        for (int i = 0; i <tab.length; i++)
           tab[i] = s.nextInt();

        for (int i = 0; i <tab.length; i++)
            System.out.println(tab[i] + " ");

        QuickSort(0,tab.length - 1);

        System.out.println("Po sortowaniu:");

        for (int i = 0; i <tab.length; i++) {
            if(tab[i] > 0)
                System.out.println(tab[i] + " ");
            else
                System.out.println(-tab[i] + " ");
        }
    }

    static void QuickSort(int left, int right) {
        int i = 0;
        while(left < right || i > 0)
        {
            if(left < right)
            {
                int q = Partition(left, right);
                tab[right] = -tab[right];
                right = q - 1;
                i++;
            }
            else
            {
                right = left = right + 2;

                while(right < tab.length)
                    if(tab[right] < 0)
                    {
                        tab[right] = -tab[right];
                        break;
                    }
                    else
                        right++;
                i--;
            }
        }
    }

    static int Partition(int left, int right) {
        long x = tab[left];
        int i=left;

        for(int j=left+1;j<=right;j++)
            if(tab[j] <= x ) {
                i = i+1;
                swap(i, j);
            }

        swap(i, left);
        return i;
    }

    static void swap(int i, int j) {
        int tmp = tab[i];
        tab[i] = tab[j];
        tab[j] = tmp;
    }
}

Algorytmy, Java, Optymalizacja QuickSort, Programowanie, QS, QuickSort, QuickSort na stosie, QuickSort nierekurencyjny, QuickSort nierekurencyjny bez stosu, Sortowanie szybkie