क्विकसॉर्ट तकनीक लिस्ट को दो भागों में अलग करके की जाती है। प्रारंभ में पार्टीशनिंग एल्गोरिदम द्वारा एक पिवट एलिमेंट चुना जाता है। पिवट का बायां भाग पिवट से छोटे मान रखता है, और दायां भाग बड़ा मान रखता है। पार्टीशनिंग के बाद, प्रत्येक अलग लिस्ट को उसी प्रक्रिया का उपयोग करके पार्टीशन किया जाता है।
यहां हम लगभग 100 एलिमेंट्स के एक बड़े ऐरे को सॉर्ट करने पर विचार कर रहे हैं। हम कुछ नंबर ले रहे हैं फिर उन्हें रैंडमाइज्ड ऑर्डर में शफल कर रहे हैं ताकि वे अनसॉर्टेड हो जाएं। फिर क्विकसॉर्ट तकनीक का उपयोग करके सॉर्ट करें।
क्विकसॉर्ट तकनीक की जटिलता
टाइम कॉम्प्लेक्सिटी - बेस्ट केस और एवरेज केस के लिए 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
pivot := array[upper]
i := lower - 1
j को lower से higher की रेंज में, करें
यदि array[j] < pivot, तो
array[i] और array[j] के मान एक्सचेंज करें
i := i + 1
किया
array[upper] और array[i + 1] के मान एक्सचेंज करें
i + 1 लौटाएं
End
quickSort(array, left, right)
इनपुट - डेटा का एक ऐरे, और ऐरे की लोअर और अपर बाउंड
आउटपुट - सॉर्टेड ऐरे
Begin
यदि lower < right तो
q = 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 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