ALG8

88 Rozdział 4. Algorytmy sortowania

Jest chyba dość oczywiste, że wywołania rekurencyjne zatrzymają się w mo-li mencie, gdy rozmiar fragmentu tablicy wynosi / - nic ma już bowiem czegoI sortować.

Przedstawiona powyżej metoda sortowania charakteryzuje się olbrzymią prostotą, I wyrażoną najdoskonalej przez zwięzły zapis samej procedury:

void OuicksorL(int *Ldb,int left, int right)

I

if (left < right)

(

int m;

// Podziel tablicę względem elementu osiowego:

// P=pierwszy element, czyli t3b[left];

II Pod koniec podziału element 'P' zostanie II przeniesiony do komórki numer 'm';

Quicksort(tab,left,m-l) ;

Ouicksort(tab,m+l,right) ;

)

)

Jak najprościej zrealizować fragment procedury sprytnie ukryty za komentarzem? Jego działanie jest przecież najistotniejszą częścią algorytmu, a my jak dotąd traktowaliśmy go dość ogólnikowo. Takie postępowanie wynikało z dość prozaicznej przyczyny: Quicksort-ow jest mnóstwo i różnią się one właśnie realizacją procedury podziału tablicy względem wartości „osi”.

Oszczędzając Czytelnikowi dylematów dotyczących wyboru „właściwej” wersji zaprezentujemy poniżej - zgodnie z prawdziwymi zasadami współczesnej demokracji - tę najwłaściwszą...

Kryteriami wyboru były: piękno, szybkość i prostota - tych cech można niewątpliwie doszukać się w rozwiązaniu przedstawionym w [Ben92],

Pomysł opiera się na zachowaniu dość prostego niezmiennika w aktualnie „rozdzielanym” fragmencie tablicy (patrz rysunek 4 - 7).

l^J

<F

Fragment niezbadany

left    m    i    right

Rys. 4 - 7.

Budowa niezmiennika dla algorytmu Quicksort.

Oznaczenia:

•    left lewy skrajny indeks aktualnego fragmentu tablicy;

•    right prawy skrajny indeks aktualnego fragmentu tablicy;