自定义QuickSort实施中的SIGSEV [英] SIGSEV in custom QuickSort implementation

问题描述

我睡着了对问题 Quicksort戏剧的答案，并想从头开始对其进行重新编码，并使用按引用调用变量。再说一次：我再也找不到失败了。我将代码与您的程序一一比较，但我找不到问题。以下代码在编译/运行期间产生异常（地址11602外部：SIGSEV）

I slept over the answer to question Quicksort drama and wanted to recode it from scratch, implementing your tip with the call-by-reference var. And again: I cannot find any failure I made again. I compare the code to your program one by one and I cannot find the problem. The following code produces an Exception (External:SIGSEV at address 11602) during compilation/run

program quicksort;

var
  iArray : array[0..8] of integer;

procedure fillArray(var iArray : array of integer);
begin;
  iArray[0] := 3;
  iArray[1] := 1;
  iArray[2] := 8;
  iArray[3] := 4;
  iArray[4] := 9;
  iArray[5] := 0;
  iArray[6] := 8;
  iArray[7] := 2;
  iArray[8] := 5;
end;

procedure writeArray(iArray : array of integer);
var i:integer;
begin
  for i:=low(iArray) to high(iArray) do begin
    write(iArray[i]);
  end;
  writeln('');
end;

procedure quickSort(var iArray : array of integer; links : integer; rechts:integer);
var
  l,r,pivot, temp: integer;
begin
  if (rechts > links) then begin
    l := links;
    r := rechts;
    pivot := iArray[(rechts+links) div 2];

    while (l<r) do begin
      while (iArray[l] < pivot) do l:=l+1;
      while (iArray[r] > pivot) do r:=r-1;
      if (l<=r) then begin
       temp := iArray[l];
       iArray[l] := iArray[r];
       iArray[r] := temp;
      end;
    end;
    if (links < r) then quickSort(iArray, links, r);
    if (l < rechts) then quickSort(iArray, l, rechts);
  end;
end;

begin
  fillArray(iArray);
  quickSort(iArray,low(iArray),high(iArray));
  writeArray(iArray);
end.

推荐答案

交换的代码块也需要增加 l 并在交换完成后递减 r ：

The block of code that swaps, also needs to increment l and decrement r once the swap is complete:

if (l <= r) then
begin
  temp := iArray[l];
  iArray[l] := iArray[r];
  iArray[r] := temp;
  inc(l); // <-- this was missing
  dec(r); // <-- as was this
end;

完整的程序，还有一些其他小的整理动作：

The complete program, with some other minor tidy ups:

program quicksort24340509;

var
  iArray: array [0 .. 8] of integer;

Procedure fillArray(var iArray: array of integer);
begin;

  iArray[0] := 3;
  iArray[1] := 1;
  iArray[2] := 8;
  iArray[3] := 4;
  iArray[4] := 9;
  iArray[5] := 0;
  iArray[6] := 8;
  iArray[7] := 2;
  iArray[8] := 5;
end;

Procedure writeArray(const iArray: array of integer);
var
  i: integer;
begin
  for i := low(iArray) to high(iArray) do
  begin
    write(iArray[i], ' ');
  end;
  writeln;
end;

Procedure quickSort(var iArray: array of integer; links, rechts: integer);
var
  l, r, pivot, temp: integer;
begin
  if (rechts > links) then
  begin
    l := links;
    r := rechts;
    pivot := iArray[(rechts + links) div 2];

    while l < r do
    begin
      while iArray[l] < pivot do inc(l);
      while iArray[r] > pivot do dec(r);
      if l <= r then
      begin
        temp := iArray[l];
        iArray[l] := iArray[r];
        iArray[r] := temp;
        inc(l);
        dec(r);
      end;
    end;
    if links < r then
      quickSort(iArray, links, r);
    if l < rechts then
      quickSort(iArray, l, rechts);
  end;
end;

begin
  fillArray(iArray);
  quickSort(iArray, low(iArray), high(iArray));
  writeArray(iArray);
  readln;
end.

输出

0 1 2 3 4 5 8 8 9

---

您的版本失败而没有缺少行的原因是，对 quickSort 的递归调用在错误的范围内运行。

---

The reason that your version fails, without the missing lines, is that the recursive calls to quickSort operate on the wrong ranges.

例如，假设您输入了

3 1 8 4 9 0 8 2 5

分区步骤以 9 并得出

3 1 8 4 5 0 8 2 9

现在，递归步骤应该是将所有值排序到枢轴的左侧，并将所有值排序在右侧。而且我们不考虑枢轴，因为分区确保了它处于最终位置。

Now, the recursive step should be to sort all the values to the left of the pivot, and all the values to the right. And we leave the pivot alone because partitioning ensured that it is in its final position.

枢轴右边没有值，因此我们应该进行递归调用范围为0到7。但是，如果检查代码会发生什么，您会发现代码不会发生变化。相反，它会递归调用0到8的范围。它本身有点良性，但是一旦范围变小，在停止条件下，情况就不同了。尝试让您的程序对这些值进行排序：

There are no values to the right of the pivot so we should be making a recursive call for the range 0 to 7. But if you inspect what happens with your code you will find that it does not. Instead it makes a recursive call for the range 0 to 8. That in itself is a little benign, but once the ranges become small, at the stopping condition, it's different. Try asking your program to sort these values:

1 2

代码以 1 为中心。在分区结束时，我们有：

The code pivots on 1. At the end of partitioning we have:

links = 0
rechts = 1
l = 0
r = 0

所以我们递归地调用 quickSort 传递 l 和 rechts 作为范围。但这跟我们最初打的电话完全一样。因此，这会导致堆栈溢出。

So we recursively call quickSort passing l and rechts as the ranges. But that's exactly the same call as we initially made. And that therefore leads to a stack overflow.

因此，要点是，我们必须确保在对数据透视表进行分区时，将其排除在以后的所有递归调用中到 quickSort 。如果不这样做，就不会细分问题，递归也不会终止。

So the point is that we must make sure that when we partition on a pivot, we exclude that pivot from all future recursive calls to quickSort. If we don't do that we don't sub-divide the problem, and the recursion does not terminate.

这篇关于自定义QuickSort实施中的SIGSEV的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！