क्विकसॉर्ट तकनीक सूची को दो भागों में विभाजित करके की जाती है। प्रारंभ में विभाजन एल्गोरिथम द्वारा एक धुरी तत्व चुना जाता है। पिवट का बायां भाग पिवट की तुलना में छोटे मान रखता है, और दायां भाग बड़ा मान रखता है। विभाजन के बाद, प्रत्येक अलग सूचियों को एक ही प्रक्रिया का उपयोग करके विभाजित किया जाता है।
यहां हम सॉर्ट करने के लिए एक बड़े सरणी (लगभग 100 तत्व) पर विचार कर रहे हैं। हम कुछ संख्याएँ ले रहे हैं और फिर उन्हें क्रमबद्ध करने के लिए यादृच्छिक क्रम में फेरबदल कर रहे हैं। फिर क्विकसॉर्ट तकनीक का उपयोग करके सॉर्ट करें।
क्विकॉर्ट तकनीक की जटिलता
-
समय की जटिलता − O(n log n) सर्वोत्तम मामले और औसत मामले के लिए, O(n 2 ) सबसे खराब स्थिति के लिए।
-
अंतरिक्ष जटिलता -ओ(लॉग एन)
इनपुट - क्रमबद्ध सूची:90 45 22 11 22 50
आउटपुट - क्रमबद्ध करने के बाद सरणी:11 22 22 45 50 90
एल्गोरिदम
विभाजन (सरणी, निचला, ऊपरी)
इनपुट -डेटा सेट सरणी, निचली सीमा और ऊपरी सीमा
आउटपुट - सही स्थिति में पिवट करें
Begin pivot := array[upper] i := lower – 1 for j in range lower to higher, do if array[j] < pivot, then exchange the values of array[i] and array[j] i := i + 1 done exchange the values of array[upper] and array[i + 1] return i + 1 End
quickSort(सरणी, बाएँ, दाएँ)
इनपुट - डेटा की एक सरणी, और सरणी की निचली और ऊपरी सीमा
आउटपुट - सॉर्ट किया गया ऐरे
Begin if lower < right then 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[]) { //function to shuffle the array elements into random positions
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]; //last item as pivot
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) { //recursively sort the list
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); //To randomize the array
quick_sort(arr, 0, MAX-1); //sort the elements of array
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