## 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;
}
```