Quicksort algorithm using Hoare’s partitioning scheme

Posted in

Quicksort algorithm using Hoare’s partitioning scheme

Vinay Khatri
Last updated on September 19, 2022

    Problem

    Implement QuickSort using Hoare’s partition scheme.

    Approach

    Hoare's Partition Scheme works by starting two indices at opposite ends and moving them toward each other until an inversion (a smaller value on the left side and a bigger value on the right side) is discovered. When an inversion is discovered, two values are switched and the procedure is repeated. If we change this scheme to pick the last element as pivot, then Quicksort may go into infinite recursion.To deal with a random pivot, just swap that random element with the first element and use the aforementioned algorithm.

    Comparison with Lomuto partition

    1. This scheme does three times fewer swaps than the Lomuto scheme on average.
    2. Creates efficient partitions even if all array elements are equal.
    3. The time complexity of both partitions schemes may degrade to O(N 2 ) when input array is sorted,

    C++ Programming

    #include <bits/stdc++.h>
    using namespace std;
    
    int partition(int arr[], int low, int high)
    {
          int pivot = arr[low];
          int i = low - 1, j = high + 1;
    
          while (true) {
    
                do {
                      i++;
                } while (arr[i] < pivot);
    
                do {
                      j--;
                } while (arr[j] > pivot);
    
                if (i >= j)
                      return j;
    
                swap(arr[i], arr[j]);
          }
    }
    
    
    void applyQuickSort(int arr[], int low, int high)
    {
          if (low < high) {
    
                int pi = partition(arr, low, high);
    
    
                applyQuickSort(arr, low, pi);
                applyQuickSort(arr, pi + 1, high);
          }
    }
    int main()
    {
          int arr[] = { 1, 5, 3, 4, 2};
          int n = sizeof(arr) / sizeof(arr[0]);
          applyQuickSort(arr, 0, n - 1);
          for (int i = 0; i < n; i++)
                printf("%d ", arr[i]);
          return 0;
    }

    Output

    1 2 3 4 5

    C Programming

    #include <stdio.h>
    void swap(int *a, int *b){
        int temp = *a;
        *a = *b;
        *b = temp;;
    }
    
    int partition(int arr[], int low, int high)
    {
          int pivot = arr[low];
          int i = low - 1, j = high + 1;
    
          while (1) {
    
                do {
                      i++;
                } while (arr[i] < pivot);
    
                do {
                      j--;
                } while (arr[j] > pivot);
    
                if (i >= j)
                      return j;
    
                swap(&arr[i], &arr[j]);
          }
    }
    
    void applyQuickSort(int arr[], int low, int high)
    {
          if (low < high) {
    
                int pi = partition(arr, low, high);
    
    
                applyQuickSort(arr, low, pi);
                applyQuickSort(arr, pi + 1, high);
          }
    }
    int main()
    {
          int arr[] = { 1, 5, 3, 4, 2};
          int n = sizeof(arr) / sizeof(arr[0]);
          applyQuickSort(arr, 0, n - 1);
          for (int i = 0; i < n; i++)
                printf("%d ", arr[i]);
          return 0;
    }
    

    Output

    1 2 3 4 5

    Python Programming

    def partition(arr, low, high):
    
          pivot = arr[low]
          i = low - 1
          j = high + 1
    
          while (True):
    
                i += 1
                while (arr[i] < pivot):
                      i += 1
    
                j -= 1
                while (arr[j] > pivot):
                      j -= 1
    
                if (i >= j):
                      return j
    
                arr[i], arr[j] = arr[j], arr[i]
    
    def applyQuickSort(arr, low, high):
    
          if (low < high):
    
                pi = partition(arr, low, high)
    
                applyQuickSort(arr, low, pi)
                applyQuickSort(arr, pi + 1, high)
    
    arr = [1, 5, 3, 4, 2]
    n = len(arr)
    applyQuickSort(arr, 0, n - 1)
    print(arr)

    Output

    [1, 2, 3, 4, 5]

    People are also reading:

    Leave a Comment on this Post

    0 Comments