3-way quick sort (Dutch flag problem)

Here we will see the quick sort technique but we will use three way quick sort. The basic quicksort technique just finds an element as the pivot, then partitions the array around the pivot, and after that, recurses on the left and right subarrays of the pivot.

Three-way quick sort is similar, but has three parts. The array arr[1 to n] is divided into three parts.

• arr[1 to i]
• arr[i 1, j]
• arr[j 1, n]

Algorithm

partition(arr, left, right, i, j) −

begin
   if right &ndash; left <= 1, then
      if arr[right] < arr[left], then
         swap arr[right] and arr[left]
      i := left
      j := right
      return
   end if
   mid := left, pivot = arr[right]
   while mid <= right, do
      if arr[mid] < pivot, then
         swap arr[left], arr[mid]
         increase left and mid by 1
      else if arr[mid] = pivot, then increase mid by 1
      else
         swap arr[mid], arr[right]
         decrease right by 1
   done
   i := left &ndash; 1
   j := mid
end

quicksort(arr, left, right) - Chinese of

begin
   if left >= right, then
      return
   end if
   define i and j
   partition(arr, left, right, i, j)
   quicksort(arr, left, i)
   quicksort(arr, j, right)
end

Example

Translates to:

Example

#include<iostream>
#include<vector>
using namespace std;
void partition(int arr[], int left, int right, int &i, int &j) {
   if (right - left <= 1) {
      if (arr[right] < arr[left])
         swap(arr[right], arr[left]);
      i = left;
      j = right;
      return;
}
int mid = left;
int pivot = arr[right];
while (mid <= right) {
   if (arr[mid]<pivot)
      swap(arr[left++], arr[mid++]);
      else if (arr[mid]==pivot)
         mid++;
      else if (arr[mid] > pivot)
         swap(arr[mid], arr[right--]);
   }
   i = left-1;
   j = mid;
}
void quicksort(int arr[], int left, int right) {
   if (left >= right) //1 or 0 elements
      return;
   int i, j;
   partition(arr, left, right, i, j);
   quicksort(arr, left, i);
   quicksort(arr, j, right);
}
void display(int arr[], int n) {
   for (int i = 0; i < n; ++i)
   cout << " " << arr[i];
   cout << endl;
}
int main() {
   int a[] = {4, 9, 4, 3, 1, 9, 4, 3, 9, 4, 3, 1, 4};
   int n = sizeof(a) / sizeof(int);
   display(a, n);
   quicksort(a, 0, n - 1);
   display(a, n);
}

Output

4 9 4 3 1 9 4 3 9 4 3 1 4
1 1 3 3 3 4 4 4 4 4 9 9 9

The above is the detailed content of 3-way quick sort (Dutch flag problem). For more information, please follow other related articles on the PHP Chinese website!