यहां हम क्विकसॉर्ट तकनीक देखेंगे लेकिन हम थ्री-वे क्विकसॉर्ट का उपयोग करेंगे। बेसिक क्विकसॉर्ट तकनीक केवल एक एलिमेंट को पिवट के रूप में ढूंढती है फिर ऐरे को पिवट के चारों ओर पार्टीशन करती है, उसके बाद पिवट के बाएं और दाएं सब ऐरे के लिए पुनरावृत्ति करती है।
थ्री-वे क्विकसॉर्ट समान है, लेकिन इसमें तीन सेक्शन होते हैं। ऐरे arr[1 से n] को तीन भागों में विभाजित किया जाता है।
- arr[1 से i]
- arr[i + 1, j]
- arr[j + 1, n]
एल्गोरिदम
partition(arr, left, right, 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(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
उदाहरण
#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[mid], arr[right--]);
}
i = left-1;
j = mid;
}
void quicksort(int arr[], int left, int right) {
if (left >= right) // 1 या 0 एलिमेंट्स
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
