c - 对具有大量元素的数组进行排序时发出 SIGSEGV 信号

Question

我有一个包含 100000 个元素(整数)的数组，我想使用快速排序对其进行排序。当我用随机数填充这个数组时它会起作用，但是当我像这样填充它时

for(i=0; i<size/2; i++)
{
    tablica[i]= i;
}
for(i=size/2; i<size; i++)
{
    tablica[i]=size-i-1;
}

我收到 SIGSEGV 信号，我的应用崩溃了。我确定我的快速排序功能没问题。当我用随机、升序或降序数字填充此数组时，一切正常，即使数组中有更多元素(如 100000000)。我这样初始化数组:

int *tablica = calloc(size, sizeof (int));

这是我的快速排序代码

void quicksort(int tab[], int lewy, int prawy)
{
int pivot = tab[(prawy+lewy)/2];
int p = prawy;
int l = lewy;
do
{
    while (tab[l] < pivot)
    {
        l++;
    }
    while (tab[p] > pivot)
    {
        p--;
    }
    if (l <= p)
    {
        int temp = tab[l];
        tab[l] = tab[p];
        tab[p] = temp;
        l++; p--;
    }
} while (l <= p);

if(p>lewy)
{
    quicksort(tab,lewy,p);
}
if(l<prawy)
{
    quicksort(tab,l,prawy);
}
}

和主要功能的例子

int main()
{
srand(time(NULL));
int i;
int *tablica;
float start, stop, czas;
tablica = calloc(size, sizeof (int));
int *tab = calloc(size, sizeof (int));
for(i=0; i<size/2; i++)
{
    tablica[i]= i;
}
for(i=size/2; i<size; i++)
{
    tablica[i]=size-i-1;
}
start = clock();
quicksort(tablica,0,size-1);
stop = clock();
czas = (stop-start)/CLOCKS_PER_SEC;
free(tablica);
free(tab);
return 0;
}

Answer 1

I'm sure that my quicksort function is fine.

它可能是递归的，不是吗？您看到的很可能是堆栈溢出，这是由递归嵌套太深引起的。快速排序在这方面尤其薄弱，这取决于枢轴的选择和值的分布。

示例:大小为 8 的数组，按照您指定的方式填充:

0 1 2 3 3 2 1 0

让我们以第一个值作为基准，因此在分区之后我们可能会得到:

0|0|1 2 3 3 2 1

看看发生了什么？我们只设法将一个数字放入左侧部分。在正确的部分快速排序不会更好:

1 2 3 3 2 1

我们像以前一样以第一个为枢轴并进行划分:

1|1|2 3 3 2

等等。

在每一步中，您只需对 2 个元素进行排序(左侧部分的主元和单个元素)...因此，对于 100000 个数字的数组，您需要 50000 步才能对其进行排序。每一步都是递归调用。这对于(调用)堆栈来说太多了。

为了减轻出现这种模式的危险，您应该调整 choice of your pivot value .

---

来自添加的快速排序代码:

int pivot = tab[(prawy+lewy)/2];

您始终选择排序范围中间的值。在第一次迭代中，这将是 size/2 -1，并且由于没有比该值更大的值(由于数组的初始化方式)，右侧部分将(几乎)为空，从而导致与我上面显示的类似模式。

提示:只需尝试使用较小的代码(例如 8)，并在每次调用时打印快速排序正在处理的数组:

0, 1, 2, 3, 3, 2, 1, 0 // (1)
0, 1, 2, 0, 1, 2
0, 1, 2, 0, 1
0, 1, 1, 0 // (2)
0, 0 // right part from (2)
3, 3 // right part from (1)

( Ideone )