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

Rys. 4 - 7.

Budowa niezmiennika dla algorytmu Quicksort.

Oznaczenia:

•    left lewy skrajny indeks aktualnego fragmentu tablicy;

•    right prawy skrajny indeks aktualnego fragmentu tablicy;

Wyszukiwarka

Podobne podstrony:
ALG6 86 Rozdział 4. Algorytmy sortowania zamiany sąsiadujących ze sobą elementów, a druga będzie wy
ALG 0 90 Rozdział 4. Algorytmy sortowania 90 Rozdział 4. Algorytmy sortowania Rys. 4 - 8. Sortowanie
ALG8 198 Rozdział 7. Algorytmy przeszukiwania pod indeks ///, stwierdzimy, że już wcześniej ktoś si
65268 P3111152 KARLR.POPPER ruch, nie jest czynnościąświadomą. Jest rzeczą dość oczywistą, że ogólny
CCF20090523080 tif KARL R. POPPER ruch, nie jest czynnością świadomą. Jest rzeczą dość oczywistą że
ALG8 48 Rozdział 2. Rekurencja W celu dokładniejszego przeanalizowania algorytmu posłużymy się kilk
ALG8 68 Rozdział 3. Analiza sprawności algorytmów3.6. Nowe zadanie: uprościć obliczenia! Nic sposób
ALG8 78___Rozdział 3 Analiza sprawności algorytmówZad. 3-4 Proszę rozwiązać następujące równanie
ALG8 138 Rozdział 5. Struktury danych • „prawy” potomek /-tego węzła jest „schowany” pod indeksem 2
ALG0 190 Rozdział 7. Algorytmy przeszukiwania Odnalezienie liczby .1 w tablicy tub jest sygnalizowa
ET8 88 Rozdział 6. Popyt turystyczny współistnienia i współdziałania wielu jednostkowych usług
ALG
8 18 Rozdziali. Zanim wystartujemy dopóki a>0 wykonuj; podstaw za c resztę z dzielenia a prze
ALG 8 98 Rozdział 5. Struktury danych W następnych paragrafach zostaną przedstawione wszystkie metod
ALG8 108__Rozdział 5. Struktury danych5.1.3.Listy jednokierunkowe - teoria i rzeczywistość Oprócz p

więcej podobnych podstron