Quick Sort

R## Problem statement Quick Sort is a Divide and Conquer algorithm. It is the third sorting algorithm that we are going to discuss to perform sorting of an array of numbers.

Solution: Recursive approach

This sorting algorithm picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of Quick Sort that pick the pivot in different ways such as:

• Always picking the first element as pivot
• Always picking the last element as the pivot (implemented below)
• Picking a random element as pivot
• Picking the median as pivot

The main focus of this sorting algorithm is the partition process. The goal of the partition process is that when given an array and an element x of the array as the pivot, it should put x at its correct position in a sorted array and 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. For this lesson, we will pick the last element as pivot. To achieve this partitioning, the following process is followed:

• A pointer is fixed at the pivot element. The pivot element is compared with the elements beginning from the first index. If the element greater than the pivot element is reached, a second pointer is set for that element.
• Now, the pivot element is compared with the other elements (a third pointer). If an element smaller than the pivot element is reached, the smaller element is swapped with the greater element found earlier.

Let us visualize the above steps for one iteration.