এখানে আমরা কুইকসর্ট টেকনিক দেখব কিন্তু আমরা থ্রি-ওয়ে কুইকসর্ট ব্যবহার করব। প্রাথমিক কুইকসর্ট কৌশলটি হল পিভট হিসাবে একটি উপাদান খুঁজে বের করা তারপর পিভটের চারপাশে অ্যারেটিকে পার্টিশন করা, তারপরে, পিভটের বাম এবং ডানদিকে সাব অ্যারেগুলির জন্য পুনরাবৃত্তি করা।
থ্রি-ওয়ে কুইকসোর্ট একই রকম, কিন্তু তিনটি বিভাগ আছে। array arr[1 থেকে n] তিনটি ভাগে বিভক্ত।
- arr[1 থেকে i]
- arr[i + 1, j]
- arr[j + 1, n]
অ্যালগরিদম
পার্টিশন (আর, বাম, ডান, আই, জে) -
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[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
