# QSort

Rekurencyjny QuickSort

  PROCEDURE Quicksort(tablica, l, r)
    IF l < r THEN { jeśli fragment dłuższy niż 1 element }
        i := PodzielTablice(tablica, l, r); { podziel i zapamiętaj punkt podziału }
        Quicksort(tablica, l, i-1);         { posortuj lewą część }
        Quicksort(tablica, i+1, r);         { posortuj prawą część }

Iteracyjny QuickSort. Zamiast wywołań rekurencyjnych spamiętujemy dane na stosie.

  PROCEDURE Quicksort(tablica, l, r)
    Stos.Dodaj(l,r)
    WHILE l < n-1
        IF l < r THEN { jeśli fragment dłuższy niż 1 element }
            l,r := Stos.Zdejmij()
            i := PodzielTablice(tablica, l, r); { podziel i zapamiętaj punkt podziału }
            Stos.Dodaj(i+1,r)
            Stos.Dodaj(l,i-1)

Iteracyjny QuickSort w stałej dodatkowej pamięci. Zamiast pamiętać granice przedziału na stosie, zaznaczamy je odpowiednimi wartownikami - pivotami.

  PROCEDURE Quicksort(tablica, l, r)
  
    { pierwsza iteracja jest inna }
    posortowane := 0
    i := PodzielTablice(tablica, l, r) 
    Zamień(l,i) { postaw wartownika }
    
    { główna pętla }
    WHILE posortowane < n-1
        
        { zamiast zdejmowania ze stosu }
        l := posortowane
        r := Pierwszy element i, t.ż. l <= i oraz A[i-1] <= A[l] <= A[i+1] { w i był pivot, którego przestawiliśmy }
        Zamień(l,r) { cofnij "stawianie wartownika" }
        --r
        
        IF l < r THEN { jeśli fragment dłuższy niż 1 element }            
            i := PodzielTablice(tablica, l, r); { podziel i zapamiętaj punkt podziału }
            
            { zamiast wrzucania na stos }
            Zamień(i,r) { postaw wartownika }
            
        ELSE { fragment długości 0 lub 1 }
            posortowane++