The idea of quicksort is taking one element (called the pivot) from an array and compare it with all other elements to divide them into two groups: (1) smaller than (or equal to) the pivot and (2) bigger than the pivot. Here is an example.
|
37 |
23 |
7 |
93 |
82 |
10 |
49 |
55 |
2 |
70 |
If we take 37 as the pivot, then we can divide this array into two groups: {23, 7, 10, 10, 2} and {93, 82, 49, 55, 70}. We then rearrange the array as follows.
|
23 |
7 |
10 |
2 |
37 |
93 |
82 |
49 |
55 |
70 |
Now {23, 7, 10, 2} and {93, 82, 49, 55, 70} are arrays of smaller size to be sorted. We can use recursive calls to sort them. Note that the orders within the sets {23, 7, 10, 10, 2} and {93, 82, 49, 55, 70} are unimportant. As long as these two sets are correctly divided, quicksort will work correctly. You can always use the first element in the array as the pivot. However, this is not a requirement since choosing which element to be the pivot does not affect the correctness of quicksort.
The sample code for quicksort is given as follows.
#include <iostream>
using namespace std;
int partition(int arr[], int start, int end) {
int pivot = arr[start];
int count = 0;
for (int i = start + 1; i <= end; i++) {
if (arr[i] <= pivot)
count++;
}
// Giving pivot element its correct position
int pivotIndex = start + count;
swap(arr[pivotIndex], arr[start]); // defined in <iostream>
// Sorting left and right parts of the pivot element
int i = start, j = end;
while (i < pivotIndex && j > pivotIndex) {
while (arr[i] <= pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i < pivotIndex && j > pivotIndex) {
swap(arr[i++], arr[j--]);
}
}
return pivotIndex;
}
void quickSort(int arr[], int start, int end) {
// base case
if (start >= end)
return;
// partitioning the array
int p = partition(arr, start, end);
// Sorting the left part
quickSort(arr, start, p - 1);
// Sorting the right part
quickSort(arr, p + 1, end);
}
Modify the given quicksort as a C++ template, and write a main function to test it with the Time class. You need to overload some relational operators (< <= > >= ==) to make it work. You are allowed to modify anything you like.
6
4:20:38 4:26:0 3:49:9 9:34:01 5:13:58 3:49:22
3:49:9 3:49:22 4:20:38 4:26:0 5:13:58 9:34:1