[C++] Sortowanie szybkie

pytanie zadane 9 kwietnia 2015 w Algorytmy przez 1110200039910 Gaduła (4,630 p.)

Witam, proszę Was o uzupełnienie algorytmu sortowania szybkiego o komentarze. Chodzi o to że nie do końca rozumiem działanie samej funkcji.

Wiem że algorytm dzieli tablice na dwie partycje, nastepnie zaczyna dzielić te partycje na kolejne metodą "Dziel i zwyciężaj" jednak nie rozumiem np. tej części kodu, wiem że zapętla on działanie funkcji (rekurencja) partycjując coraz mniejsze zbiory, ale dlaczego np. dane wprowadzane do funkcji 'Sortowanie' są różne od siebie

if (q>lewy) Sortowanie(tablica,lewy,q);         
if (p<prawy) Sortowanie(tablica,p,prawy);

tzn. występuje (tablica,lewy,q), a dlaczego niżej nie ma (tablica,prawy,p) tylko (tablica,p,prawy).

Proszę o pomoc, najlepiej by było gdyby ktoś uzupełnił algorytm o odpowiednie komentarze. Oto kod:

void Sortowanie(int *tablica, int lewy, int prawy)
{
    int v=tablica[(lewy+prawy)/2]; 
    p=lewy;
    q=prawy;
    do
    {
        while (tablica[p]<v) p++;                  
        while (tablica[q]>v) q--;
        if (p<=q)
        {
            swap (tablica[p],tablica[q]);
            p++;
            q--;
        }
    }   while (p<=q);
    if (q>lewy) Sortowanie(tablica,lewy,q);         
    if (p<prawy) Sortowanie(tablica,p,prawy);
}

2 odpowiedzi

odpowiedź 9 kwietnia 2015 przez bossik21 Mądrala (5,750 p.)
edycja 9 kwietnia 2015 przez bossik21

Najlepsza

void Sortowanie(int *tablica, int lewy, int prawy)
{
    int v=tablica[(lewy+prawy)/2]; 
    p=lewy;
    q=prawy;
    do
    {
        while (tablica[p]<v) p++; //Wyszukujemy od Lewej strony tablicy element wiekszy od piwota               
        while (tablica[q]>v) q--; // Wyszukujemy od prawej strony tablicy element mniejszy od piwota
        if (p<=q)
        {
            swap (tablica[p],tablica[q]);
            //Zamieniamy elementy tak aby wiekszy od piwota podszedl na prawa strone
            // a mniejszy od piwota poszedl na lewa
            p++; 
            q--;
        }
    }   while (p<=q);
    if (q>lewy) Sortowanie(tablica,lewy,q);         
    if (p<prawy) Sortowanie(tablica,p,prawy);
}

Dlaczego jest to :


if (q>lewy) Sortowanie(tablica,lewy,q);        

if (p<prawy) Sortowanie(tablica,p,prawy);

Dlatego, że gdy posortujesz już tablicę względem piwota, że po lewo od piwota będziesz miał elementy mniejse, a po prawej elementy większe, to następnie musisz posortować te nowe "mniejsze części tablicy" i dlatego wykonujesz potem sortowanie oddzielnie lewej części tablicy i prawej części tablicy.

PS. Możesz mi powiedzieć jak wstawiać kod tak ładnie poformatowany?

komentarz 9 kwietnia 2015 przez 1110200039910 Gaduła (4,630 p.)

Jak piszesz post to u góry masz te znaczki, klikasz znaczek z widocznym symbolem [...]CODE i tam wybierasz jezyk oraz wpisujesz tresc

komentarz 9 kwietnia 2015 przez bossik21 Mądrala (5,750 p.)

Dzięki, zaraz porawię post :)

odpowiedź 9 kwietnia 2015 przez 0x8b Obywatel (1,430 p.)

Witam.

Tutaj jest wszystko pięknie opisane: http://edu.i-lo.tarnow.pl/inf/alg/003_sort/0018.php

komentarz 9 kwietnia 2015 przez 1110200039910 Gaduła (4,630 p.)

Jak wspominałem, sam algorytm jest dla mnie zrozumiały, przeczytałem cały artykuł który podesłałeś przed zadaniem pytania.Mimo wszystko funkcja napisana wyżej w C++ to dla mnie magia.