यहां हम क्विकसॉर्ट तकनीक देखेंगे लेकिन हम थ्री-वे क्विकसॉर्ट का उपयोग करेंगे। मूल क्विकसॉर्ट तकनीक सिर्फ एक तत्व को पिवट के रूप में ढूंढ रही है, फिर पिवट के चारों ओर सरणी को विभाजित करें, उसके बाद, पिवट के बाएं और दाएं उप सरणी के लिए पुनरावृत्ति करें।
थ्री-वे क्विकॉर्ट समान है, लेकिन तीन खंड हैं। सरणी गिरफ्तारी [1 से n] तीन भागों में विभाजित है।
- गिरफ्तार[1 से मैं]
- गिरफ्तारी[i + 1, j]
- गिरफ्तारी[j + 1, n]
एल्गोरिदम
विभाजन (गिरफ्तारी, बाएँ, दाएँ, i, j) -
begin if right – 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 – 1 j := mid end
Quicksort (गिरफ्तारी, बाएँ, दाएँ) -
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
उदाहरण
#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);
} आउटपुट
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