# Quicksort | C++ Implementation

Like mergesort, **quicksort** also follows *divide-and-conquer* approach. The algorithm selects an element as *pivot*. The input array is **divided** into two subarrays. All elements in left subarray are less than pivot and all elements in right subarray are greater than pivot. These two subarrays are **sorted** independently and then **merged** to form a single sorted array.

**Related :** Merge Sort

In fig. (a) 4 is selected as the pivot and in fig. (b) all elements left to the 4 are smaller than it and all elements right to the 4 are greater than it and then these two subarrays are solved independently.

The pivot element 4 in fig. (b) ends up in the correct position in the array and so on all pivot elements ends up in the correct position.

# Implementation

`split`

function returns the index of pivot element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int split(int a[], int start_index, int end_index)
{
int x = a[end_index];
int i = start_index - 1;
for (int j = start_index; j < end_index; j++)
{
if (a[j] <= x)
{
i++;
std::swap(a[i], a[j]);//swap(a[i],a[j])
}
}
std::swap(a[i+1], a[end_index]);//swap(a[i+1],a[end_index])
return i+1;
}

Here is the operation of `split`

for the first time.

1
2
3
4
5
6
7
8
9

void quicksort(int a[], int start_index, int end_index)
{
if (start_index < end_index)
{
int mid_index = split(a, start_index, end_index);
quicksort(a, start_index, mid_index - 1);
quicksort(a, mid_index + 1, end_index);
}
}

### C++ Implementation of Quicksort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <algorithm>
int split(int a[], int start_index, int end_index)
{
int x = a[end_index];
int i = start_index - 1;
for (int j = start_index; j < end_index; j++)
{
if (a[j] <= x)
{
i++;
std::swap(a[i], a[j]);//swap(a[i],a[j])
}
}
std::swap(a[i+1], a[end_index]);//swap(a[i+1],a[end_index])
return i+1;
}
void quicksort(int a[], int start_index, int end_index)
{
if (start_index < end_index)
{
int mid_index = split(a, start_index, end_index);
quicksort(a, start_index, mid_index - 1);
quicksort(a, mid_index + 1, end_index);
}
}
int main()
{
int arr[8] = {2, 8, 7, 1, 3, 5, 6, 4};
quicksort(arr, 0, 7);
for (int i = 0; i < 8; i++)
{
std::cout << arr[i] << " ";
}
std::cout << "\n";
return 0;
}

View this code on Github

Get this post in pdf - Quicksort

Reference:

Introduction to Algorithms

The Algorithm Design Manual

Data Structures and Algorithms Made Easy

Competitive Programmer’s Handbook - Antti Laaksonen

### You may also like