3방향 퀵 정렬(네덜란드 국기 문제)

여기에서는 빠른 정렬 기술을 볼 것이지만 우리는 3방향 빠른 정렬을 사용할 것입니다. 기본 퀵 정렬 기술은 피벗으로 요소를 찾은 다음 피벗 주위에 배열을 분할하고 그 후 피벗의 왼쪽 및 오른쪽 하위 배열에서 반복됩니다.

3방향 퀵 정렬은 비슷하지만 세 부분으로 구성됩니다. arr[1 to n] 배열은 세 부분으로 나뉩니다.

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

빠른 정렬(arr, left, right) -

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

의 중국어 번역은 다음과 같습니다.

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

위 내용은 3방향 퀵 정렬(네덜란드 국기 문제)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!