Quicksort using Dutch National Flag Algorithm

Problem

Implement Quicksort using Dutch National Flag Algorithm

What’s the issue with the normal QuickSort Algorithm

If all elements are equal in an array, the left partition is empty after the pivot operation, and the right subarray only decreases by one. Therefore, the algorithm takes O(N ² ) time in the worst case.

How to improve on the above algorithm

We can use the concept of the Dutch National Flag Problem. We can separate the values into three parts: values equal to the pivot values less than the pivot and the values greater than the pivot. The pivot values are already sorted. Therefore, we just need to sort the less than and greater than pivot values recursively.

C++ Programming

#include <bits/stdc++.h>
using namespace std;
 
pair<int, int> partition(int arr[], int start, int end)
{
    int mid = start;
    int pivot = arr[end];
 
    while (mid <= end)
    {
        if (arr[mid] < pivot)
        {
            swap(arr[start], arr[mid]);
            ++start, ++mid;
        }
        else if (arr[mid] > pivot)
        {
            swap(arr[mid], arr[end]);
            --end;
        }
        else {
            ++mid;
        }
    }
 

    return make_pair(start - 1, mid);
}
 

void applyQuickSort(int arr[], int start, int end)
{

    if (start >= end) {
        return;
    }

    if (start - end == 1)
    {
        if (arr[start] < arr[end]) {
            swap(arr[start], arr[end]);
        }
        return;
    }

    pair<int, int> pivot = partition(arr, start, end); 
    applyQuickSort(arr, start, pivot.first); 
    applyQuickSort(arr, pivot.second, end);
}
 
int main()
{
    int arr[] = { 1, 2, 2, 1, 2, 6, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    applyQuickSort(arr, 0, n - 1);

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

Output

1 1 2 2 2 4 6

Python Programming

def swap (arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

def partition(arr, start, end):
 
    mid = start
    pivot = arr[end]
 
    while mid <= end:
 
        if arr[mid] < pivot:
            swap(arr, start, mid)
            start += 1
            mid += 1
 
        elif arr[mid] > pivot:
            swap(arr, mid, end)
            end -= 1
 
        else:
            mid += 1

    return start - 1, mid

def applyQuickSort(arr, start, end):

    if start >= end:
        return 

    if start - end == 1:
        if arr[start] < arr[end]:
            swap(arr, start, end)
        return
 
    x, y = partition(arr, start, end)
    applyQuickSort(arr, start, x)
 
    applyQuickSort(arr, y, end)
 
a = [1, 2, 2, 1, 2, 6, 4]
 
applyQuickSort(a, 0, len(a) - 1)

print(a)

Output

[1, 1, 2, 2, 2, 4, 6]

Java Programming

import java.util.Arrays;
 
class Pair
{
    private int x;
    private int y;
 
    Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
 
    public int getX() { return x; }
    public int getY() { return y; }
}
 
class Main
{
    public static void swap (int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    public static Pair partition(int[] arr, int start, int end)
    {
        int mid = start;
        int pivot = arr[end];
 
        while (mid <= end)
        {
            if (arr[mid] < pivot)
            {
                swap(arr, start, mid);
                ++start;
                ++mid;
            }
            else if (arr[mid] > pivot)
            {
                swap(arr, mid, end);
                --end;
            }
            else {
                ++mid;
            }
        }
 
        return new Pair(start - 1, mid);
    }
    public static void applyQuickSort(int[] arr, int start, int end)
    {

        if (start >= end) {
            return;
        }
 

        if (start - end == 1)
        {
            if (arr[start] < arr[end]) {
                swap(arr, start, end);
            }
            return;
        }
 

        Pair pivot = partition(arr, start, end);
 

        applyQuickSort(arr, start, pivot.getX());
 

        applyQuickSort(arr, pivot.getY(), end);
    }
 
    public static void main(String[] args)
    {
        int a[] = { 1, 2, 2, 1, 2, 6, 4 };
 
        applyQuickSort(a, 0, a.length - 1);
        for(int i=0;i<a.length;i++)
        System.out.println(a[i]);
    }
}

Output

1
1
2
2
2
4
6

People are also reading:

• Quicksort algorithm using Hoare’s partitioning scheme
• In-place vs out-of-place algorithms
• Problems solved using partitioning logic of Quicksort
• Find a Pair with the given sum in a BST
• Construction of an Expression Tree
• Create a mirror of an m–ary Tree
• Print a two-dimensional view of a Binary Tree
• Dutch National Flag Problem
• Maximum Sum Circular Subarray
• Find Maximum Subarray Sum