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
else
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
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!');