Quick Sort

The quicksort algorithm is based on the divide and conquer technique. We start by:

1. Choosing one element as a pivot, and
2. Divide the array around it, such that all the elements on the left of the pivot are smaller than the it, and all the elements on the right are greater than the pivot.

How does Quick Sort work?

We will choose a random element from the array as a pivot and swap it with the last element of the array. We will also initialize two pointers left and right pointing to the start and end of the array.

Following this setup, we will rearrange the elements in such a way that the left side of the pivot contains elements that are the smaller and right side of the pivot contains elements that are greater than the pivot. We can accomplish this by following the steps below.

1. Move the left pointer to the right until it reaches a value greater or equal to the pivot. Afterward, stop the left pointer and move to step 2.
2. Move the right pointer to the left until it crosses the left pointer or finds a value less than the pivot.
3. Repeat the above steps until unless both pointers cross each other.

Let's take a look at the following illustrations to understand the approach better. In the figure below, we have chosen the pivot and swapped it with the last element of the array.

Now, we move the left and right pointer depending on the steps described above. If right < left, then we will swap them.

Now, we can see in the figure below that both pointers crossed each other. Given this, we will mark the element pointed by the left pointer as sorted.

We will then repeat the above steps by first choosing the pivot and swapping it with the last index and so on. At last, we will have all elements sorted.