3-Wege-Schnellsortierung (Problem mit niederländischer Flagge)

Hier sehen wir die Schnellsortiertechnik, aber wir verwenden die Drei-Wege-Schnellsortierung. Die grundlegende Quicksort-Technik findet lediglich ein Element als Pivot, unterteilt dann das Array um den Pivot herum und führt anschließend eine Rekursion auf dem linken und rechten Subarray des Pivots durch.

Die Drei-Wege-Schnellsortierung ist ähnlich, besteht jedoch aus drei Teilen. Das Array arr[1 bis n] ist in drei Teile unterteilt.

• arr[1 bis 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

Schnellsortierung (arr, links, rechts) – Die chinesische Übersetzung von

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

Beispiel

lautet:

Beispiel

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

Ausgabe

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

Das obige ist der detaillierte Inhalt von3-Wege-Schnellsortierung (Problem mit niederländischer Flagge). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!