Java Reference
In-Depth Information
We choose 53 as the pivot. The general idea is to scan from the right looking for a key that is smaller than, or
equal to, the pivot. We then scan from the left for a key that is greater than, or equal to, the pivot. We swap these two
values; this process effectively puts smaller values to the left and bigger values to the right.
We use two variables,
lo
and
hi
, to mark our positions on the left and right. Initially, we set
lo
to
0
and
hi
to
11
(
n+1
). We then loop as follows:
1.
Subtract
1
from
hi
(making it
10
).
2.
Compare
num[hi]
,
21
, with
53
; it is smaller, so stop scanning from the right with
hi
=
10
.
3.
Add
1
to
lo
(making it
1
) .
4.
Compare
num[lo]
,
53
, with
53
; it is not smaller, so stop scanning from the left with
lo
=
1
.
5.
lo
(
1
) is less than
hi
(
10
), so swap
num[lo]
and
num[hi]
.
6.
Subtract
1
from
hi
(making it
9
).
7.
Compare
num[hi]
,
72
, with
53
; it is bigger, so decrease
hi
(making it
8
). Compare
num[hi]
,
46
, with
53
; it is smaller, so stop scanning from the right with
hi
=
8
.
8.
Add
1
to
lo
(making it
2
).
9.
Compare
num[lo]
,
12
, with
53
; it is smaller, so add
1
to
lo
(making it
3
). Compare
num[lo]
,
98
, with
53
; it is bigger, so stop scanning from the left with
lo
=
3
.
10.
lo
(
3
) is less than
hi
(
8
), so swap
num[lo]
and
num[hi]
.
At this stage, we have
lo
=
3
,
hi
=
8
and
num
as follows:
num
21
12
46
63
18
32
80
98
72
53
1
2
3
4
5
6
7
8
9
10
11.
Subtract
1
from
hi
(making it
7
).
12.
Compare
num[hi]
,
80
, with
53
; it is bigger, so decrease
hi
(making it
6
). Compare
num[hi]
,
32
, with
53
; it is smaller, so stop scanning from the right with
hi
=
6
.
13.
Add
1
to
lo
(making it
4
).
14.
Compare
num[lo]
,
63
, with
53
; it is bigger, so stop scanning from the left with
lo
=
4
.
15.
lo
(
4
) is less than
hi
(
6
), so swap
num[lo]
and
num[hi]
, giving this:
num
21
12
46
32
18
63
80
98
72
53
1
2
3
4
5
6
7
8
9
10
Subtract
1
from
hi
(making it
5
).
16.
Compare
num[hi]
,
18
, with
53
; it is smaller, so stop scanning from the right with
hi
=
5
.
17.
Add
1
to
lo
(making it
5
).
18.
Compare
num[lo]
,
18
, with
53
; it is smaller, so add
1
to
lo
(making it
6
). Compare
num[lo]
,
63
, with
53
; it is bigger, so stop scanning from the left with
lo
=
6
.
19.
20.
lo
(
6
) is
not
less than
hi
(
5
), so the algorithm ends.
Search WWH ::
Custom Search