Bhav Kushwaha

Posted on

# Quicksort (Grokking Algorithms)

Quicksort is a sorting algorithm which is frequently used in real life.

Let's explore different senarios where we can implement Quicksort:-

## Array Containing 0 or 1 Element

Empty arrays and single element array will not need to be sorted. The base case will be the result for them.

## Array Containing 2 Elements

An array containing two Elements is also easy to sort.

## Array Containing 3 Elements

In order to sort an array containing three elements, we need to break it down to the base case using the Divide & Conquer approach.

• First pickup an element from the array, called the pivot.

(Will discuss how to pickup a good pivot later, for now lets take the first element as pivot.)

• Now find the elements smaller than the pivot and the elements larger than the pivot.

This is called Partioning. You have :
1) A sub-array of all the numbers less than the pivot
2) The pivot
3) A sub-array of all the numbers more than the pivot

• The two two sub-arrays obtained are not neccessarily sorted. Therefore, we come come across 2 cases:

1) If the sub-arrays are sorted then we can combine the whole thing

`left array + pivot + right array = Sorted Array`

2) If the sub-arrays are not sorted then we have to sort them.

We can do that by applying quicksort on the sub-arrays (since we know the results of sorting an array containing 0 or 1 elements or 2 elements array).

`quicksort([15, 10]) + [33] + quicksort([])`

`> [10, 15, 33]`

• Similary, we can choose any element of the array as pivot and apply the above steps to obtain a sorted array.

## Array Containing 4 Elements

Suppose we are given an array

• We choose 33 as the pivot element.

• The left sub-array has 3 elements. We had already seen how to sort an array of three elements: call quicksort on it recursively.

• Therefore, we can now easily repeat the steps learned above to sort the 4 elements array.

## Sorting an array of 5 elements (Different Pivots)

Given Array :

Different Pivot Elements :

Notice: all the sub-arrays of any pivot lies between 0-4 elements, and we can easily sort them as seen in the above examples.

Example 1)

Example 2)

## The Code for Quicksort

``````def quicksort(array):

if len(array) < 2:
return array
# Base Case: arrays with 0 or 1 elements

else:
pivot = array[0]
# Recursive Case

less = [ i for i in array [1:] if i <= pivot]
# Sub-array to the left of the pivot

greater = [ i for i in array [1:] if i > pivot]
# Sub-array to the right of the pivot

return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])
``````