This sorting method is more sophisticated than the 'bubble' sort method and is much faster than most other methods when sorting large lists. It is the method employed for sort methods in many Delphi objects.
The approach of the quick sort method is to select one item from the list and put it in its correct place in the list, an action that produces two sub_lists, one either side of the correctly placed item. The action is then repeated for a number in each sub_list, and so on until all the numbers have been placed in their correct positions. Defining the problem in this way leads to a recursive solution.
We will use the following data set:
23 12 54 36 76 14 98 15 83 11
We select an item to put in its correct place with the other numbers on either side. Taking 23 as the first item we must search from the right end of the list for items less than 23 and from the left end of the list for items greater than 23.
From the right we find 11, which is less than 23, and from the left we find 54, which is greater than 23. We now swap these round, giving:
23 12 11 36 76 14 98 15 83 54
The search continues for a number less than 23 on the right, which yields 15, and from the left for one greater than 23, which produces 36. These are now swapped:
23 12 11 15 76 14 98 36 83 54
A further search produces 76 and 14:
23 12 11 15 14 76 98 36 83 54
At this point the right pointer has moved 5 places left and the left pointer has moved 4 places right; on the next move the pointers will cross, which will signal the end of the first cycle and at this point the first number is swapped with the left pointer giving:
14 12 11 15 23 76 98 36 83 54
This produces a mid-point value of 23 and two sub_lists, [14 12 11 15] and [76 98 36 83 54]. These can be treated in exactly the same way.
The code:
The list of numbers is initialised by the FormCreate event. The numbers are presented as the caption in an edit box:
The button handler calls the quick sort procedure and displays the sorted list in the second edit box:
procedure TForm1.Button1Click(Sender: TObject);
var
i:integer;
displaystring:string;
begin
quicksort(1, length(numlist));
for i:= 1 to length(numlist) do
displaystring:= displaystring+inttostr(numlist[i])+ ' ';
edit2.Text:=displaystring;
end;
The quicksort procedure is as follows:
procedure TForm1.quicksort(low, high:integer);
var mid:integer;
begin
if low < high then
begin
split(low, high, mid);
quicksort(low, mid-1);
quicksort(mid+1, high);
end;
end;
The initial parameters for quicksort are 1 and 10, the length of numlist. The quicksort procedure calls split, which splits the list in the way we have seen, and then calls itself twice to process the two sub_lists it created by split. These recursive calls continue as long as the condition low < high is met. The code for split is the key to the quick sort algorithm:
procedure TForm1.split(low, high:integer; var
mid:integer);
var
left, right : integer;
temp:datatype;
begin
left:=low;
right:=high;
while left < right do
begin
while numlist[right] > numlist[low] do
right:=right-1 //move right
pointer until numlist[right] is less than numlist[low]
while (left < right) and (numlist[left] <= numlist[low]) do
left:=left+1; //move left
pointer until numlist[left] is greater than numlist[low]
if left < right then //pointers have
not crossed so swap items found
begin
temp:=numlist[left];
numlist[left]:=numlist[right];
numlist[right]:=temp;
end;
end; //while left < right
mid := right; //set mid-point of list
temp:=numlist[mid]; //swap first item with
mid-point
numlist[mid]:= numlist[low];
numlist[low]:=temp;
end;
The split procedure takes the low and high values from the call to quicksort (1 and 10 for the first call in this case) and uses them in compare operations with the left and right pointers as they track across the list. Subsequent calls of quicksort operate on sub-lists produced by changing the parameters to the left and right items of the sub-lists.
It works!