क्विकसॉर्ट तकनीक सूची को दो भागों में विभाजित करके की जाती है। प्रारंभ में विभाजन एल्गोरिथम द्वारा एक धुरी तत्व चुना जाता है। पिवट का बायां भाग पिवट की तुलना में छोटे मान रखता है, और दायां भाग बड़ा मान रखता है। विभाजन के बाद, प्रत्येक अलग सूचियों को एक ही प्रक्रिया का उपयोग करके विभाजित किया जाता है।
इस मामले में हम धुरी तत्व को बेतरतीब ढंग से चुन रहे हैं। पिवट चुनने के बाद, हम विभाजन कर रहे हैं, फिर सरणी को पुनरावर्ती रूप से क्रमबद्ध करें।
क्विकॉर्ट तकनीक की जटिलता
-
समय की जटिलता − O(n log n) सर्वोत्तम मामले और औसत मामले के लिए, O(n 2 ) सबसे खराब स्थिति के लिए।
-
अंतरिक्ष जटिलता -ओ(लॉग एन)
इनपुट - क्रमबद्ध सूची:90 45 22 11 22 50
आउटपुट - क्रमबद्ध करने के बाद सरणी:11 22 22 45 50 90
एल्गोरिदम
विभाजन (सरणी, निचला, ऊपरी)
इनपुट -डेटा सेट सरणी, निचली सीमा और ऊपरी सीमा
आउटपुट - सही स्थिति में पिवट करें
Begin index := lower pivot := higher for i in range lower to higher, do if array[i] < array[pivot], then exchange the values of array[i] and array[index] index := index + 1 done exchange the values of array[pivot] and array[index] End
random_pivot_partition(सरणी, निचला, ऊपरी)
इनपुट - डेटा सेट सरणी, निचली सीमा और ऊपरी सीमा
आउटपुट − बेतरतीब ढंग से चुनी गई धुरी का अंतिम सूचकांक
Begin n := a random number pvt := lower + n mod (upper – lower + 1) exchange the values of array[pivot] and array[upper] index := Partition(array, lower, upper) return index End
quickSort(सरणी, बाएँ, दाएँ)
इनपुट - डेटा की एक सरणी, और सरणी की निचली और ऊपरी सीमा
आउटपुट - क्रमबद्ध सरणी
Begin if lower < right then 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[]) {
//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;
}
}
// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high) {
int pivot, index, i;
index = low;
pivot = high;
for(i=low; i < high; i++) {
// finding index of pivot.
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){
// Random selection of pivot.
int pvt, n, temp;
n = rand();
pvt = low + n%(high-low+1); // Randomizing the pivot value from sub-array.
swap(a[high], a[pvt]);
return Partition(a, low, high);
}
void quick_sort(int arr[], int p, int q) {
//recursively sort the list
int pindex;
if(p < q) {
pindex = RandomPivotPartition(arr, p, q); //randomly choose pivot
// Recursively implementing QuickSort.
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); //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