# Quicksort using Dutch National Flag Algorithm

Posted in

Vinay Khatri
Last updated on September 21, 2024

## 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 2 ) 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]);
}
}```

```1
1
2
2
2
4
6```