Quick Sort!!. DSA - #1
Tags: beginners, tutorial, algorithms, python
Published: 2022-06-14 05:24:29

## Quick Sort
---


Like Merge sort, Quick Sort uses a divide and conquer algorithm. It picks a pivot point and divides the whole array around that point. After dividing the whole array around that point we will have two parts of the array the left and the right part. Now we have to repeat the whole process for both halves i.e pick the pivot point and divide the whole array around that point. Repeating these steps will lead to a point where the array will contain only one element and that is our base case i.e when the length of the array became 1 we simply return the array.


## How to find Pivot Index.


A pivot number is defined as the number whose left side is the smaller and right side is greater.

For example in arr = [2, 1, 3, 6, 4] 3 is pivot point. Because all the elements before 3 are smaller than 3 and all the numbers after 3 are greater.

To divide the array around the pivot point we need to find the pivot index i.e index of the pivot point.

For example if arr = [2, 1, 3, 6, 4]. Here pivot number = 3 and it's index = 2. After dividing the array around 3 arr_left = [2, 1, 3] and arr_right = [6, 4]

In this algorithm, we need to select a number and make it a pivot point i.e we need to put it in its right position. We can select any number we want, but for simplicity, I am going to choose the 1st element i.e element at index 0.

```Python
def pivot(arr: list) -> int:
    pivot_count, length = 0, len(arr)
    for i in range(1, length):
        if arr[0] > arr[i]:
            pivot_count += 1
            arr[i], arr[pivot_count] = arr[pivot_count], arr[i]
    arr[0], arr[pivot_count] = arr[pivot_count], arr[0]
    return pivot_count
```


In above code pivot\_count returns the pivot index.


## Logic


How to put the selected number in the right place. Suppose we have `arr = [4, 8, 2, 1, 5, 7, 6, 3]`. Let's choose 4 as our number. 4 will be in its right place if all the element left to 4 is smaller and all the elements right to 4 is greater. Therefore the length of the left side of 4 = total number which is smaller than 4 and hence the index of 4 i.e pivot\_index = total number which is smaller than 4 (we didn't add 1 because the index start from 0).


Therefore final array will become `arr = [3, 2, 1, 4, 8, 5, 7, 6]`


## Dry Run


Let's dry run the above code to understand it much better.


Let `arr = [4, 8, 2, 1, 5, 7, 6, 3]`

1. Pivot\_count = 0, length = 8

2. Beginning of Loop. Our pivot number is 4 (as I mentioned above I am going to choose the first element). We don't want to compare 4 with 4 i.e arr\[0\] with arr\[0\] that's why I am starting loop from index 1.

3. First iteration: 4 > 8 ---> false.


`pivot_count = 0`

4. Second iteration: 4 > 2 ---> true. Therefore we increment the pivot\_count and now we are ready to swap. Notice I am incrementing pivot\_count before swapping. This is because I want to swap with the number which is the first largest number than 4. Now the `arr = [4, 2, 8, 1, 5, 7, 6, 3]`


`pivot_count = 1`

5. Third iteration: 4 > 1 ---> true. Therefore we increment the pivot\_count and swap the two number.


`pivot_count = 2 arr = [4, 2, 1, 8, 5, 7, 6, 3]`

6. Fourth iteration: 4 > 5 ---> false.


pivot\_count = 2 arr = \[4, 2, 1, 8, 5, 7, 6, 3\]

7. Fourth iteration: 4 > 7 ---> false.


pivot\_count = 2 arr = \[4, 2, 1, 8, 5, 7, 6, 3\]

8. Fourth iteration: 4 > 6 ---> false.


pivot\_count = 2 arr = \[4, 2, 1, 8, 5, 7, 6, 3\]

9. Third iteration: 4 > 3 ---> true. Therefore we increment the pivot\_count and swap the two number.


`pivot_count = 3 arr = [4, 2, 1, 3, 5, 7, 6, 8]`

10. Now the loop will break and we put the 4 at index = pivout\_count


`arr = [3, 2, 1, 4, 5, 7, 6, 8]`


## Implementing Quick sort


What we need to do


Take the first element of the array and make it pivot i.e place it in the right position. Now we have one element sorted. We divide the pivot about this point and find the pivot in the left and right half respectively. We will continue this process until the length of an array became 1.

```Python
def quick_sort(arr: list) -> list:
    length = len(arr)
    if length <= 1:
        return arr
    mid = pivot(arr)
    return quick_sort(arr[:mid + 1]) + quick_sort(arr[mid + 1:])
```


Let's dry run the program to understand it much better.


Let `arr = [4, 8, 2, 1, 5, 7, 6, 3]`


We will return the arr if the length of arr <= 1. This will be our base case


‏‏‎ ‎


1 ---> arr = \[4, 8, 2, 1, 5, 7, 6, 3\]


mid = 3 arr = \[3, 2, 1, 4, 5, 7, 6, 8\]


quick\_sort(\[3, 2, 1, 4\]) + quick\_sort(\[5, 7, 6, 8\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/90aae09f-5bf2-4d6e-b3e0-4c575769a8df.png)](undefined)


‏‏‎ ‎


1->2 ---> arr = \[3, 2, 1, 4\]


mid = 2 arr = \[1, 2, 3, 4\]


quick\_sort(\[1, 2, 3\]) + quick\_sort(\[4\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/f278b169-acd2-40fb-b9c5-703029dfaafa.png)](undefined)


‏‏‎ ‎


1->2->3 ---> arr = \[1, 2, 3\]


mid = 0 arr = \[1, 2, 3\]


quick\_sort(\[1\]) + quick\_sort(\[2, 3\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/abc82216-b039-416b-b8a1-8e76ba772abc.png)](undefined)


‏‏‎ ‎


1->2->3->4 ---> arr = \[1\]


returns \[1\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/7e5d39c2-a90a-4643-8e25-83e9555ae4c3.png)](undefined)


‏‏‎ ‎


1->2->3 ---> arr = \[1, 2, 3\]


mid = 0 arr = \[1, 2, 3\]


\[1\] + quick\_sort(\[2, 3\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/abc82216-b039-416b-b8a1-8e76ba772abc.png)](undefined)


1->2->3->4 ---> arr = \[2, 3\]


mid = 0 arr = \[2, 3\]


quick\_sort(\[2\]) + quick\_sort(\[3\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/d96d308c-d54b-4a16-8171-256e001e88f6.png)](undefined)


‏‏‎ ‎


1->2->3->4->5 ---> arr = \[2\]


returns \[2\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/501683f5-b215-42f1-9e90-88b03320490a.png)](undefined)


‏‏‎ ‎


1->2->3->4 ---> arr = \[2, 3\]


mid = 0 arr = \[2, 3\]


\[2\] + quick\_sort(\[3\])


‏‏‎ ‎

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/d96d308c-d54b-4a16-8171-256e001e88f6.png)](undefined)


1->2->3->4->5 ---> arr = \[3\]


returns \[3\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/bda407f8-44a6-4e91-adea-87e648a9ef49.png)](undefined)


‏‏‎ ‎


1->2->3->4 ---> arr = \[2, 3\]


mid = 0 arr = \[2, 3\]


\[2\] + \[3\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/d96d308c-d54b-4a16-8171-256e001e88f6.png)](undefined)


1->2->3 ---> arr = \[1, 2, 3\]


mid = 0 arr = \[1, 2, 3\]


\[1\] + \[2, 3\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/abc82216-b039-416b-b8a1-8e76ba772abc.png)](undefined)


1->2 ---> arr = \[3, 2, 1, 4\]


mid = 2 arr = \[1, 2, 3, 4\]


\[1, 2, 3\] + quick\_sort(\[4\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/c198e083-387f-4ae8-a66d-77bcb8fdaf94.png)](undefined)


1->2->3 ---> arr = \[4\]


returns \[4\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/a5536d27-702f-4d5e-9801-b3b4dbbbd499.png)](undefined)


‏‏‎ ‎


1->2 ---> arr = \[3, 2, 1, 4\]


mid = 2 arr = \[1, 2, 3, 4\]


\[1, 2, 3\] + \[4\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/c198e083-387f-4ae8-a66d-77bcb8fdaf94.png)](undefined)


1 ---> arr = \[4, 8, 2, 1, 5, 7, 6, 3\]


mid = 3 arr = \[3, 2, 1, 4, 5, 7, 6, 8\]


\[1, 2, 3, 4\] + quick\_sort(\[5, 7, 6, 8\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/b0434a73-41a0-4f3e-bcde-9f62ec7c3203.png)](undefined)


‏‏‎ ‎


1->2---> arr = \[5, 7, 6, 8\]


mid = 0 arr = \[5, 7, 6, 8\]


quick\_sort(\[5\]) + quick\_sort(\[7, 6, 8\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/31e8983a-4d33-4caf-8fc9-f3476813dcb3.png)](undefined)


‏‏‎ ‎


1->2->3---> arr = \[5\]


returs \[5\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/10a1f6d7-19af-42ba-a079-e3bf41c94f45.png)](undefined)


‏‏‎ ‎


1->2---> arr = \[5, 7, 6, 8\]


mid = 0 arr = \[5, 7, 6, 8\]


\[5\] + quick\_sort(\[7, 6, 8\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/31e8983a-4d33-4caf-8fc9-f3476813dcb3.png)](undefined)


1->2->3---> arr = \[7, 6, 8\]


mid = 1 arr = \[6, 7, 8\]


quick\_sort(\[6, 7\]) + quick\_sort(\[8\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/22ec627f-c73e-4e90-908e-a31b68296267.png)](undefined)


‏‏‎ ‎


1->2->3->4---> arr = \[6, 7\]


mid = 0 arr = \[6, 7\]


quick\_sort(\[6\]) + quick\_sort(\[7\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/fa919455-414f-425a-b3dd-9bd27a4d2e78.png)](undefined)


‏‏‎ ‎


1->2->3->4->5---> arr = \[6\]


returns \[6\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/6e57a219-7c60-411c-ac30-94e212e2f832.png)](undefined)


‏‏‎ ‎


1->2->3->4---> arr = \[6, 7\]


mid = 0 arr = \[6, 7\]


\[6\] + quick\_sort(\[7\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/fa919455-414f-425a-b3dd-9bd27a4d2e78.png)](undefined)


1->2->3->4->5---> arr = \[7\]


returns \[7\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/71ab8024-4872-4911-b448-c826bf7eb752.png)](undefined)


‏‏‎ ‎


1->2->3->4---> arr = \[6, 7\]


mid = 0 arr = \[6, 7\]


\[6\] + \[7\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/fa919455-414f-425a-b3dd-9bd27a4d2e78.png)](undefined)


1->2->3---> arr = \[7, 6, 8\]


mid = 1 arr = \[6, 7, 8\]


\[6, 7\] + quick\_sort(\[8\])

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/22ec627f-c73e-4e90-908e-a31b68296267.png)](undefined)


1->2->3->4---> arr = \[8\]


returns \[8\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/72249739-093b-42a6-be10-c3b5ebe57ba3.png)](undefined)


‏‏‎ ‎


1->2->3---> arr = \[7, 6, 8\]


mid = 1 arr = \[6, 7, 8\]


\[6, 7\] + \[8\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/22ec627f-c73e-4e90-908e-a31b68296267.png)](undefined)


1->2---> arr = \[5, 7, 6, 8\]


mid = 0 arr = \[5, 7, 6, 8\]


\[5\] + \[6, 7, 8\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/356853ee-b7b7-4415-8a43-273df6b3c33e.png)](undefined)


‏‏‎ ‎


1 ---> arr = \[4, 8, 2, 1, 5, 7, 6, 3\]


mid = 3 arr = \[3, 2, 1, 4, 5, 7, 6, 8\]


\[1, 2, 3, 4\] + \[5, 6, 7, 8\]

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/capture_markup_images/db83863996f84552b3af9a5f0853cfe6/1736a463-5906-4cec-8bd4-2aa7247119f0.png)](undefined)

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/image_upload/db83863996f84552b3af9a5f0853cfe6/3027d0a4-1984-4482-b3c7-e01e34cfc9e6.png)](undefined)

[![Quick Sort image](https://slid-users-assets-v1-mumbai.s3.ap-south-1.amazonaws.com/public/image_upload/db83863996f84552b3af9a5f0853cfe6/7ee5ace1-e8d3-45f8-b169-692d0e7f81a5.png)](undefined)


final ans = \[1, 2, 3, 4, 5, 6, 7, 8\]

Final code
```Python
def pivot(arr: list) -> int:
    pivot_count, length = 0, len(arr)
    for i in range(1, length):
        if arr[0] > arr[i]:
            pivot_count += 1
            arr[i], arr[pivot_count] = arr[pivot_count], arr[i]
    arr[0], arr[pivot_count] = arr[pivot_count], arr[0]
    return pivot_count


def quick_sort(arr: list) -> list:
    length = len(arr)
    if length <= 1:
        return arr
    mid = pivot(arr)
    return quick_sort(arr[:mid + 1]) + quick_sort(arr[mid + 1:])


print(quick_sort([4, 8, 2, 1, 5, 7, 6, 3]))

```
‏‏‎ ‎