Java Reference
In-Depth Information
Assuming a function
partition
is available that partitions a given section of an array and returns the division
point, we can write
quicksort
as follows:
public static void quicksort(int[] A, int lo, int hi) {
//sorts A[lo] to A[hi] in ascending order
if (lo < hi) {
int dp = partition(A, lo, hi);
quicksort(A, lo, dp-1);
quicksort(A, dp+1, hi);
}
} //end quicksort
The call
quicksort(num, 1, n)
will sort
num[1..n]
in ascending order.
We now look at how
partition
may be written. Consider the following array:
num
53
12
98
63
18
32
80
46
72
21
1
2
3
4
5
6
7
8
9
10
We will partition it with respect to
num[1]
, 53 (the pivot) by making one pass through the array. We will look at
each number in turn. If it is bigger than the pivot, we do nothing. If it is smaller, we move it to the left side of the array.
Initially, we set the variable
lastSmall
to
1
; as the method proceeds,
lastSmall
will be the index of the last item that
is known to be smaller than the pivot. We partition
num
as follows:
Compare
12
with
53
; it is smaller, so add
1
to
lastSmall
(making it
2
) and swap
num[2]
with itself.
1.
Compare
98
with
53
; it is bigger, so move on.
2.
Compare
63
with
53
; it is bigger, so move on.
3.
Compare
18
with
53
; it is smaller, so add
1
to
lastSmall
(making it
3
) and swap
num[3]
,
98
,
with
18
.
4.
At this stage, we have this:
num
53
12
18
63
98
32
80
46
72
21
1
2
3
4
5
6
7
8
9
10
5.
Compare
32
with
53
; it is smaller, so add
1
to
lastSmall
(making it
4
) and swap
num[4]
,
63
, with
32
.
6.
Compare
80
with
53
; it is bigger, so move on.
7.
Compare
46
with
53
; it is smaller, so add
1
to
lastSmall
(making it
5
) and swap
num[5]
,
98
,
with
46
.
At this stage, we have the following:
num
53
12
18
32
46
63
80
98
72
21
1
2
3
4
5
6
7
8
9
10
Search WWH ::
Custom Search