Java Reference

In-Depth Information

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

Search WWH ::

Custom Search