c - 快速排序算法中的分段故障(堆芯故障)

Question

以下是我的快速排序代码（C）。我遇到了分段错误核心转储。
我尽力解决问题，但一无所获。

#include<stdio.h>

int divide(int a[], int p, int q) {
    int mid, i, lastsmall, temp;

    mid = (p + q)/2;
    temp = a[mid];
    a[mid] = a[p];
    a[p] = temp;
    int pivot = a[p];
    lastsmall = p;

    for (i = p + 1; i <= q; i++) {
        if (a[p] > pivot)
            continue;
        else {
             lastsmall++;
             temp = a[i];
             a[i] = lastsmall;
             lastsmall = a[i];
        }
    }
    return lastsmall;
}

void quick(int a[], int p, int q) {
    int pivot;
    if (p < q) {
        pivot = divide(a, p, q);
        quick(a, p, pivot);
        quick(a, pivot + 1, q);
    }
}

int main() {
    int ar[10], i;

    printf("Enter the list\n");
    for (i = 0; i < 10;i++)
        scanf("%d", &ar[i]);
    quick(ar, 0, 9);
    for (i = 0; i < 10; i++)
        printf("%d ", ar[i]);
    return 0;
}

Answer 1

编辑添加一些说明

分段错误很容易在第26行精确定位，一一对应。我无法理解您的divide函数，因此我只是在Rosetta的伪代码之后实现了对数据透视表的搜索。发现简单易懂。

#include<stdio.h>
int divide(int a[], int low, int high)
{
  int pivot, tmp;

  // Yes, you can choose other start values.
  pivot = (low + high)/2;

  while (low <= high) {
    while (a[low] < a[pivot]) {
      low++;
    }
    while (a[high] > a[pivot]) {
      high--;
    }
    if (low <= high) {
      tmp = a[low];
      a[low] = a[high];
      a[high] = tmp;
      low++;
      high--;
    }
  }
  return pivot;
}

void quick(int a[], int p, int q)
{
  int pivot;
  if (p < q) {
    pivot = divide(a, p, q);
    // Here was your segfault
    quick(a, p, pivot - 1);
    quick(a, pivot + 1, q);
  }
}

int main()
{
  int ar[10], i;
  printf("Enter the list\n");
  for (i = 0; i < 10; i++) {
    scanf("%d", &ar[i]);
  }
  quick(ar, 0, 9);
  for (i = 0; i < 10; i++) {
    printf("%d ", ar[i]);
  }
  return 0;
}

实际的实现将涉及很多指针操作，用于比较元素的函数，作为函数指针传递以及大量优化。例如，参见GLibC implementation。

上面的编辑承诺：

枢轴本身可以是任何东西，只要它在输入中的某处即可，甚至可以像我以前一样是恒定的。关于枢轴的选择已经写了许多论文，它们唯一的共同点是结论：它取决于预期的输入。

我在外部while循环中放置了一个计数器（可能更好地计算比较次数），并生成了100次10到10,000之间的100个随机整数。平均“回合数”是用于返回


low = 168.55
--low = 185.67
high = inf（显然）
++high = 174.87
pivot = 216.04（即：始终是起始索引，该索引每第二个调用加一）


如果我将枢轴更改为几何均值的下限，则得到


low = 153.22
--low = 152.65
high = inf
++high = 151.88
pivot = 134.85


计算比较的实际次数，并使用100,000个10至1,000,000之间的随机整数元素数组（数据点仍然是几何平均值），对100次运行进行平均比较


low = 12762491.95
--low = 12756154.17
high = inf
++high = 12702092.52
pivot = 13121675.81


将枢轴设置为几何均值也是如此


low = 12749755.60
--low = 12801865.60
high = inf
++high = 12705592.10
pivot = 13113604.20


有人可能会说，对quick()的调用次数（对divide()的调用略多于具有恒定因子的调用的一半）将是一个更好的衡量标准，它们也是正确的。这次只有10发。

相同


low = 1281068.00
--low = 1225781.20
high = inf
++high = 1221477.00
pivot = 1048575.00


相同，输入从低到高排序


low = 1280983.80
--low = 1225749.80
high = inf
++high = 1221376.80
pivot = 1048575.00


相同，输入从高到低排序


low = 1281025.80
--low = 1225738.80
high = inf
++high = 1221632.20
pivot = 1048575.00


用WhozCraig提出的divide()进行测试：

未分类的输入：1333671.00
排序的输入（从低到高）：1333513.60
排序的输入（从高到低）：1333594.80

稳定的运行时，但也慢了一点点（对于给定的输入而言！）。

结论：对于均匀分布，随机，密集的输入集，将枢轴设置为low和high之间的几何平均值似乎可以节省最多的比较。返回起始枢轴或稍后计算的一个最佳值之间的差异很大，但在比较中却很小，但在实际调用quick()时却相差很大。

对于其他输入集和其他枢轴值（您也可以使用多个枢轴），以及不同的体系结构，这将有所不同。

确实有可能浪费大量时间来优化快速排序，所以要小心！