Recursion - Multimedia Introduction to Programming Using Java - page 414

0 15
4 6 0 1 0 4 5 7 3 9 2 3 1 8 7 5

We develop an upper bound on the number of array comparisons that
quicksort will make when sorting this array segment, in the best possible case,
under the assumption that method partition performs one comparison for each
array element that it processes.
When quicksort is given this array segment to sort, the if-condition in its
body evaluates to false , so the assignment to j is executed. This assignment
partitions as shown below —to the right of the array, we give an upper bound 16
on the number of array comparisons used to partition the array.

0 j 15
1 3 0 2 0 3 1 4 7 9 6 4 5 8 7 5

16 comparisons

The initial value in b[0] , the pivot value, has been placed in b[j] , everything to
the left of b[j] is at most b[j] , and everything to the right is at least b[j] , so
the comment following the assignment to j has been truthified.
Procedure quicksort sorts b[0..j-1] and then b[j+1..15] . But for this
analysis, it is better to think of quicksort as partitioning both these segments
and then sorting them. Below, we show the results of partitioning the two seg-
ments. Since each segment has at most 8 elements, the number of comparisons
made in partitioning each of them is at most 8, for a total of at most 16.

j
0 0 1 1 3 2 3

j
5 5 6 4 7 8 7 9

8 + 8 = 16 comparisons

Now 4 segments are to be sorted recursively: b[0..2] , b[4..6] , b[8..11] ,
and b[13..15] . Each segment has at most 4 elements. The first step in sorting
them is to partition them, and since each has at most 4 elements, partitioning
them takes at most 4 * 4 = 16 comparisons.
On the next level, 8 segments are partitioned, each with at most 2 elements,
so again it takes a maximum of 16 comparisons. This leaves 16 segments of at
most 1 element each, and each is handled as a base case, so no more comparisons
are done.
In summary, here is what procedure partition does on each level:

level no. of partitions max size of partition max no. of comparisons

1 1 16 16

2 2 8 16

3 4 4 16

4 8 2 16