क्विक सॉर्ट डिवाइड-एंड-कंकर पर आधारित है। इस एल्गोरिदम की औसत समय जटिलता O(n log n) है लेकिन सबसे खराब स्थिति की जटिलता O(n^2) है। सबसे खराब स्थिति की संभावना को कम करने के लिए यहां क्विकसॉर्ट को रैंडमाइजेशन का उपयोग करके लागू किया गया है।
एल्गोरिदम
partition(int a[], int l,int h)
शुरुआत pivot = h Index = l start = l and end = h while start < end do while a[start] <= pivot AND start < end do start = start +1 done while a[end] > pivot do end = end – 1 done if start < end then swap a[start] with a[end] done a[low] = a[end] a[end] = pivot return end अंत
RandomPivotPartition(int a[], int l, int h)
शुरुआत n = rand() pivot = l + n%(h-l+1); Swap a[h] with a[pivot] return Partition(a, l, h) अंत
QuickSort(int a[], int l, int h)
शुरुआत int pindex; If (l<h) pindex = RandomPivotPartition(a, l, h) QuickSort(a, l, pindex-1) QuickSort(a, pindex+1, h) return 0 अंत
उदाहरण कोड
#include<iostream> #include<cstdlib> using namespace std; void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int Partition(int a[], int l, int h) { int pivot, index, i; index = l; pivot = h; for(i = l; i < h; i++) { if(a[i] < a[pivot]) { swap(&a[i], &a[index]); index++; } } swap(&a[pivot], &a[index]); return index; } int RandomPivotPartition(int a[], int l, int h) { int pvt, n, temp; n = rand(); pvt = l + n%(h-l+1); swap(&a[h], &a[pvt]); return Partition(a, l, h); } int QuickSort(int a[], int l, int h) { int pindex; if(l < h) { pindex = RandomPivotPartition(a, l, h); QuickSort(a, l, pindex-1); QuickSort(a, pindex+1, h); } return 0; } int main() { int n, i; cout<<"\nसॉर्ट किए जाने वाले डेटा एलिमेंट की संख्या दर्ज करें: "; cin>>n; int arr[n]; for(i = 0; i < n; i++) { cout<<"एलिमेंट "<<i+1<<": "; cin>>arr[i]; } QuickSort(arr, 0, n-1); cout<<"\nसॉर्टेड डेटा "; for (i = 0; i < n; i++) cout<<"->"<<arr[i]; return 0; } आउटपुट
सॉर्ट किए जाने वाले डेटा एलिमेंट की संख्या दर्ज करें: 4 एलिमेंट 1 दर्ज करें: 3 एलिमेंट 2 दर्ज करें: 4 एलिमेंट 3 दर्ज करें: 7 एलिमेंट 4 दर्ज करें: 6 सॉर्टेड डेटा ->3->4->6->7
