क्विकसॉर्ट एक छँटाई तकनीक है जो एक क्रमबद्ध सूची (सरणी) को क्रमबद्ध करने के लिए तुलना का उपयोग करती है। Quicksort को पार्टीशन एक्सचेंज सॉर्ट के रूप में भी जाना जाता है।
यह एक स्थिर प्रकार नहीं है, क्योंकि समान प्रकार की वस्तुओं का सापेक्ष क्रम संरक्षित नहीं है। क्विकसॉर्ट एक सरणी पर काम कर सकता है, जिसके लिए छँटाई करने के लिए थोड़ी अतिरिक्त मात्रा में मेमोरी की आवश्यकता होती है। यह चयन प्रकार के समान है, सिवाय इसके कि यह हमेशा सबसे खराब स्थिति वाले विभाजन का चयन नहीं करता है। तो, इसलिए हम इसे चयन सॉर्ट के बेहतर गठन के रूप में ले सकते हैं।
QuickSort सबसे कुशल सॉर्टिंग एल्गोरिदम में से एक है और यह एक सरणी को छोटे लोगों में विभाजित करने पर आधारित है। नाम इस तथ्य से आता है कि क्विकॉर्ट किसी भी सामान्य सॉर्टिंग एल्गोरिदम की तुलना में डेटा तत्वों की सूची को काफी तेजी से सॉर्ट करने में सक्षम है। और मर्ज सॉर्ट की तरह, क्विक सॉर्ट भी समस्या-समाधान पद्धति के विभाजन और जीत के दृष्टिकोण की श्रेणी में आता है।
क्विकसॉर्ट एल्गोरिथम निम्न तरीके से काम करता है
-
समरूप दृष्टिकोण को परिप्रेक्ष्य में लेते हुए, एक ऐसी स्थिति पर विचार करें, जहां छात्रों के नाम वाले पेपरों को नाम से छांटना पड़े। कोई इस दृष्टिकोण का उपयोग इस प्रकार कर सकता है -
-
एक विभाजन मान चुनें, मान लें कि L. विभाजन मान को पिवट . के रूप में भी जाना जाता है
-
कागजों के ढेर को दो भागों में बाँट लें। ए-एल और एम-जेड। यह जरूरी नहीं है कि बवासीर बराबर हो।
-
उपरोक्त दो चरणों को ए-एल ढेर के साथ दोहराएं, इसे इसके महत्वपूर्ण दो हिस्सों में विभाजित करें। और एम-जेड ढेर, इसके हिस्सों में विभाजित। प्रक्रिया तब तक दोहराई जाती है जब तक कि ढेर आसानी से छांटने के लिए पर्याप्त छोटे न हो जाएं।
-
अंततः, छोटे ढेरों को एक के ऊपर एक रखा जा सकता है ताकि पूरी तरह से क्रमबद्ध और व्यवस्थित कागज़ों का सेट तैयार किया जा सके।
-
-
यहां इस्तेमाल किया गया दृष्टिकोण पुनरावृत्ति . है एकल-तत्व सरणी में जाने के लिए प्रत्येक विभाजन पर।
-
प्रत्येक विभाजन पर, ढेर को विभाजित किया गया था और फिर छोटे बवासीर के लिए उसी दृष्टिकोण का उपयोग किया गया था।
-
इन विशेषताओं के कारण, Quicksort को विभाजन विनिमय सॉर्ट . भी कहा जाता है ।
Input: arr[] = {7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7 स्पष्टीकरण
अवधारणा को समझने के लिए एक उदाहरण काम आ सकता है। निम्नलिखित सरणी पर विचार करें:50, 23, 9, 18, 61, 32
चरण 1 - सूची से धुरी होने के लिए किसी भी मान को तय करें (आमतौर पर अंतिम मान)। मान लीजिए कि दो मान “निम्न” और “उच्च” हैं जो पहली अनुक्रमणिका और अंतिम अनुक्रमणिका के अनुरूप हैं।
हमारे मामले में निम्न 0 है और उच्च 5 है।
निम्न और उच्च पर मान 50 और 32 हैं और धुरी का मान 32 है।
इसलिए, विभाजन के लिए कॉल करें, सरणी को इस तरह से पुनर्व्यवस्थित करें कि धुरी (32) अपनी वास्तविक स्थिति में आ जाए। और पिवट के बाईं ओर, सरणी में इससे कम सभी तत्व होते हैं, और दाईं ओर इससे बड़े होते हैं।
विभाजन समारोह में, हम पहले तत्व से शुरू करते हैं और इसकी तुलना धुरी से करते हैं। चूंकि 50, 32 से बड़ा है, इसलिए हम कोई बदलाव नहीं करते हैं और अगले तत्व 23 पर आगे बढ़ते हैं।
धुरी के साथ फिर से तुलना करें। चूँकि 23, 32 से कम है, हम 50 और 23 को स्वैप करते हैं। सरणी 23, 50, 9, 18, 61, 32 बन जाती है।
हम अगले तत्व 9 पर आगे बढ़ते हैं जो फिर से पिवट (32) से कम है और इस प्रकार इसे 50 के साथ स्वैप करने से हमारा एरे बन जाता है
23, 9, 50, 18, 61, 32.
इसी तरह, अगले तत्व 18 के लिए जो 32 से कम है, सरणी बन जाती है
23, 9, 18, 50, 61, 32 अब 61 पिवट (32) से बड़ा है, इसलिए कोई बदलाव नहीं।
अंत में, हम अपनी धुरी को 50 से बदल देते हैं ताकि वह सही स्थिति में आ जाए।
इस प्रकार धुरी (32) अपनी वास्तविक स्थिति में आती है और इसके बाईं ओर के सभी तत्व कम होते हैं, और दाईं ओर के सभी तत्व अपने आप से बड़े होते हैं।
चरण 2 - इसलिए पहले चरण के बाद की सरणी बन जाती है
23, 9, 18, 32, 61, 50, 32 को धुरी के रूप में लेते हुए।
चरण 3 - अब सूची को दो भागों में बांटा गया है:
1. पिवट से पहले सबलिस्ट करें:23, 9, 18
2. पिवट के बाद सबलिस्ट करें:61, 50
चरण 4 - इन उप-सूचियों के लिए चरणों को दोबारा दोहराएं।
इस प्रकार अंतिम सरणी 9, 18, 23, 32, 50, 61 हो जाती है।
उदाहरण
#include <stdio.h>
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = 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);
}
int QuickSort(int a[], int low, int high) {
return 0;
}
int main() {
int n, i;
n=7;
int arr[]={7,4,2,6,3,1,5};
int high = n-1;
int low = 0 ;
int pindex;
if(low < high) {
pindex = RandomPivotPartition(arr, low, high);
QuickSort(arr, low, pindex-1);
QuickSort(arr, pindex+1, high);
}
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}