Quicksort Demonstration 2 (Lazarus)

Our next version of quicksort, based on a C implementation by Eugene Jitomirsky, does not allow the pivot to move until the end of the partitioning procedure. The pivot starts as the first item in the list and swaps into the list in its final position at the end of each procedure. The pivot never needs to be included in either partition afterwards.

We have checked that the output corresponds to the annotated results on the web page. We have also checked it with Knuth's data set (page 114) for a similar quicksort algorithm.

program QuickSortDemo2;
  {$APPTYPE CONSOLE}
uses
  SysUtils, crt;
const
  UPPER_BOUND = 9;
  FIELD_WIDTH = 3;
var
  Ints : array[1..UPPER_BOUND] of integer = (3, 1, 4, 5, 9, 2, 6, 8, 7);
procedure Quicksort(Left, Right: integer);
var
  ptrLeft, ptrRight, Pivot, Temp: integer;
procedure DisplayArray;
var
  Count : integer;
begin
  for Count := 1 to UPPER_BOUND do
    begin
      if (Count >= Left) and (Count <= Right) then
        textBackground(yellow)
      else
        textBackground(black);
      if Count = ptrLeft  then
        textColor(green)
      else if Count =  ptrRight then
        textColor(Red)
      else
        textColor(white);
      if Ints[Count] =  Pivot then
        textBackground(lightgray);
      write(ints[Count] : FIELD_WIDTH);

    end;
    textColor(white);
    textBackground(black);
    if PtrLeft = PtrRight then
      writeln('  Pointers coincide. Press return to continue.')
    else
      writeln('                     Press return to continue.');
    readln;
end;
begin
  ptrLeft := Left;
  ptrRight := Right;
  Pivot := Ints[Left];
  TextColor(white);
  writeln('Quicksort for index ', Left,  ' to ', Right, ' with pivot ', Pivot,':');
  DisplayArray;
  if Right - Left >= 1 then
    begin
    {Increment left pointer if value is less than or equal to pivot and has not passed
     upper index of array partition and is still less than right pointer.}
     while ptrRight > ptrLeft do
       begin
         while (ptrLeft <= Right) and (Ints[ptrLeft] <= Pivot) and (ptrRight > ptrLeft) do
           begin
             writeln('Left pointer moves right:');
             inc(ptrLeft);
             DisplayArray;
           end;
         {Decrement left pointer if value is less than pivot and has not reached
         lower index of array partition.}
         while (ptrRight >= Left) and (Ints[ptrRight] >= Pivot) and (ptrRight >= ptrLeft) do
           begin
             writeln('Right pointer moves left:');
             dec(ptrRight);
             DisplayArray;
           end;
        if ptrLeft < ptrRight then  //if left pointer and right pointer have not crossed
          begin
            //Swap values at left and right pointers if pointers are not equal
            writeln(Ints[ptrLeft], ' swaps with ', Ints[ptrRight],':');
            Temp := Ints[ptrLeft];
            Ints[ptrLeft] := Ints[ptrRight];
            Ints[ptrRight] := Temp;
            DisplayArray;
          end;
       end; //while
       //Swap start with ptrRight
       writeln('Pivot ',Pivot, ' swaps with ', Ints[ptrRight],':');
       Ints[Left] := Ints[ptrRight];
       Ints[ptrRight] := Pivot;
       DisplayArray;
       Quicksort(Left, ptrRight - 1);
       Quicksort(ptrRight + 1, Right);
  end
  else
    writeln('No need to sort because Right - Left < 1');
   //if
end;//proc
begin
  Quicksort(1, UPPER_BOUND);
  writeln('Sorted!');
  readln;
end.
Programming - a skill for life!

Discussion of quicksort