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

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:

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:

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:

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):

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:

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

, , , , , , , , ,

  • Ten iteracyjny bez stosu jest błędny. Jest niesamowicie złożony czasowo, ale co ważniejsze sypie mnóstwo minusów w posortowanych liczbach.

    • Jak go testowałem to dobrze działał, sprawdzę jeszcze raz (być może trzeba tam wartość bezwzględną brać). Co do złożoności to wiadomo, że jest większa od pierwotnej wersji, tutaj chodziło o to, żeby usunąć rekurencję.

      PS: A do testów brałeś liczby większe lub równe 0?

      • Wpadłem już na to :) Reszta jest ok już. Partition tylko trochę mało optymalne, ale to najmniej ważne akurat, bo można wymienić na inne i dodatkowo też brać środkowy pivot (zamienić z pierwszym elementem najpierw). Wtedy hula szybko.

        • Dokładnie, Partition jest uniwersalne, ja na potrzeby tego artykułu wziąłem Lomuto ;)