Quick Sort Working Mechanism

For Complete YouTube Video: Click Here

This class will try to understand the Quick Sort Working Mechanism.

In our previous class, we discussed the concepts of “Divide and Conquer” and the Merge Sort Algorithm.

Quick Sort Working Mechanism

Consider the sample array below to understand Quick Sort’s working mechanism.

The Quick Sort will have a partitioning algorithm to divide the array into sub-problems.

How does the Partitioning algorithm work?

The partitioning algorithm will consider one of the elements as a pivot element.

The array’s last element in our algorithm will be considered the pivot element.

In some algorithms, the array’s first element is considered the pivot element.

The partitioning algorithm will rearrange the elements so that the algorithm will bring the pivot element into its position.

The elements will be arranged as shown below if the partition algorithm is applied to the array.

After applying the partition algorithm, the elements less than or equal to the pivot element will be arranged on the left-hand side, and the elements greater than or equal to the pivot element will be arranged on the right-hand side.

Now, based on the index of the pivot element returned by the partitioning algorithm, the division to the sub-problems is made.

In our example, the pivot element is brought to index three, the exact position of the element after sorting.

The elements to the left of the pivot element are made into a sub-array, and the elements to the right are made into another sub-array, as shown below.

Similarly, the partition algorithm is applied to each sub-array till the array cannot be further divided.