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

Quicksort

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.

Quicksort

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

Selection sort
Insertion Sort
Heapsort