我有一个包含 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;
}
最佳答案
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 )
关于c - 对具有大量元素的数组进行排序时发出 SIGSEGV 信号,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36345404/