Quicksort
This is an in place sort algorithm which works on divide and conquer technique. The idea is pretty simple
- pick an element and divide the array such that one half of element are lesser and the other half has elements greater or equal to this element picked. This element is called the pivot.
- Repeat this process for the two halves thus formed until there’s two halves with one element each.
Code
The code below also counts the number of comparisons done and depending on whether we want increasing or decreasing order.
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define INVALID_IDX (-2)
#define PARTITION_DONE (-1)
#define ARRAY_SIZE(X) (sizeof(X) / sizeof(X[0]))
#define PRINT_ARRAY(X) \
for (int i = 0 ;i < ARRAY_SIZE(X); i += 1) {\
std::cout<<#X<<"["<<i<<"]="<<X[i]<<"\n"; \
}
#define SWAP(X,Y) \
({ \
int temp = X;\
X = Y; \
Y = temp;\
})
int partition(int a[], int start,
int len, bool descending = false, int *comparisons = nullptr)
{
int pivot_idx = start - 1;
int pivot = a[len - 1];
for (int j = start; j < len - 1; j += 1) {
if (descending) {
if (comparisons != nullptr)
(*comparisons)++;
if (a[j] > pivot) {
pivot_idx += 1;
SWAP(a[pivot_idx], a[j]);
}
} else {
if (comparisons != nullptr)
(*comparisons)++;
if (a[j] < pivot) {
pivot_idx += 1;
SWAP(a[pivot_idx], a[j]);
}
}
}
pivot_idx += 1;
SWAP(a[pivot_idx], a[len - 1]);
return pivot_idx;
}
int quicksort(int arr[], int start, int len,
bool descending = false)
{
int comparisons = 0;
if (start < 0 || start >= len)
return comparisons;
int p = partition(arr, start, len, descending, &comparisons);
if (p == INVALID_IDX) {
std::cout<< "Invalid index " << p << "\n";
return comparisons;
}
comparisons += quicksort(arr, 0, p, descending);
comparisons += quicksort(arr, p + 1, len, descending);
return comparisons;
}
#define PRINT_AND_SORT_ARRAY(arr) \
({\
std::cout<<"Unsorted array is \n";\
std::cout<<"-------------\n";\
PRINT_ARRAY(arr); \
int __comp = quicksort(arr, 0, ARRAY_SIZE(arr)); \
std::cout<<"Sorted array \n"; \
std::cout<<"---------------\n"; \
std::cout<<"Comparisons done = "<<__comp<<"\n";\
PRINT_ARRAY(arr); \
})
int main(int argc, char *argv[])
{
int arr1[] = {12, 20, 22, 16, 25, 18, 8, 10, 6, 15};
int arr2[] = {6, 8, 10, 12, 15, 16, 18, 20, 22, 25};
PRINT_AND_SORT_ARRAY(arr1);
std::cout<<"Array 2"<<"\n";
std::cout<<"=============\n";
PRINT_AND_SORT_ARRAY(arr2);
return 0;
}