Similar to the Merge Sort algorithm, the Quick Sort algorithm is a Divide and Conquer algorithm. It initially selects an element as a pivot element and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
Always pick the first element as a pivot (implemented below).
Always pick the last element as the pivot.
Pick a random element as a pivot.
Pick median as a pivot.
Details
The key process in quickSort is the partition() process. The aim of the partition() function is to receive an array and an element x of the array as a pivot, put x at its correct position in a sorted array and then put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time i.e. Big O(n) .
Summary
Similar to the Merge Sort algorithm, the Quick Sort algorithm is a Divide and Conquer algorithm. It initially selects an element as a pivot element and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
Always pick the first element as a pivot (implemented below). Always pick the last element as the pivot. Pick a random element as a pivot. Pick median as a pivot.
Details
The key process in quickSort is the partition() process. The aim of the partition() function is to receive an array and an element x of the array as a pivot, put x at its correct position in a sorted array and then put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time i.e. Big O(n) .
References
[https://www.geeksforgeeks.org/cpp-program-for-quicksort/]
Checks