Quick Sort

[wpdm_package id=’1367′]

Quick Sort is one of the fastest sorting algorithms used.

Steps:

1. Choose a pivot element. Here, we are choosing the middle element. It could even be randomly chosen.

2. Arrange the array elements such that all the elements greater than the pivot element shift to the right of the pivot element and the elements lesser than the pivot element is arranged to the left side of the pivot.

3. Repeat step to iteratively on either side of the pivot element.

Time Complexity : O(nlogn)

Example:

Suppose we have an array of elements:

4  7  2  1  5  9

Pivot element=2

1  2  4  7  5  9

Pivot element = 7 //only 1 is to the right side of the pivot, so we need to find pivot only for the right hand side

1  2  4  5  7  9

Pivot element = 4

1  2  4  5  7  9