Quick Sort

Algorithm

• Quicksort is a recursive algorithm. We choose a pivot in each step (for example, the first element of the array is chosen as the pivot).

• Partition the array into two pieces, with all elements smaller than the pivot moving to the left side and all items larger than the pivot being transferred to the right side. To do this, we follow the procedure below:

  * Choose pivot as the array’s first element.

  * Create two index variables, one for lower index and one for upper index.

  * Make the lower index the array’s second element and the upper index the array’s last element.

  * Increase the lower index until the value is less than the pivot.

  * Then, lower the top index till the value is greater than the pivot.

  * Then, swap the lower and upper index values.

  * Repeat the previous three stages until the upper index exceeds the lower value.

  * Finally, switch the pivot and upper index values.

• The left and right sub-arrays are then sorted independently.

• The whole array is sorted when the algorithm returns.

Let’s look at the illustration below to to how we can choose our pivot and divide the array.