quicksort, SIGSEGV podczas najgorszego przydadku.

Poniższa implementacja quicksorta dostaje SIGSEGV podczas sortowania 90 000 elementowej tablicy elementów rosnąco-malejących (0, 1, 2, ... , 2, 1, 0) , radząc sobie bezproblemowo z wielokrotnie większymi tablicami liczb pseudolosowych. Dodam tylko, że na oś wybierany jest umyślnie zawsze element środkowy tablicy - chodzi o spreparowanie najgorszego przypadku.

 
void quick_sort(int tab[], int l, int r)
{
    int v = tab[(l+r)/2];
    int i = l;
    int j = r;
    do
    {
        while(tab[i] < v) i++;
        while(tab[j] > v) j--;
        if (i <= j)
        {
            swap(tab[i], tab[j]);
            i++, j--;
        }
    }
    while(i <= j);
    if (l < j)
        quick_sort(tab, l, j);
    if(i < r)
        quick_sort(tab, i, r);
}

Podejrzewam, że w pierwszym przypadku dochodzi do zbyt dużej ilości wywołań rekurencyjnych i miejsce ma przepełnienie stosu. Czy mam rację?

SIGSEGV mówi o tym, że odwołujesz się do adresu pamięci, do którego nie masz prawa. Innymi słowy gdzieś pewnie odwołujesz się do indeksu tablicy przekraczającego rozmiar tablicy.

Poza tym co robi pętla

while(i <= j);

greengoo napisał(a):

SIGSEGV mówi o tym, że odwołujesz się do adresu pamięci, do którego nie masz prawa. Innymi słowy gdzieś pewnie odwołujesz się do indeksu tablicy przekraczającego rozmiar tablicy.

Poza tym co robi pętla

while(i <= j);

To blokada wirująca xD Mie miałeś systemów operacyjnych w kucbazie? xD

ononiemapeja napisał(a):

Poniższa implementacja quicksorta dostaje SIGSEGV podczas sortowania 90 000 elementowej tablicy elementów rosnąco-malejących (0, 1, 2, ... , 2, 1, 0) , radząc sobie bezproblemowo z wielokrotnie większymi tablicami liczb pseudolosowych. Dodam tylko, że na oś wybierany jest umyślnie zawsze element środkowy tablicy - chodzi o spreparowanie najgorszego przypadku.

void quick_sort(int tab[], int l, int r)
{
int v = tab[(l+r)/2];
int i = l;
int j = r;
do
{
while(tab[i] < v) i++;
while(tab[j] > v) j--;
if (i <= j)
{
swap(tab[i], tab[j]);
i++, j--;
}
}
while(i <= j);
if (l < j)
quick_sort(tab, l, j);
if(i < r)
quick_sort(tab, i, r);
}

> Podejrzewam, że w pierwszym przypadku dochodzi do zbyt dużej ilości wywołań rekurencyjnych i miejsce ma przepełnienie stosu. Czy mam rację?


zacznijmy od tego, że pętla 

while(i <= j);

jest całkowicie pozbawiona sensu.