Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Implementation

Program gif introduces the AbstractQuickSorter class. The AbstractQuickSorter class extends the AbstractSorter class defined in Program gif. It declares the abstract method SelectPivot the implementation of which is provided by a derived class.

   program37504
Program: AbstractQuickSorter fields.

Program gif defines a Sort method of the AbstractQuickSorter class that takes two integer arguments, left and right, which denote left and right ends, respectively, of the section of the array to be sorted. That is, this Sort method sorts

displaymath69156

.

   program37525
Program: AbstractQuickSorter class recursive Sort method.

As discussed above, the AbstractQuickSorter only sorts sequences whose length exceeds the cut-off value. Since the implementation shown only works correctly when the number of elements in the sequence to be sorted is three or more, the cut-off value of two is used (line 5).

The algorithm begins by calling the method SelectPivot which chooses one of the elements to be the pivot (line 7). The implementation of SelectPivot is discussed below. All that we require here is that the value p returned by SelectPivot satisfies tex2html_wrap_inline69160. Having selected an element to be the pivot, we hide the pivot by swapping it with the right-most element of the sequence (line 8). The pivot is hidden in order to get it out of the way of the next step.

The next step partitions the remaining elements into two sequences--one comprised of values less than or equal to the pivot, the other comprised of values greater than or equal to the pivot. The partitioning is done using two array indices, i and j. The first, i, starts at the left end and moves to the right; the second, j, starts at the right end and moves to the left.

The variable i is increased as long as array[i] is less than the pivot (line 14). Then the variable j is decreased as long as array[j] is greater than the pivot (line 15). When i and j meet, the partitioning is done (line 16). Otherwise, tex2html_wrap_inline69162 but tex2html_wrap_inline69164. This situation is remedied by swapping array[i] and array[j] (line 17).

When the partitioning loop terminates, the pivot is still in array[right]; the value in array[i] is greater than or equal to the pivot; everything to the left is less than or equal to the pivot; and everything to the right is greater than or equal to the pivot. We can now put the pivot in its proper place by swapping it with array[i] (lines 19-20). This is called restoring the pivot. With the pivot in its final resting place, all we need to do is sort the subsequences on either side of the pivot (lines 21-24).

Program gif defines the no-arg Sort method of the AbstractQuickSorter class. The no-arg Sort acts as the front end to the recursive Sort given in Program gif. It calls the recursive Sort method with left set to zero and right set to n-1, where n is the length of the array to be sorted. Finally, it uses a StraightInsertionSorter to finish sorting the list.

   program37575
Program: AbstractQuickSorter class Sort method.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.