CODEWITHSUNDEEP
delphipascalquicksort
gutenmorgenuhu
gutenmorgenuhu

Reputation: 2362

Quicksort drama

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.

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

What is happening here?

Upvotes: 7

Views: 1481

Answers (1)

David Heffernan
David Heffernan

Reputation: 612904

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);

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.

Output

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!

Upvotes: 8

Related Questions