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.

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.