Explain what the quicksort algorithm is and how you would implement it?
TLDR
Quicksort is a divide and conquer algorithm that quickly sorts items by picking an element as the pivot and partitions the array around the chosen pivot.
quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is now
at right place */
pi = partition(arr, low, high);
quickSort(arr, low, pi — 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
Further Explained
Quicksort is a divide and conquer algorithm that quickly sorts items by picking an element as the pivot and partitions the array around the chosen pivot. The speed of the algorithm is very dependent on how the pivot is chosen so there are many ways to implement it. Some of the common ways to decide a pivot is:
- Always the first element is the pivot
- Always pick the last element
- Pick a random element as the pivot.
- Choose the median as the pivot
Quicksort works by finding a partition x and putting it in its correct position in the sorted array. Then puts all the elements smaller than x before x and all the elements larger than x after it.
More Reading
