±.³. Quicksort
².¶
Quicksort
Quicksort is another recursive sorting algorithm, discovered by Tony Hoare in
´¶¸¶ and first published in ´¶¹´. In this algorithm, the hard work is splitting
the array into smaller subarrays
before
recursion, so that merging the sorted
subarrays is trivial.
´. Choose a
pivot
element from the array.
³.
Partition the array into three subarrays containing the elements smaller
than the pivot, the pivot element itself, and the elements larger than the
pivot.
². Recursively quicksort the first and last subarrays.
Input:
S
O
R
T
I
N
G
E
X
A
M
P
L
Choose a pivot:
S
O
R
T
I
N
G
E
X
A
M
P
L
Partition:
A
G
O
E
I
N
L
M
P
T
X
S
R
Recurse Left:
A
E
G
I
L
M
N
O
P
T
X
S
R
Recurse Right:
A
E
G
I
L
M
N
O
P
R
S
T
X
Figure ².·.
A quicksort example.
More detailed pseudocode is given in Figure ´.µ. In the
P±µ²´²´¸¾
subroutine,
the input parameter
p
is the index of the pivot element in the unsorted array;
the subroutine partitions the array and returns the new index of the pivot
element. There are many different efficient partitioning algorithms; the one
I’m presenting here is attributed to Nico Lomuto.
¹
The variable
‘
counts the
number of items in the array that are
‘
ess than the pivot element.
Q·´¶ÈS¸µ²
(
A
[
1 ..
n
])
:
if
(
n
>
1
)
Choose a pivot element
A
[
p
]
r
←
P±µ²´²´¸¾
(
A
,
p
)
Q·´¶ÈS¸µ²
(
A
[
1 ..
r
-
1
])
〈〈
Recurse!
〉〉
Q·´¶ÈS¸µ²
(
A
[
r
+
1 ..
n
])
〈〈
Recurse!
〉〉
P±µ²´²´¸¾
(
A
[
1 ..
n
]
,
p
)
:
swap
A
[
p
]
↔
A
[
n
]
‘
←
0
〈〈
#items
<
pivot
〉〉
for
i
←
1
to
n
-
1
if
A
[
i
]
<
A
[
n
]
‘
←
‘
+
1
swap
A
[
‘
]
↔
A
[
i
]
swap
A
[
n
]
↔
A
[
‘
+
1
]
return
‘
+
1
Figure ².8.
Quicksort
Correctness
Just like mergesort, proving that
Q·´¶ÈS¸µ²
is correct requires two separate
induction proofs: one to prove that
P±µ²´²´¸¾
correctly partitions the array, and
¹
Hoare proposed a more complicated “two-way” partitioning algorithm that has some
practical advantages over Lomuto’s algorithm. On the other hand, Hoare’s partitioning algorithm
is one of the places off-by-one errors go to die.
¶´