Quicksort戏剧 [英] Quicksort drama

问题描述

我只能把头砸在墙上。我不明白，为什么下面的快速排序算法无法正常工作。它是用Pascal编写的：

I just could smash my head against the wall. I do not understand, why my following quicksort algorithm is not working. It is written in Pascal:

program quicksort;

Type iArray = array [0..8] of integer;
var intArray, newArray : iArray;

Function getIntArray(localIntArray : iArray) : iArray;
begin
  localIntArray[0] := 3;
  localIntArray[1] := 1;
  localIntArray[2] := 8;
  localIntArray[3] := 4;
  localIntArray[4] := 9;
  localIntArray[5] := 0;
  localIntArray[6] := 8;
  localIntArray[7] := 2;
  localIntArray[8] := 5;
  getIntArray := localIntArray;
end;

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

Procedure quicksort(links : integer ; rechts:integer; localIntArray : iArray); 
// links:      Index des 1. Elements, rechts: Index des letzten Elements
var l, r, pivot, pivotValue, temp : Integer;


    Function swap (larray : iArray; links :integer; rechts:integer) : iArray;                                 
    // Ich tausche in einem IntegerArray die Positionen links und rechts
    var temp : integer;
    begin
        temp                    := larray[links];
        larray[links]           := larray[rechts];
        larray[rechts]          := temp;
        swap                    := larray;
    end;

begin
  if (rechts>links) then begin
    l:= links;
    r:= rechts;
    pivot := localIntArray[(rechts+links) div 2];

    while (l<r) do begin
       while localIntArray[l] < pivot do l:=l+1;
       while localIntArray[r] > pivot do r:=r-1;
       if (l<=r) then begin
         localIntArray := swap(localIntArray,l,r);
         l := l+1;
         r := r-1;
       end;
    end;

    if (links < r) then quicksort(links, r, localIntArray);
    if (rechts > l) then quicksort(l, rechts, localIntArray);

    writeln('s Array: ');
    writeArray(localIntArray);
  end;
end;

var i : integer;
begin

  intArray := getIntArray(intArray);
  writeln('Unsortiertes Array: ');
  writeArray(intArray);
  quicksort(low(intArray), high(intArray), intArray);

end.

当我输入数组时： 3,1,8,4,9 ，0,8,2,5
我收到以下计算结果：

When I input the array: 3,1,8,4,9,0,8,2,5 I receive the following calculations:

0,1， 2,3,5,4,8,8,9 -> 0,1,2,3,5,4,8,8,9 -> 3,1,2,0,4,5,8,8,9 -> 3,1,2,0， 4,5,8,8,9 -> 3,1,2,0,4,5,8,8,9 -> 3,1,2,0,5,4,8,8,9 -> 3,1,8,4,5,0， 8,2,9

0,1,2,3,5,4,8,8,9 -> 0,1,2,3,5,4,8,8,9 -> 3,1,2,0,4,5,8,8,9 -> 3,1,2,0,4,5,8,8,9 -> 3,1,2,0,4,5,8,8,9 -> 3,1,2,0,5,4,8,8,9 -> 3,1,8,4,5,0,8,2,9

这里发生了什么？

推荐答案

您的程序失败，因为您对数组的副本进行了操作，而不是就地进行操作。因此，请考虑 quicksort 的声明：

Your program fails because you operate on copies of the array, rather than operating in-place. So consider the declaration of quicksort:

Procedure quicksort(links, rechts: integer; localIntArray: iArray);

该数组按值传递。您将数组传递给过程，但是调用者从不会看到对数组所做的任何更改。相反，您需要通过将引用传递给数组来进行就地操作。那是一个 var 参数：

The array is passed by value. You pass the array into the procedure, but any changes made to the array are never seen by the caller. Instead you need to operate in place by passing a reference to the array. That is a var parameter:

Procedure quicksort(links, rechts: integer; var localIntArray: iArray);

您还需要对交换应该这样声明的过程：

And you need to do likewise with the swap procedure which should be declared like this:

Procedure swap(var larray: iArray; links, rechts: integer);

这是一个完整的程序，可以正确排序：

Here is a complete program that sorts correctly:

program quicksort24335585;

Type
  iArray = array [0 .. 8] of integer;

var
  intArray: iArray;

Function getIntArray(localIntArray: iArray): iArray;
begin
  localIntArray[0] := 3;
  localIntArray[1] := 1;
  localIntArray[2] := 8;
  localIntArray[3] := 4;
  localIntArray[4] := 7;
  localIntArray[5] := 0;
  localIntArray[6] := 8;
  localIntArray[7] := 2;
  localIntArray[8] := 5;
  getIntArray := localIntArray;
end;

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

Procedure quicksort(links: integer; rechts: integer; var localIntArray: iArray);
// links:      Index des 1. Elements, rechts: Index des letzten Elements
var
  l, r, pivot: integer;

  procedure swap(var larray: iArray; links: integer; rechts: integer);
  // Ich tausche in einem IntegerArray die Positionen links und rechts
  var
    temp: integer;
  begin
    temp := larray[links];
    larray[links] := larray[rechts];
    larray[rechts] := temp;
  end;

begin
  if (rechts > links) then
  begin
    l := links;
    r := rechts;
    pivot := localIntArray[(rechts + links) div 2];

    while (l < r) do
    begin
      while localIntArray[l] < pivot do
        l := l + 1;
      while localIntArray[r] > pivot do
        r := r - 1;
      if (l <= r) then
      begin
        swap(localIntArray, l, r);
        l := l + 1;
        r := r - 1;
      end;
    end;

    if (links < r) then
      quicksort(links, r, localIntArray);
    if (rechts > l) then
      quicksort(l, rechts, localIntArray);
  end;
end;

begin
  intArray := getIntArray(intArray);
  writeln('Unsortiertes Array: ');
  writeArray(intArray);

  quicksort(low(intArray), high(intArray), intArray);

  writeln('s Array: ');
  writeArray(intArray);

  Readln;
end.

输出

Unsortiertes Array:
3 1 8 4 7 0 8 2 5
s Array:
0 1 2 3 4 5 7 8 8

我很确定该程序可以完善和改进。这样做将成为您学习曲线的一部分！

I'm quite sure the program could be polished and improved. Doing so will be part of your learning curve!

这篇关于Quicksort戏剧的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！