Implement Quick Sort using Python and C++ & Time complexity

quick-sort-algorithm
Spread the love

Quicksort is a divide-and-conquer algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays. According to whether they are less than or greater than the pivot.

In this tutorial, I will show you how to implement the Quicksort algorithm using C++. I will also discuss the time complexity of Quicksort. As I told you before, Quicksort is a divide and conquer algorithm. That means quicksort divides the array into many partitions by pivot value.

Divide-and-conquer algorithm

 In computer science, divide and conquer is an algorithm design paradigm. The divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

quick-sort-algorithm
quick-sort-algorithm

Well, Implement the quicksort algorithm you have to define two functions. One is partition and another one is quicksort. The partition function is the backbone of the quicksort algorithm. Let’s have a look below code.

Read More: Implement doubly linked list using OOP in Python

The partition function in C++

int partition(int arr[], int lb, int ub)
{
    int pivot = arr[lb];
    int start = lb;
    int end = ub;

    while (start < end)
    {
        while (arr[start] <= pivot)
        {
            start++;
        }
        while (arr[end] > pivot)
        {
            end--;
        }
        if (start < end)
        {
            swap(arr[start], arr[end]);
        }
    }

    swap(arr[lb], arr[end]);

    return end;
}

The partition function in Python

def partition(arr, lb, ub):
    pivot = arr[lb]
    start = lb
    end = ub

    while start < end:
        while arr[start] <= pivot:
            start += 1
        while arr[end] > pivot:
            end -= 1
        if start < end:
            temp = arr[start]
            arr[start] = arr[end]
            arr[end] = temp
    temp = arr[lb]
    arr[lb] = arr[end]
    arr[end] = temp

    return end

How partition function works

Well, now I will explain to you how works the partition function. You can see the partition function takes three parameters. The first parameter is an array the second parameter is lower bound and the third parameter is the upper bound. Now a question arises, What is the lower and upper bound?

The lower bound is the first index of this array and the upper bound is the last index of this array. Well, then take a variable that will store the pivot value. Now a question arises, What is pivot value and how do I take a value that is a pivot?

You can take any value as pivot value. But remember, according to the pivot value your implementation will different. I took the pivot value as the array’s first value. Which is the lower bound. arr[lb]

Well, now you have to take two variables to store the value of upper and lower bound. I take the variable’s name as start and end.

Now take a while loop. It will execute until the start value crosses the end value. Inside the while loop takes another while loop. this loop’s condition is array’s current start index’s value is greater and equal to the pivot value. If the condition is fulfilled then increase the start value one.

After the while loop, you have to define another while loop. Which condition is array’s current start index’s value is lower than the pivot value. If the condition is fulfilled then decrease the end value one.

After the while loop, check a condition that the start is greater than the end. If this condition is fulfilled then swap the value of the array’s start index with the array’s end index.

Well, after the break first while loop then swaps the value of the array’s lower bound index with the array’s end index. then return the end value.

Well, now you have to define the quicksort function. The quicksort function takes three parameters like the partition function. Follow the quicksort function then I will explain.

The Quicksort function in C++

void quick_sort(int arr[], int lb, int ub)
{
    if (lb < ub)
    {
        int loc = partition(arr, lb, ub);
        quick_sort(arr, lb, loc - 1);
        quick_sort(arr, loc + 1, ub);
    }
}

The Quicksort function in Python

def quick_sort(arr, lb, ub):
    if lb < ub:
        loc = partition(arr, lb, ub)
        quick_sort(arr, lb, loc - 1)
        quick_sort(arr, loc+1, ub)

How Quicksort function works

The quicksort function is a simple function. Inside this function first, check the lower bound is greater than the upper bound? Then call the partition function that returns the partition index and store the index in a variable. After that call again the quicksort function two times. The first time the lower bound will initial lower bound the upper bound will the loc – 1. The second time the lower bound will be the loc + 1 and the upper bound will be the initial upper bound.

Read More : Implement a Binary tree with inOrder postOrder preOrder

Full code of the quicksort in C++

#include <bits/stdc++.h>
using namespace std;

void print_array(int arr[], int n)
{
    cout << endl;

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
}

int partition(int arr[], int lb, int ub)
{
    int pivot = arr[lb];
    int start = lb;
    int end = ub;

    while (start < end)
    {
        while (arr[start] <= pivot)
        {
            start++;
        }
        while (arr[end] > pivot)
        {
            end--;
        }
        if (start < end)
        {
            swap(arr[start], arr[end]);
        }
    }

    swap(arr[lb], arr[end]);

    return end;
}
void quick_sort(int arr[], int lb, int ub)
{
    if (lb < ub)
    {
        int loc = partition(arr, lb, ub);
        quick_sort(arr, lb, loc - 1);
        quick_sort(arr, loc + 1, ub);
    }
}
int main()
{
    int arr[] = {5, 30, 50, 15, 20, 1, 20, 10, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    print_array(arr, n);
    quick_sort(arr, 0, n - 1);
    print_array(arr, n);

    return 0;
}

Full code of Quicksort in Python

def partition(arr, lb, ub):
    pivot = arr[lb]
    start = lb
    end = ub

    while start < end:
        while arr[start] <= pivot:
            start += 1
        while arr[end] > pivot:
            end -= 1
        if start < end:
            temp = arr[start]
            arr[start] = arr[end]
            arr[end] = temp
    temp = arr[lb]
    arr[lb] = arr[end]
    arr[end] = temp

    return end


def quick_sort(arr, lb, ub):
    if lb < ub:
        loc = partition(arr, lb, ub)
        quick_sort(arr, lb, loc - 1)
        quick_sort(arr, loc+1, ub)


arr = [5, 1, 200, 15, 10, 9, 6, -1]
n = len(arr) - 1
quick_sort(arr, 0, n)

print(arr)

Time Complexity

Now I will discuss with you the time complexity of QuickSort. The best and average complexity of quicksort is n*log(n) and the worst time complexity is n^2. Now a question arises, Why the worst complexity is n^2?

As I told you before the quicksort follows the divide and conquer strategy. That’s why every iteration the array divides two partitions. If the array is already sorted then the partition will return the end value sequentially from start to end. That means it takes O^2 time complexity. Hope this tutorial will help you.

Read More: Laravel Application Deploy in Heroku Cloud Platform

Learn Laravel


Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published. Required fields are marked *