Niedokładne sortowanie quicksort

pytanie zadane 29 maja 2015 w Algorytmy przez Kororo3 Nowicjusz (150 p.)

Bardzo proszę o pomoc z poniższym kodem. Niestety sortowanie przebiega niedokładnie, a więc to żadne sortowanie :) ale niestety nie mogę zlokalizować gdzie robię błąd.

void quicksort(int tab[],int poczatek, int koniec){
int punkt_podzialu = (poczatek+koniec)/2;
if(poczatek<koniec){
podzial(tab,poczatek,koniec,punkt_podzialu);
quicksort(tab,poczatek,punkt_podzialu-1);
quicksort(tab,punkt_podzialu+1,koniec);
}
return;
}

void podzial (int tab[], int poczatek,int koniec, int punkt_podzialu)
{
    int i = poczatek;
    int j = koniec;
    int v = tab[poczatek];
    int temp;

    do {
        while (tab[i] <= v)
            i++;
        while (v <= tab[j])
            j--;
        if ( i <= j )
        {
            temp = tab[i];
            tab[i] = tab[j];
            tab[j] = temp;
            i++;
            j--;
        }
    } while (i <= j);

    return;
}

1 odpowiedź

odpowiedź 29 maja 2015 przez iwan9449 Pasjonat (20,810 p.)
wybrane 30 maja 2015 przez Kororo3

Najlepsza

Błędy są co najmniej w kilku miejscach :) Przeanalizuj ten kod:

int podzial (int tab[], int poczatek,int koniec)
{
    int i = poczatek;
    int j = koniec;
    int v = tab[poczatek];
    int temp;

    do
    {
        while (tab[i] < v)
            i++;
        while (v < tab[j])
            j--;
        if ( i < j )
        {
            temp = tab[i];
            tab[i] = tab[j];
            tab[j] = temp;
            i++;
            j--;
        }
    }
    while (i < j);

    return j;
}

void quicksort(int tab[],int poczatek, int koniec)
{
    int q;
    if(poczatek<koniec)
    {
        q = podzial(tab,poczatek,koniec);
        quicksort(tab,poczatek,q);
        quicksort(tab,q+1,koniec);
    }
    return;
}