কুইক সোর্ট একটি ডিভাইড-এন্ড-কঙ্কোয়ার অ্যালগরিদম। একটি পিভট এলিমেন্ট বেছে নিয়ে অ্যারেটিকে দুটি অংশে পার্টিশন করা হয়: বামে পিভটের চেয়ে ছোট, ডানে বড়। তারপর প্রতিটি সাব-অ্যারে রিকারসিভলি সর্ট করা হয়।
কুইক সোর্টের জটিলতা
- টাইম কমপ্লেক্সিটি: বেস্ট/এভারেজ O(n log n), ওয়ার্স্ট O(n²)
- স্পেস কমপ্লেক্সিটি: O(log n) (রিকারসন স্ট্যাক)
ইনপুট এবং আউটপুট
Input: The unsorted list: 90 45 22 11 22 50
Output: Array before Sorting: 90 45 22 11 22 50
Array after Sorting: 11 22 22 45 50 90
অ্যালগরিদম
partition(array, lower, upper) - হোয়ার পার্টিশনিং
Begin
pivot := array[lower], start := lower, end := upper
while start < end do
while array[start] <= pivot AND start < end: start++
while array[end] > pivot: end--
if start < end: swap array[start], array[end]
done
array[lower] = array[end]; array[end] = pivot
return end
End
quickSort(array, left, right)
Begin
if left < right then
q = partition(array, left, right)
quickSort(array, left, q-1)
quickSort(array, q+1, right)
End
C++ উদাহরণ
#include <iostream>
using namespace std;
void swapping(int &a, int &b) { int t=a; a=b; b=t; }
void display(int *a, int n) { for(int i=0;i pivot) end--;
if(start < end) swapping(array[start], array[end]);
}
array[lower] = array[end]; array[end] = pivot;
return end;
}
void quickSort(int *array, int left, int right) {
if(left < right) {
int q = partition(array, left, right);
quickSort(array, left, q-1);
quickSort(array, q+1, right);
}
}
int main() {
int n; cout << "Enter the number of elements: "; cin >> n;
int arr[n];
cout << "Enter elements:" << endl;
for(int i=0; i> arr[i];
cout << "Array before Sorting: "; display(arr, n);
quickSort(arr, 0, n-1);
cout << "Array after Sorting: "; display(arr, n);
}
আউটপুট
Enter the number of elements: 6
Enter elements: 90 45 22 11 22 50
Array before Sorting: 90 45 22 11 22 50
Array after Sorting: 11 22 22 45 50 90
