क्विकसॉर्ट तकनीक लिस्ट को दो भागों में अलग करके की जाती है। प्रारंभ में पार्टीशनिंग एल्गोरिदम द्वारा एक पिवट एलिमेंट चुना जाता है। पिवट का बायां भाग पिवट से छोटे मान रखता है, और दायां भाग बड़ा मान रखता है। पार्टीशनिंग के बाद, प्रत्येक अलग लिस्ट को उसी प्रक्रिया का उपयोग करके पार्टीशन किया जाता है।
इस मामले में हम पिवट एलिमेंट को रैंडमली चुन रहे हैं। पिवट चुनने के बाद, हम पार्टीशनिंग कर रहे हैं, फिर ऐरे को रिकर्सिवली सॉर्ट कर रहे हैं।
क्विकसॉर्ट तकनीक की जटिलता
टाइम कॉम्प्लेक्सिटी - बेस्ट केस और एवरेज केस के लिए O(n log n), वर्स्ट केस के लिए O(n²)।
स्पेस कॉम्प्लेक्सिटी - O(log n)
इनपुट - अनसॉर्टेड लिस्ट: 90 45 22 11 22 50
आउटपुट - सॉर्टिंग के बाद ऐरे: 11 22 22 45 50 90
एल्गोरिदम
partition(array, lower, upper)
इनपुट - डेटा सेट ऐरे, लोअर बाउंडरी और अपर बाउंडरी
आउटपुट - सही पोजीशन में पिवट
Begin
index := lower
pivot := higher
i को lower से higher की रेंज में, करें
यदि array[i] < array[pivot], तो
array[i] और array[index] के मान एक्सचेंज करें
index := index + 1
किया
array[pivot] और array[index] के मान एक्सचेंज करें
End
random_pivot_partition(array, lower, upper)
इनपुट - डेटा सेट ऐरे, लोअर बाउंडरी और अपर बाउंडरी
आउटपुट - रैंडमली चुने गए पिवट का अंतिम इंडेक्स
Begin
n := एक रैंडम नंबर
pvt := lower + n mod (upper - lower + 1)
array[pivot] और array[upper] के मान एक्सचेंज करें
index := Partition(array, lower, upper)
index लौटाएं
End
quickSort(array, left, right)
इनपुट - डेटा का एक ऐरे, और ऐरे की लोअर और अपर बाउंड
आउटपुट - सॉर्टेड ऐरे
Begin
यदि lower < right तो
q = random_pivot_partition(array, left, right).
quickSort(array, left, q-1)
quickSort(array, q+1, right)
End
उदाहरण कोड
#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