Quicksort using Dutch National Flag Algorithm

Posted in

Quicksort using Dutch National Flag Algorithm
vinaykhatri

Vinay Khatri
Last updated on March 29, 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]);
        }
    }

    Output

    1
    1
    2
    2
    2
    4
    6

    People are also reading:

    Leave a Comment on this Post

    0 Comments