কুইকসোর্ট টেকনিক লিস্টকে দুই অংশে ভাগ করে করা হয়। প্রাথমিকভাবে পার্টিশনিং অ্যালগরিদম দিয়ে একটি পিভট এলিমেন্ট বেছে নেওয়া হয়। পিভটের বাম অংশে পিভট থেকে ছোট ভ্যালুগুলো থাকে, এবং ডান অংশে বড় ভ্যালুগুলো। পার্টিশনিং के পর, প্রতিটি আলাদা লিস্টকে একই প্রসিডিউর দিয়ে পার্টিশন করা হয়।
এখানে আমরা একটি বড় অ্যারে (প্রায় ১০০ এলিমেন্ট) সর্ট করব। আমরা কিছু নম্বর নিব এবং সেগুলো র্যান্ডোম অর্ডারে শাফল করব আনসর্টেড বানাতে। তারপর কুইকসোর্ট টেকনিক দিয়ে সর্ট করব।
কুইকসোর্ট টেকনিকের কমপ্লেক্সিটি
টাইম কমপ্লেক্সিটি - বেস্ট কেস এবং এভারেজ কেসের জন্য 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)
ইনপুট - ডেটা সেট অ্যারে, লোয়ার বাউন্ডারি এবং আপার বাউন্ডারি
আউটপুট - সঠিক পজিশনে পিভট
শুরু
pivot := array[upper]
i := lower - 1
for j in range lower to higher, do
if array[j] < pivot, then
array[i] এবং array[j]-এর ভ্যালু এক্সচেঞ্জ করুন
i := i + 1
লুপ শেষ
array[upper] এবং array[i + 1]-এর ভ্যালু এক্সচেঞ্জ করুন
return i + 1
শেষ
quickSort(array, left, right)
ইনপুট - একটি ডেটা অ্যারে, এবং অ্যারের লোয়ার এবং আপার বাউন্ড
আউটপুট - সর্টেড অ্যারে
শুরু
if lower < right then
q = 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 partion(int arr[], int p, int r) {
int pivot = arr[r]; // লাস্ট আইটেম আজ পিভট
int i = p - 1;
for (int j = p; j < r; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i+1], arr[r]);
return i + 1;
}
void quick_sort(int arr[], int p, int q) {
int j;
if (p < q) {
j = partion(arr, p, q);
quick_sort(arr, p, j - 1);
quick_sort(arr, j + 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
