quick sort c with examples
इलस्ट्रेशन के साथ C ++ में क्विकॉर्ट।
क्विकॉर्ट एक व्यापक रूप से उपयोग की जाने वाली छँटाई एल्गोरिथ्म है जो 'धुरी' नामक एक विशिष्ट तत्व का चयन करता है और इस धुरी s0 के आधार पर सरणी या सूची को दो भागों में विभाजित करने के लिए विभाजित करता है जो कि धुरी से कम तत्व सूची और तत्वों के बाईं ओर हैं। धुरी से अधिक सूची के दाईं ओर हैं।
इस प्रकार यह सूची दो उपविभागों में विभाजित है। समान आकार के लिए सब्लिस्ट आवश्यक नहीं हो सकते हैं। फिर क्विकॉर्ट ने खुद को इन दो उप-कलाकारों को क्रमबद्ध करने के लिए पुनरावर्ती कॉल किया।
=> यहां परफेक्ट सी ++ ट्रेनिंग गाइड देखें।
आप क्या सीखेंगे:
- परिचय
- सामान्य एल्गोरिथम
- क्विकॉर्ट के लिए छद्म कोड
- चित्रण
- C ++ उदाहरण
- जावा उदाहरण
- क्विकॉर्ट एल्गोरिथम की जटिलता विश्लेषण
- 3-रास्ता क्विकॉर्ट
- रैंडमाइज़्ड क्विकॉर्ट
- Quicksort बनाम मर्ज सॉर्ट
- निष्कर्ष
- अनुशंसित पाठ
परिचय
क्विकॉर्ट कुशलता से काम करता है और साथ ही साथ बड़ी सरणियों या सूचियों के लिए भी तेजी से काम करता है।
इस ट्यूटोरियल में, हम क्विकसॉर्ट एल्गोरिथम के कुछ प्रोग्रामिंग उदाहरणों के साथ क्विकसॉर्ट के काम के बारे में अधिक जानकारी प्राप्त करेंगे।
धुरी मूल्य के रूप में, हम पहले, अंतिम या मध्य मूल्य या किसी भी यादृच्छिक मूल्य को चुन सकते हैं। सामान्य विचार यह है कि अंततः धुरी का मूल्य सरणी में अन्य तत्वों को बाईं या दाईं ओर ले जाकर सरणी में अपनी उचित स्थिति पर रखा जाता है।
सामान्य एल्गोरिथम
Quicksort के लिए सामान्य एल्गोरिथ्म नीचे दिया गया है।
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low आइए अब क्विकॉर्ट तकनीक के लिए छद्मकोड पर एक नज़र डालें।
क्विकॉर्ट के लिए छद्म कोड
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low विभाजन एल्गोरिथ्म का काम एक उदाहरण का उपयोग करके नीचे वर्णित है।
इस दृष्टांत में, हम अंतिम तत्व को धुरी के रूप में लेते हैं। हम देख सकते हैं कि सरणी क्रमिक रूप से धुरी तत्व के आसपास विभाजित है जब तक कि हमारे पास सरणी में एक भी तत्व नहीं है।
अब हम अवधारणा को बेहतर ढंग से समझने के लिए नीचे दिए गए क्विकॉर्ट का उदाहरण प्रस्तुत करते हैं।
चित्रण
आइए हम क्विकसॉर्ट एल्गोरिथम का एक चित्रण देखते हैं। अंतिम तत्व के साथ धुरी के रूप में निम्नलिखित सरणी पर विचार करें। इसके अलावा, पहला तत्व कम लेबल किया गया है और अंतिम तत्व उच्च है।
कैरेक्टर को int c ++ में कन्वर्ट करें
दृष्टांत से, हम देख सकते हैं कि, हम व्यूअर के दोनों सिरों पर बिंदुओं को ऊँचे और नीचे ले जाते हैं। जब भी धुरी से अधिक तत्व की ओर कम और उच्च बिंदु से धुरी की तुलना में कम तत्व को इंगित करता है, तो हम इन तत्वों की स्थिति का आदान-प्रदान करते हैं और निम्न और उच्च बिंदुओं को उनके संबंधित दिशाओं में आगे बढ़ाते हैं।
यह तब तक किया जाता है जब तक कम और उच्च बिंदु एक दूसरे को पार नहीं करते हैं। एक बार जब वे एक दूसरे को पार करते हैं तो धुरी तत्व को उसके उचित स्थान पर रखा जाता है और सरणी को दो भागों में विभाजित किया जाता है। फिर इन दोनों उप-सरणियों को पुनरावर्ती रूप से क्विकर का उपयोग करके स्वतंत्र रूप से सॉर्ट किया जाता है।
C ++ उदाहरण
नीचे दिए गए C ++ में क्विकसॉर्ट एल्गोरिथम का कार्यान्वयन है।
यूनिक्स खोल पटकथा साक्षात्कार प्रश्न और अनुभवी के लिए जवाब
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int pivot = arr(high); // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< आउटपुट:
इनपुट सरणी
12 23 3 43 51 35 19 45
एरेस क्विकॉर्ट के साथ सॉर्ट किया गया
3 12 19 23 35 43 45 51
यहां हमारे पास कुछ रूटीन हैं जिनका उपयोग सरणी को विभाजित करने के लिए किया जाता है और विभाजन सामग्री, मूल क्विकसॉर्ट फ़ंक्शन और उपयोगिता कार्यों को सॉर्ट करने के लिए पुनरावर्ती कॉल करता है और सरणी सामग्री को प्रदर्शित करने और तदनुसार दो तत्वों को स्वैप करने के लिए कार्य करता है।
सबसे पहले, हम क्विकॉर्ट फंक्शन को इनपुट एरे के साथ कहते हैं। Quicksort फ़ंक्शन के अंदर, हम विभाजन फ़ंक्शन कहते हैं। विभाजन फ़ंक्शन में, हम अंतिम तत्व का उपयोग सरणी के लिए धुरी तत्व के रूप में करते हैं। एक बार धुरी तय हो जाने के बाद, सरणी को दो भागों में विभाजित किया जाता है और फिर क्विकॉर्ट फ़ंक्शन को स्वतंत्र रूप से दोनों उप सरणियों को सॉर्ट करने के लिए कहा जाता है।
जब एस्कॉर्ट फंक्शन लौटता है, तो सरणी को इस तरह सॉर्ट किया जाता है कि धुरी तत्व अपने सही स्थान पर होता है और धुरी की तुलना में कम तत्व धुरी के बाईं ओर होता है और धुरी से बड़ा तत्व धुरी के दाईं ओर होता है।
अगला, हम जावा में क्विकसॉर्ट एल्गोरिथम लागू करेंगे।
जावा उदाहरण
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr(), int low, int high) { int pivot = arr(high); int i = (low-1); // index of smaller element for (int j=low; j आउटपुट:
इनपुट सरणी
12 23 3 43 51 35 19 45
क्विकॉर्ट के साथ छँटाई के बाद सरणी
3 12 19 23 35 43 45 51
जावा कार्यान्वयन में भी, हमने उसी तर्क का उपयोग किया है जो हमने C ++ कार्यान्वयन में उपयोग किया था। हमने धुरी में अंतिम तत्व का उपयोग किया है क्योंकि धुरी और क्विकॉर्ट को धुरी तत्व को उसके उचित स्थान पर रखने के लिए सरणी पर किया जाता है।
क्विकॉर्ट एल्गोरिथम की जटिलता विश्लेषण
एक सरणी को सॉर्ट करने के लिए क्विकॉर्ट द्वारा लिया गया समय इनपुट सरणी और विभाजन की रणनीति या विधि पर निर्भर करता है।
यदि कश्मीर धुरी से कम तत्वों की संख्या है और n कुल तत्वों की संख्या है, तो क्विकॉर्ट द्वारा लिया गया सामान्य समय निम्नानुसार व्यक्त किया जा सकता है:
T (n) = T (k) + T (n-k-1) + O (n)
यहाँ, T (k) और T (n-k-1) पुनरावर्ती कॉल द्वारा लिया गया समय है और O (n) कॉल विभाजन द्वारा लिया गया समय है।
आइए इस समय की जटिलता के बारे में विस्तार से विश्लेषण करें।
(1) सबसे खराब मामला : क्विकॉर्ट तकनीक में सबसे खराब स्थिति ज्यादातर तब होती है जब हम सरणी में सबसे कम या उच्चतम तत्व का चयन धुरी के रूप में करते हैं। (उपरोक्त चित्रण में हमने धुरी के रूप में उच्चतम तत्व का चयन किया है)। ऐसी स्थिति में सबसे खराब स्थिति तब होती है जब क्रमबद्ध किए जाने वाले सरणी को आरोही या अवरोही क्रम में पहले से ही सॉर्ट किया जाता है।
इसलिए कुल समय के लिए उपरोक्त अभिव्यक्ति इस प्रकार है:
T (n) = T (0) + T (n-1) + O (n) यह संकल्प करता है परदो)
# 2) सबसे अच्छा मामला: क्विकॉर्ट के लिए सबसे अच्छा मामला हमेशा तब होता है जब चयनित धुरी तत्व सरणी के बीच होता है।
इस प्रकार सबसे अच्छे मामले की पुनरावृत्ति है:
खोलने .7z फ़ाइलें मैक पर
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) औसत मामला: एस्कॉर्ट के लिए औसत मामले का विश्लेषण करने के लिए, हमें सभी सरणी क्रमपरिवर्तन पर विचार करना चाहिए और फिर इनमें से प्रत्येक क्रमपरिवर्तन द्वारा लिए गए समय की गणना करनी चाहिए। संक्षेप में, एस्कॉर्ट के लिए औसत समय भी O (nlogn) हो जाता है।
क्विकॉर्ट तकनीक की विभिन्न जटिलताएँ नीचे दी गई हैं:
सबसे खराब स्थिति समय जटिलता ओ (एन 2) स्थिरता स्थिर नहीं क्योंकि समान मूल्यों वाले दो तत्वों को एक ही क्रम में नहीं रखा जाएगा। स्थिर - एक ही मान वाले दो तत्व समान क्रम में आउटपुट में दिखाई देंगे। सबसे अच्छा मामला समय जटिलता O (n * लॉग एन) औसत समय जटिलता O (n * लॉग एन) अंतरिक्ष की जटिलता O (n * लॉग एन)
हम पिवट एलिमेंट (मध्य, प्रथम या अंतिम) की पसंद को बदलकर कई अलग-अलग तरीकों से क्विकर को लागू कर सकते हैं, हालांकि, क्विकर के लिए सबसे खराब स्थिति शायद ही कभी होती है।
3-रास्ता क्विकॉर्ट
मूल क्विकॉर्ट्स तकनीक में, हम आमतौर पर एक धुरी तत्व का चयन करते हैं और फिर इस धुरी के चारों ओर उप-सरणियों में सरणी को विभाजित करते हैं ताकि एक उप-सरणी में धुरी से कम तत्व शामिल हों और दूसरे में धुरी से अधिक तत्व शामिल हों।
लेकिन क्या होगा अगर हम एक धुरी तत्व का चयन करते हैं और सरणी में एक से अधिक तत्व हैं जो धुरी के बराबर है?
उदाहरण के लिए, निम्न सरणी पर विचार करें {5,76,23,65,4,4,5,4,1,1,2,2,2,2}। यदि हम इस सरणी पर एक सरल क्विकॉर्ट करते हैं और 4 को एक पिवेट एलिमेंट के रूप में चुनते हैं, तो हम एलिमेंट 4 की केवल एक घटना को ठीक करेंगे और बाकी को अन्य तत्वों के साथ विभाजित किया जाएगा।
इसके बजाय, यदि हम 3-तरफ़ा एस्कॉर्ट का उपयोग करते हैं, तो हम सरणी (l… r) को तीन उप-सरणियों में विभाजित करेंगे:
- Array (l… i) - यहाँ, मैं धुरी हूँ और इस सरणी में धुरी से कम तत्व हैं।
- Array (i + 1… j-1) - उन तत्वों को समाहित करता है जो धुरी के बराबर होते हैं।
- ऐरे (जे… आर) - इसमें धुरी से अधिक तत्व शामिल हैं।
इस प्रकार 3-तरफ़ा एस्कॉर्ट का उपयोग तब किया जा सकता है जब हमारे पास सरणी में एक से अधिक अनावश्यक तत्व हों।
रैंडमाइज़्ड क्विकॉर्ट
जब हम धुरी तत्व का चयन करने के लिए यादृच्छिक संख्याओं का उपयोग करते हैं तो क्विकॉर्ट तकनीक को रैंडमाइज़्ड क्विकॉर्ट तकनीक कहा जाता है। यादृच्छिक परिमाण में, इसे 'केंद्रीय धुरी' कहा जाता है और यह सरणी को इस तरह से विभाजित करता है कि प्रत्येक पक्ष में कम से कम-तत्व हों।
यादृच्छिक क्विकॉर्ट के लिए छद्म कोड नीचे दिया गया है:
// Sorts an array arr(low..high) using randomized quick sort randomQuickSort(array(), low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from (low..high). Let pi be the randomly picked number. (ii) Count elements in array(low..high) that are smaller than array(pi). Let this count be a_low. (iii) Count elements in array(low..high) that are greater than array(pi). Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array(low..high) around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedure'RandomQuickSort' पर उपरोक्त कोड में, चरण # 2 में हम केंद्रीय धुरी का चयन करते हैं। चरण 2 में, चयनित तत्व के केंद्रीय धुरी होने की संभावना prob है। इसलिए चरण 2 में लूप 2 बार चलने की उम्मीद है। इस प्रकार यादृच्छिक परिमाण में चरण 2 के लिए समय जटिलता O (n) है।
केंद्रीय धुरी का चयन करने के लिए एक लूप का उपयोग करना यादृच्छिक परिमाण को लागू करने का आदर्श तरीका नहीं है। इसके बजाय, हम बेतरतीब ढंग से एक तत्व का चयन कर सकते हैं और इसे केंद्रीय धुरी कह सकते हैं या सरणी तत्वों को फेरबदल कर सकते हैं। रैंडमाइज्ड एस्कॉर्ट एल्गोरिथ्म के लिए अपेक्षित सबसे खराब स्थिति समय जटिलता हे (nlogn) है।
Quicksort बनाम मर्ज सॉर्ट
इस खंड में, हम क्विक सॉर्ट और मर्ज सॉर्ट के बीच मुख्य अंतर पर चर्चा करेंगे।
तुलना पैरामीटर जल्दी से सुलझाएं मर्ज़ सॉर्ट विभाजन सरणी को एक धुरी तत्व के चारों ओर विभाजित किया गया है और जरूरी नहीं कि हमेशा दो हिस्सों में हो। इसे किसी भी अनुपात में विभाजित किया जा सकता है। सरणी को दो हिस्सों (n / 2) में विभाजित किया गया है। सबसे खराब मामला जटिलता ओ (एन 2) - सबसे बुरे मामले में तुलना की बहुत आवश्यकता है। ओ (nlogn) - औसत मामले के समान डेटा उपयोग सेट करता है बड़े डेटा सेट के साथ अच्छी तरह से काम नहीं कर सकता। आकार के बावजूद सभी डेटासेट के साथ अच्छी तरह से काम करता है। अतिरिक्त स्थान इन-प्लेस - अतिरिक्त स्थान की आवश्यकता नहीं है सहायक स्थान संग्रहीत करने के लिए अतिरिक्त स्थान की आवश्यकता नहीं है। छँटाई विधि आंतरिक - डेटा को मुख्य मेमोरी में सॉर्ट किया जाता है। बाहरी - डेटा सरणियों के भंडारण के लिए बाहरी मेमोरी का उपयोग करता है। दक्षता छोटे आकार की सूचियों के लिए तेज़ और कुशल। बड़ी सूचियों के लिए तेज और कुशल। एरे / लिंक से जुड़ी सूची सरणियों के लिए अधिक पसंदीदा। लिंक की गई सूचियों के लिए अच्छी तरह से काम करता है।
निष्कर्ष
जैसा कि नाम से ही पता चलता है, क्विकसॉर्ट वह एल्गोरिथ्म है जो सूची को किसी अन्य छँटाई वाले एल्गोरिदम की तुलना में जल्दी से सॉर्ट करता है। मर्ज सॉर्ट की तरह, क्विक सॉर्ट भी एक विभाजन को अपनाता है और रणनीति को जीतता है।
जैसा कि हम पहले ही देख चुके हैं, त्वरित प्रकार का उपयोग करके हम सूची को पिवट तत्व का उपयोग करके उप-सरणियों में विभाजित करते हैं। फिर इन उप-सरणियों को स्वतंत्र रूप से क्रमबद्ध किया जाता है। एल्गोरिथ्म के अंत में, संपूर्ण सरणी पूरी तरह से सॉर्ट की जाती है।
Quicksort तेजी से है और डेटा संरचनाओं को सॉर्ट करने के लिए कुशलता से काम करता है। क्विकॉर्ट एक लोकप्रिय छँटाई एल्गोरिथ्म है और कभी-कभी मर्ज सॉर्ट एल्गोरिथ्म पर भी पसंद किया जाता है।
अपने अगले ट्यूटोरियल में, हम शेल के बारे में विस्तार से चर्चा करेंगे।
=> यहाँ सरल सी ++ प्रशिक्षण श्रृंखला देखें।
अनुशंसित पाठ
- MongoDB सॉर्ट () उदाहरण के साथ विधि
- सिंटैक्स, विकल्प और उदाहरण के साथ यूनिक्स सॉर्ट कमांड
- उदाहरणों के साथ C ++ में मर्ज करें
- उदाहरणों के साथ C ++ में ढेर छाँटें
- शैल C ++ में उदाहरणों के साथ
- चयन सी में सी + + उदाहरण के साथ
- उदाहरणों के साथ C ++ में बबल सॉर्ट
- उदाहरणों के साथ C ++ में प्रविष्टि सॉर्ट करें
