SZYBKIE SORTOWANIE --QUICKSORT--

CO trzeba umieć:

-- TABLICE 

//////////////////////////////////////////////////////////////////
 

Szybkie sortowanie (Quicksort) polega na tym, że znajdujemy element graniczny i dzieli naszą tablicę na dwie części następnie przenosimy element tak, aby po jednej stronie były elementy nie większe od tego elementu, a po drugiej nie mniejsze od tego elementu. Następnie sortujemy dwie tablice oddzielnie. W tym miejscu, aż prosi się o rekurencję. Więc wykonujemy ponownie naszą funkcję dla jednej części tablicy i drugiej. Rekurencje tak wykonujemy, aż otrzymamy tablicę jednoelementową (po podziałach), bo jednego elementu nie się nie sortuje. Dzięki zastosowaniu takiej sztuczki możemy naprawdę szybko posortować naszą tablicę.

Przykład: 

 

tablica [2,5,1,6,3,9,4,8,7,0], sortujemy rosnąco

Na początku wybieramy element graniczny ustalmy go dowolnie (np.: jako środkowy element)

[2,5,1,6,3,9,4,8,7,0]

I teraz trzeba zamieniać elementy miejscami i tu ruszamy się dwoma wskaźnikami jednym idziemy od końca, a drugim od początku. Najpierw ten od początku 2 jest mniejsze od 3 (nasz element graniczny), czyli jest dobrze, więc przesuwamy wskaźnik o jeden dalej. 5 jest większe od 3 więc stop. Teraz bierzemy w obrotny nasz wskaźnik drugi i idziemy od tyłu. 0 mniejsze od 3 więc stop.

[2,5,1,6,3,9,4,8,7,0]

Teraz musimy zamienić miejscami elementy, na których stanęły wskaźniki i przestawiamy o jeden (ten który szedł od początku dajemy o jeden do przodu, a ten który szedł od końca dajmy o jeden do tyłu).

[2,0,1,6,3,9,4,8,7,5]

Następnie dalej dokonujemy zamian naszych elementów. 1 jest mniejsze od 3 dobrze, więc dalej, 6 większe od 3, stop. Teraz przestawiamy drugi wskaźnik. 7 większe od 3, przestawiamy. 8,4,9 również jest większe od 3. Dalej mamy 3. No 3 nie jest większe od 3 więc stop. 

 

[2,0,1,6,3,9,4,8,7,5]

Zamieniamy miejscami i przestawiamy wskaźniki tak sama jak wcześniej, ale możemy zauważyć, że nasze wskaźniki się minęły. Oznacza to, że już poprzerzucaliśmy nasze elementy i możemy podzielić naszą tablicę za pomocą naszego wskaźnika który szedł od końca.

[2,0,1,3,6,9,4,8,7,5]

nasze nowe dwie tablice:

[2,0,1,3] [6,9,4,8,7,5]

Teraz sortujemy osobno lewą podtablicę, a potem prawą podtablicę.

Najpierw lewa, wybieramy element graniczny, oczywiście tak samo.

[2,0,1,3]

Najpierw pierwszy wskaźnik 2 jest większe od 0, stop. Teraz drugi wskaźnik. 3 i 1 są większe od 0. 0 oczywiście nie jest większe od 0, więc stop.

[2,0,1,3]

Zamieniamy miejscami i przestawiamy wskaźniki.

[0,2,1,3]

Nasze wskaźniki się minęły, więc dzieli tablicę na dwie za pomocą wskaźnika, który szedł od tyłu.

[0] [2,1,3]

Znowu wykonujemy naszą funkcję najpierw dla lewej części a potem dla prawej.

[0]

Lewa podtablica zawiera jeden element, więc kończymy. Teraz bierzemy prawą część i ustalamy element graniczny. 

 

[2,1,3]

Ponownie robimy tak samo, najpierw wskaźnik początkowy. 2 jest większe od 1, stop. Następnie wskaźnik końcowy. 3 jest większe od 1, więc idziemy dalej 1 nie jest większe od 3, więc stop.

[2,1,3]

Zamieniamy elementy miejscami i oczywiście przestawiamy wskaźniki.

[1,2,3]

Nasze wskaźniki się minęły, więc możemy podzielić naszą tablicę.

[1] [2,3]

Ponownie wywołujemy naszą funkcję dla lewej części, a potem dla prawej.

[1]

Tablica zawiera jeden element, koniec. Bierzemy prawą cześć i ustalamy element graniczny.

[2,3]

Ponownie bawimy się wskaźnikami. Początkowy zatrzyma się oczywiście na elemencie 2, wskaźnik końcowy również zatrzyma się na elemencie dwa.

[2,3]

Oczywiście nie dokonujemy zamiany, bo byłoby to bez sensu, ale nasze wskaźniki się zrównały, więc możemy znowu podzielić naszą tablicę.

[2] [3]

Wywołujemy znowu funkcje dla lewej i prawej części. Obie części zawierają pojedyncze elementy, więc koniec.

Teraz podsumujmy nasze sortowanie lewej części.

[0] [1] [2] [3]

Czyli lewą cześć naszej głównej tablicy posortowaliśmy prawidłowo. Teraz wracamy do naszej prawej części.

[6,9,4,8,7,5]

Teraz tą tablicę sortujemy dokładnie tak samo jak poprzednia część. Teraz użyję mojej tajemnej mocy przewidywania przyszłość i powiem, że otrzymamy:

[4] [5] [6] [7] [8] [9]

A po połączeniu naszych dwóch posortowanych tablicy otrzymamy posortowaną tablicę wejściową:

[0,1,2,3,4,5,6,7,8,9]

Jakbyś mi nie uwierzył to gorąco zachęcam to rozpisania sobie tej części tablicy na kartce, tak samo jak ja zrobiłem to z lewą stroną. A ja ze swojej strony powiem tylko tyle, że jestem leniwy i mi się nie chciało :P.

No więc, tak właśnie wygląda idea Quicksort'a. Jak widać nie jest to wcale takie trudne. Wystarczy wybrać sobie element graniczny (całkowicie dowolny), a następnie poprzerzucać elementy, podzielić tablicę i znowu posortować. Tutaj taka mała uwagą, bo może nie jest to do końca jasne. Nie tworzymy dodatkowych tablicy, cały czas działamy na jednej tylko podajemy element początkowy tablicy i element końcowy tablicy( lub odpowiedniej części tej tablicy).

Złożoność tego sortowania jest O[n log(n)], czyli już całkiem przyzwoita, a na pewno dużo lepsza od pierwszego sortowania.

KOD:

(WERSJA I) (TABLICE) // sortowanie malejące

void qsort(int tab[], int l, int r){

// funkcja za argumenty przyjmuje tablice oraz indeks początkowy i końcowy

    int i = l,j = r,x = tab[( l + r ) / 2 ], temp;

    // zmienne pomocnicze i-indeks początkowy, j-indeks końcowy,
  // x- elemetn graniczny 

 

   do{

        while( tab[ i ] > x )i++; // pętla szuka elementu to większego od x

        while( tab[ j ] < x )j--; // szuka elementu mniejszego do x

        // gdy funkcje znalazły odpowiednie elementy do zamiany

 

    if( i <= j ){ // zamiana

               temp=tab[i];

               tab[i]=tab[j];

               tab[j]=temp;

               i++; // wskaźnik początkowy o 1 do przodu

               j--; // wskaźnik końcowy o jedne do tyłu

        }

     } while( i <= j ); // pętla wykonuje się, aż nasze wskaźnik się nie miną

     if( l < j ) qsort( tab, l, j ); // wywołanie funkcji dla lewej części

     if( r > i ) qsort( tab, i, r ); // wywołanie funkcji dla prawej części

}

Sam kod jest dość prosty. Mamy główną pętlę do – while, w której są jeszcze dwie pętle while. Mają one za zadanie znalezienie elementów do zamiany. Gdy znajdą element i te element spełniają nasze warunki to dokonujemy zamiany i powtarzamy pętlę do – while, aż nasze wskaźniki się nie miną, co będzie oznaczać, że poprzerzucaliśmy wszystkie elementy zgodnie z algorytmem. Następnie wywołujemy funkcję dla lewej części, a potem dla prawej.

Pierwsze wywołanie funkcji gdy chcemy posortować całą tablicę wygląda tak : qsort(tab,0,rozmiar_tablicy-1). Ponieważ funkcja qsort chce od nasz 3 argumenty. Pierwszym jest nasza tablica, pozostałymi kolejno lewy koniec i prawy koniec tablicy do posortowania. Możemy zaobserwować, że tą samą funkcją możemy sortować tylko fragment naszej tablicy, a nie zawsze cała. Dzięki temu możemy przyspieszyć nasz algorytm, który będzie pracował na jakimś fragmencie danych.

KOD:

(I Wersja)(LISTY) // sortowanie malejące

void qsortlist(struct list *head,int l, int r){

// funkcja ma za zadnie posortować listę,
// struktura listy jest taka sama jak ostatnio

     

   struct list *i=head; // wskaźnik początkowy

      struct list *j=head; // wskaźnik końcowy

      struct list *x=head; // element graniczny

   int temp; // zmienna pomocnicza

      int k=0,p1=l,p2=r; // zmienne pomocnicze

    // ustawianie prawidłowo wskaźników na początku

    for(k=0;k<l;k++)i=i->next;

    for(k=0;k<r;k++)j=j->next;

    for(k=0;k<(l+r)/2;k++)x=x->next;

    //

    // Dalsza część nie różni się już od wersji która sortuje tablicę

    do{

        while(i->key > x->key){ // wskaźnik początkowy

            i=i->next;

            p1++;

       }

       while(j->key < x->key){ // wskaźnik końcowy

           j=j->prev;

           p2--;

       }

       if(p1<= p2){ // zamiana

           temp=i->key;

           i->key=j->key;

           j->key=temp;

           i=i->next;

           p1++;

           j=j->prev;

           p2--;

      }

    }while(p1<=p2); // gdy nasze wskaźniki się miną to koniec

    // wywołanie funkcji dla podzielonej listy

   if(l<p2)qsortlist(head,l,p2);

   if(r>p1)qsortlist(head,p1,r);

   //

}

Jak widzimy sortowanie listy nie wiele różni się od sortowania tablicy, a sama idea jest taka sama. Różni się tylko sposób operowania listą od operowania tablicą. W tablicy łatwiej jest znaleźć element o podanym indeksie, a tutaj musieliśmy do tego wykorzystać pętlę for. Dalsza część kodu jest praktycznie nie zmieniona.

KOD:

(Wersja II) (tablica)

int partition(int tablica[],int p,int r){

// Pierwsza funkcja przyjmuje 3 argumenty, tablicę, początek, koniec

// Ma za zadanie poprzerzucać argumenty i zwrócić indeks podziału

    int x=tablica[(p+r)/2], i =p,j=r,w; // zmienne pomocnicze

    while(1){ // pętla nieskończona

        while(tablica[j] > x) j--; // przechodzenie lewym wskaźnikiem

        while(tablica[i] < x) i++; // przechodzenie prawym wskaźnikiem

        if(i<j){ // zamiana

              w=tablica[i];

              tablica[i]=tablica[j];

              tablica[j]=w;

              i++;

              j--;

        }else return j;
// jeśli nie dokonano zamiany, to nasze wskaźniki
// się przecięły, więc możemy podzielić naszą
// tablicę za pomocą indeksu prawego.
// Kończymy pętlę i wychodzimy z funkcji

     }

}

void quicksort(int tablica[],int p,int r){

// Druga funkcja przyjmuje 3 argumenty, tablicę, początek, koniec

     int q,i; // zmienne pomocnicze

     if(p<r){ // gdy w tablicy jest więcej niż 1 element

           q=partition(tablica,p,r); // wywołanie pierwszej funkcji

           quicksort(tablica,p,q); // sortowanie lewej części

           quicksort(tablica,q+1,r); // sortowanie prawej części

      }

}

Jak widzimy ten kod jest bardzo podobny do tego wyżej (I wersja). Omawiam go dlatego, że często qsort'a spotyka się właśnie w takiej postaci, a nie chciałbym, abyś przeżył szok widząc coś dziwnego :). Pierwsza funkcja szuka nam elementu, na którym będzie podział i przerzuca nam nasze elementy. Druga funkcja wykorzystując element podział, który zwróciła pierwsza funkcja wywołuje sortowanie dla lewej części i prawej części tej tablicy.