Quicksort (Grokking Algorithms)
Tags: computerscience, quicksort, sorting, algorithms
Published: 2023-09-29 07:02:48

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.

![0 Array & 1 Array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iwh2h99w0jlihuizbwqq.png)


## Array Containing 2 Elements

An array containing two Elements is also easy to sort.

![2 Array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/f7jxl0v6a2prxqpyqcb0.png)

## 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.

![3 Array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q8lgvyhuga46wxjt2yp5.png)

- 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.)

![pivot](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l6bckbn415ozovgyghyy.png)

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

![partioning](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/b6aqx14of9nt2dn9k5il.png)


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] ```

![sorted 3 Array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9o8odjgx4op0bdvyf6ce.png)

- 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

![4 Array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/em8yta6znqi6cw77y2pu.png)

- We choose **33** as the pivot element.

![pivot33](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5vv2s9cvlob7mwzjq4jk.jpg)

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

![sub-array sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y6zurmxdouw6lwcdhz6o.png)

- 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 :

![5 Array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/d6oxbt04mj8noz6sh5c8.png)

Different Pivot Elements :

![Different Pivots](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3hf73yrhimp5al650ue2.jpg)

**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 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0tmzhcs7lglow0mda9e5.jpg)

Example 2)

![Example 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hby6puxypkc9jewabtke.jpg)

## 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])
```