এখানে আমরা কুইকসোর্ট কৌশল দেখব কিন্তু তিন-পথে (three-way) কুইকসোর্ট ব্যবহার করব। মৌলিক কুইকসোর্টে একটি পিভট বের করে অ্যারের সেটি পিভট চারপাশে পার্টিশন করা হয়, তারপর পিভটের বাম ও ডানের সাব-অ্যারে জন্য পুনরাবৃত্তি করা হয়।
থ্রি-ওয়ে কুইকসোর্টও অনুরূপ, কিন্তু এখানে তিনটি সেকশন থাকে। অ্যারের arr[1 to n] তিন ভাগে ভাগ করা হয়:
- arr[1 to i]
- arr[i + 1, j]
- arr[j + 1, n]
অ্যালগরিদম
partition(arr, left, right, i, j) −
শুরু 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] left এবং mid ১ বাড়ান else if arr[mid] = pivot, then mid ১ বাড়ান else swap arr[mid], arr[right] right ১ কমান done i := left – 1 j := mid শেষ
quicksort(arr, left, right) −
শুরু if left >= right, then return end if i এবং j ডিক্লেয়ার করুন partition(arr, left, right, i, j) quicksort(arr, left, i) quicksort(arr, j, right) শেষ
উদাহরণ
#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) // ১ বা ০ এলিমেন্ট 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
