Quicksort Algorithm implemented the easy way : without cumbersome partitioning schemes

Quicksort Algorithm is one of the most common coding interview questions . This requires partitioning the given array/list . Most notably two partitioning schemes are used for this purpose viz: Hoare partition scheme and Lomuto partition scheme.

But the approach I am showing today doesn’t require any of them . This makes it easy to implement and saves a lot of time .

This solution make use of the random module of python which makes the task of partitioning a cakewalk . And it also makes the solution much more intuitive . So here goes the code .

quicksort using random module

So what the code does is :

first it selects a pivot using python’s random module . From python’s documentation :

Then it fills the list into 3 distinct lists :

1. equal : elements equal to pivot will be in this list
2. greater: elements greater than the pivot will be in this list
3. smaller: elements smaller than the pivot will be in this list

Finally, recursively generate the sorted list of both greater and smaller list . The equal list will remain fixed in its spot .

References:

https://docs.python.org/3/library/random.html