কুইকসোর্ট টেকনিক লিস্টকে দুই অংশে ভাগ করে করা হয়। প্রাথমিকভাবে পার্টিশনিং অ্যালগরিদম দিয়ে একটি পিভট এলিমেন্ট বেছে নেওয়া হয়। পিভটের বাম অংশে পিভট থেকে ছোট ভ্যালুগুলো থাকে, এবং ডান অংশে বড় ভ্যালুগুলো। পার্টিশনিং के পর, প্রতিটি আলাদা লিস্টকে একই প্রসিডিউর দিয়ে পার্টিশন করা হয়।
এই কেসে আমরা পিভট এলিমেন্ট র্যান্ডমলি বেছে নিচ্ছি। পিভট বেছে নেওয়ার পর, আমরা পার্টিশনিং করছি, তারপর রিকারসিভলি অ্যারে সর্ট করছি।
কুইকসোর্ট টেকনিকের কমপ্লেক্সিটি
টাইম কমপ্লেক্সিটি - বেস্ট কেস এবং এভারেজ কেসের জন্য O(n log n), ওয়ার্স্ট কেসের জন্য O(n2)
স্পেস কমপ্লেক্সিটি - O(log n)
ইনপুট - অনসর্টেড লিস্ট: 90 45 22 11 22 50
আউটপুট - সর্টিং পরে অ্যারে: 11 22 22 45 50 90
অ্যালগরিদম
partition(array, lower, upper)
ইনপুট - ডেটা সেট অ্যারে, লোয়ার বাউন্ডারি এবং আপার বাউন্ডারি
আউটপুট - সঠিক পজিশনে পিভট
শুরু
index := lower
pivot := higher
for i in range lower to higher, do
if array[i] < array[pivot], then
array[i] এবং array[index]-এর ভ্যালু এক্সচেঞ্জ করুন
index := index + 1
লুপ শেষ
array[pivot] এবং array[index]-এর ভ্যালু এক্সচেঞ্জ করুন
শেষ
random_pivot_partition(array, lower, upper)
ইনপুট - ডেটা সেট অ্যারে, লোয়ার বাউন্ডারি এবং আপার বাউন্ডারি
আউটপুট - র্যান্ডমলি বেছে নেওয়া পিভটের ফাইনাল ইনডেক্স
শুরু n := একটি র্যান্ডম নম্বর pvt := lower + n mod (upper - lower + 1) array[pivot] এবং array[upper]-এর ভ্যালু এক্সচেঞ্জ করুন index := Partition(array, lower, upper) return index শেষ
quickSort(array, left, right)
ইনপুট - একটি ডেটা অ্যারে, এবং অ্যারের লোয়ার এবং আপার বাউন্ড
আউটপুট - সর্টেড অ্যারে
শুরু
if lower < right then
q = random_pivot_partition(array, left, right).
quickSort(array, left, q-1)
quickSort(array, q+1, right)
শেষ
উদাহরণ কোড
#include<iostream>
#include<cstdlib>
#include<ctime>
#define MAX 100
using namespace std;
void random_shuffle(int arr[]) {
srand(time(NULL));
for (int i = MAX - 1; i > 0; i--) {
int j = rand()%(i + 1);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int Partition(int a[], int low, int high) {
int pivot, index, i;
index = low;
pivot = high;
for(i=low; i < high; i++) {
if(a[i] < a[pivot]) {
swap(a[i], a[index]);
index++;
}
}
swap(a[pivot], a[index]);
return index;
}
int RandomPivotPartition(int a[], int low, int high){
int pvt, n, temp;
n = rand();
pvt = low + n%(high-low+1); // সাব-অ্যারে থেকে র্যান্ডমলি পিভট ভ্যালু
swap(a[high], a[pvt]);
return Partition(a, low, high);
}
void quick_sort(int arr[], int p, int q) {
int pindex;
if(p < q) {
pindex = RandomPivotPartition(arr, p, q); // র্যান্ডমলি পিভট বেছে নিন
quick_sort(arr, p, pindex-1);
quick_sort(arr, pindex+1, q);
}
}
int main() {
int i;
int arr[MAX];
for (i = 0;i < MAX; i++)
arr[i] = i + 1;
random_shuffle(arr); // অ্যারে র্যান্ডোমাইজ
quick_sort(arr, 0, MAX - 1); // অ্যারের এলিমেন্ট সর্ট
for (i = 0; i < MAX; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
আউটপুট
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
