This is the first in a series of recursive sorting algorithms. Sorting algorithms, as their name implies, intend to take an unsorted collection of things—numbers, for now, but they could be anything—and put them in order.
Quicksort does this recursively with a “pivot” element. This pivot element
works like a fulcrum on a lever: you have the left side of the lever (which is
entirely left of the fulcrum), the fulcrum, and the right side of the lever
(which is entirely right of the fulcrum).
Quicksort works like this:
- Pick a pivot
- Move everything less than the pivot to its left
- Move everything greater than the pivot to its right
- Quicksort the left
- Quicksort the right
When we’re looking at only 0 or 1 elements, those are
trivially already sorted—our base cases/stopping conditions for the recursion.
Suppose we have
|
3 |
7 |
2 |
4 |
1 |
5 |
6 |
There are many ways to pick pivots—the first, the last, the middle, the median
(but this involves already sorting them, then picking the middle element), a random
element. Here, for simplicity, we’ll pick the middle, 4 (3 things on its left,
it, 3 things on its right).
Now, everything less than 4 goes on 4’s left, and everything greater goes on 4’s
right.
|
3 |
2 |
1 |
4 |
7 |
5 |
6 |
Now, let’s just look at “the left”:
|
3 |
2 |
1 |
The pivot is 2; there is only one element less than it, so
it is “the left” of “the left”; and there is only one element greater than 2,
so it is “the right” of “the left.”
|
1 |
2 |
3 |
Now, let’s apply the same procedure to “the right” (and include the first pivot):
|
4 |
7 |
5 |
6 |
Let’s pick 6 as the pivot—so everything less than 6 is on the left of 6, then
we have 6, then we have everything greater than it on the right.
|
4 |
5 |
6 |
7 |
We quickSorted the left half and the right half (where our pivot was), so we
have successfully sorted both halves of the array—the left half (everything less
than the pivot) and the right half (the pivot and everything greater). Since we
have sorted both halves of the array, we have sorted the whole array:
|
3 |
7 |
2 |
4 |
1 |
5 |
6 |
sorted with quicksort becomes
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Before you go on, try a few more examples of about this size—no fewer than 5,
no more than 10. Pick a pivot, sort the left half (by picking a pivot), sort
the right half (by picking a pivot).
In pseudocode, this is:
quicksort(arr, left, right)
if left >=
right
return
// Choose the
middle element as pivot
mid = left +
(right - left) / 2
pivot = arr[mid]
// Partition the
array
i = left
j = right
while i <= j
while arr[i]
< pivot
i = i + 1
while arr[j]
> pivot
j = j - 1
if i <= j
swap
arr[i] and arr[j]
i = i + 1
j = j - 1
// Recursively
sort the two partitions
quicksort(arr,
left, j)
quicksort(arr, i,
right)
and in real Java, this is:
public class QuickSort {
public static
void quicksort(int[] arr, int left, int right) {
if (left
>= right) {
return;
}
// Choose the
middle element as pivot
int mid =
left + (right - left) / 2;
int pivot =
arr[mid];
int i = left;
int j =
right;
while (i
<= j) {
while
(arr[i] < pivot) {
i++;
}
while
(arr[j] > pivot) {
j--;
}
if (i
<= j) {
//
Swap arr[i] and arr[j]
int
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
//
Recursively sort the two partitions
if (left <
j) {
quicksort(arr, left, j);
}
if (i <
right) {
quicksort(arr, i, right);
}
}
// Example usage
public static
void main(String[] args) {
int[] array =
{ 9, 3, 7, 1, 8, 2, 5, 4, 6 };
quicksort(array, 0, array.length - 1);
// Print
sorted array
for (int num
: array) {
System.out.print(num + " ");
}
}
}
No comments:
Post a Comment