Quicksort algorithm using Hoare’s partitioning scheme

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 ² ) when the 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:

• In-place vs out-of-place algorithms
• Construction of an Expression Tree
• Minimum Edit Distance
• The Stock Span Problem
• Print Triangle Using * Character
• Diameter of a Binary Tree
• Subset Sum Problem
• Maximum size square sub-matrices with all 1’s
• Merge Sort for Linked Lists