क्विकसॉर्ट एल्गोरिथम जावास्क्रिप्ट में

क्विक सॉर्ट क्या है?

त्वरित सॉर्ट एल्गोरिथ्म डिवाइड और जीत दृष्टिकोण का अनुसरण करता है। यह कुछ हालत के आधार पर तत्वों को छोटे भागों में विभाजित करता है और उन विभाजित छोटे भागों पर क्रमिक संचालन करता है।

क्विक सॉर्ट एल्गोरिथ्म किसी भी प्रोग्रामिंग भाषा में सबसे अधिक इस्तेमाल किया जाने वाला और लोकप्रिय एल्गोरिदम है। लेकिन, यदि आप एक जावास्क्रिप्ट डेवलपर हैं, तो आप सॉर्ट () के बारे में सुन सकते हैं जो पहले से ही जावास्क्रिप्ट में उपलब्ध है। फिर, आप सोच रहे होंगे कि इस क्विक सॉर्ट एल्गोरिथ्म की आवश्यकता क्या है। इसे समझने के लिए, पहले हमें यह देखना होगा कि जावास्क्रिप्ट में क्या छंटाई है और डिफ़ॉल्ट क्या है।

छंटनी क्या है?

छंटनी और कुछ नहीं है, लेकिन हम चाहते हैं कि आदेश में तत्वों की व्यवस्था है। आप अपने स्कूल या कॉलेज के दिनों में इसके पार आ गए होंगे। जैसे छोटे से बड़े (आरोही) या अधिक से छोटे (अवरोही) से संख्याओं की व्यवस्था करना जो हमने अब तक देखा है और उसे क्रमबद्धता कहा जाता है।

जावास्क्रिप्ट में डिफ़ॉल्ट छँटाई

जैसा कि पहले उल्लेख किया गया है, जावास्क्रिप्ट में सॉर्ट () है । आइए हम कुछ उदाहरणों जैसे [5,3,7,6,2,9] के साथ एक उदाहरण लेते हैं और आरोही क्रम में इस सरणी तत्वों को क्रमबद्ध करना चाहते हैं। आइटम सरणी पर बस सॉर्ट () कॉल करें और यह आरोही क्रम में सरणी तत्वों को सॉर्ट करता है।

कोड:

var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]

जावास्क्रिप्ट में डिफ़ॉल्ट सॉर्ट () पर त्वरित सॉर्ट चुनने का कारण क्या है

हालांकि सॉर्ट () हम चाहते हैं कि परिणाम देता है, समस्या यह है कि यह सरणी तत्वों को किस तरह से निहित है। जावास्क्रिप्ट में डिफ़ॉल्ट सॉर्ट () मोज़िला फ़ायरफ़ॉक्स और सफारी द्वारा क्रोम और मर्ज प्रकार के V8 इंजन द्वारा सम्मिलन प्रकार का उपयोग करता है ।

लेकिन, अन्य यह उपयुक्त नहीं है यदि आपको बड़ी संख्या में तत्वों को सॉर्ट करने की आवश्यकता है। तो, समाधान बड़े डेटासेट के लिए त्वरित सॉर्ट का उपयोग करना है।

इसलिए, पूरी तरह से समझने के लिए, आपको यह जानने की जरूरत है कि क्विक सॉर्ट कैसे काम करता है और हमें अब इसे विस्तार से देखना है।

त्वरित प्रकार क्या है?

त्वरित प्रकार डिवाइड और जीत एल्गोरिथ्म का अनुसरण करता है। यह कुछ स्थिति के आधार पर छोटे भागों में तत्वों को विभाजित कर रहा है और उन विभाजित छोटे भागों पर क्रमबद्ध संचालन कर रहा है। इसलिए, यह बड़े डेटासेट के लिए अच्छा काम करता है। तो, यहाँ पर सरल शब्दों में क्विक सॉर्ट कैसे काम करता है, इसके चरण दिए गए हैं।

पहले एक तत्व का चयन करें जिसे धुरी तत्व कहा जाता है।
अगला, चयनित सरणी तत्व के साथ सभी सरणी तत्वों की तुलना करें और उन्हें इस तरह से व्यवस्थित करें कि, धुरी तत्व की तुलना में कम तत्वों को छोड़ दिया जाए और धुरी से अधिक यह सही हो।
अंत में, बाएँ और दाएँ पक्ष तत्वों पर समान तत्वों को धुरी तत्व पर करें।

तो, यह त्वरित प्रकार की मूल रूपरेखा है। यहां वे चरण हैं, जिन्हें त्वरित क्रमबद्ध करने के लिए एक के बाद एक करने की आवश्यकता है।

क्विकॉर्ट काम कैसे करता है

पहले सरणी में "धुरी" तत्व ढूंढें ।
सरणी के पहले तत्व पर बाएं सूचक को प्रारंभ करें।
सरणी के अंतिम तत्व पर दायाँ सूचक प्रारंभ करें।
बाएं पॉइंटर के साथ इंगित करने वाले तत्व की तुलना करें और यदि यह पिवट तत्व से कम है, तो बाएं पॉइंटर को दाईं ओर ले जाएं (1 को बाएं इंडेक्स में जोड़ें)। इसे तब तक जारी रखें जब तक बाईं ओर का तत्व धुरी तत्व से अधिक या उसके बराबर न हो।
सही पॉइंटर से इंगित करने वाले तत्व की तुलना करें और यदि यह पिवट एलिमेंट से अधिक है, तो दाएं पॉइंटर को बाईं ओर ले जाएं (1 को राइट इंडेक्स में घटाएं)। इसे तब तक जारी रखें जब तक कि दाईं ओर का तत्व धुरी तत्व से कम या उसके बराबर न हो।
जांचें कि क्या बाएं पॉइंटर राइट पॉइंटर से कम या बराबर है, तो इन पॉइंटर्स के स्थानों में तत्वों को देखा।
बाएं पॉइंटर को बढ़ाएं और दाएं पॉइंटर को बढ़ाएं।
यदि बाएं पॉइंटर का इंडेक्स अभी भी राइट पॉइंटर के इंडेक्स से कम है, तो प्रक्रिया को दोहराएं; बाएं सूचक के सूचकांक को वापस करें।

तो, आइए इन चरणों को एक उदाहरण के साथ देखते हैं। आइए हम उन तत्वों की सरणी पर विचार करें जिन्हें हमें क्रमबद्ध करने की आवश्यकता है [5,3,7,6,2,9]।

पिवट तत्व का निर्धारण करें

लेकिन क्विक सॉर्ट के साथ आगे बढ़ने से पहले, पिवट तत्व का चयन एक प्रमुख भूमिका निभाता है। यदि आप पहले तत्व को धुरी तत्व के रूप में चुनते हैं, तो यह क्रमबद्ध सरणी में सबसे खराब प्रदर्शन देता है। इसलिए, हमेशा मध्य तत्व (2 से विभाजित सरणी की लंबाई) को धुरी तत्व के रूप में चुनना उचित है और हम ऐसा ही करते हैं।

त्वरित प्रदर्शन करने के चरण यहां दिए गए हैं, जिन्हें एक उदाहरण के साथ दिखाया जा रहा है [5,3,7,6,2,9]।

चरण 1: मध्य तत्व के रूप में धुरी निर्धारित करें। तो, 7 धुरी तत्व है।

चरण 2: क्रमशः सरणी के पहले और अंतिम तत्वों के रूप में बाएं और दाएं संकेत शुरू करें। तो, बायाँ सूचक सूचकांक 0 पर 5 की ओर इशारा कर रहा है और दायाँ सूचक 9 सूचकांक 5 पर इंगित कर रहा है ।

चरण 3: धुरी तत्व के साथ बाएं सूचक पर तत्व की तुलना करें। चूंकि, इंडेक्स 1 के दाईं ओर 5 <6 शिफ्ट पॉइंटर छोड़ा गया है।

चरण 4: अब, अभी भी 3 <6 इसलिए दाएं से बाएं सूचक को एक और सूचकांक में स्थानांतरित करें। तो अब 7> 6 स्टॉप बाएं पॉइंटर को बढ़ाता है और अब लेफ्ट पॉइंटर 2 इंडेक्स पर है।

चरण 5: अब, सही सूचक पर धुरी तत्व के साथ मूल्य की तुलना करें। चूंकि 9> 6 दाएं पॉइंटर को बाईं ओर ले जाते हैं। अब 2 <6 के रूप में सही पॉइंटर को आगे बढ़ाना बंद करें।

चरण 6: बाएँ और दाएँ दोनों बिंदुओं पर मौजूद मानों को एक-दूसरे के साथ स्वैप करें।

चरण 7: दोनों बिंदुओं को एक और कदम बढ़ाएं।

STEP 8: 6 = 6 के बाद से, पॉइंटर्स को एक और स्टेप पर ले जाएं और बाएं पॉइंटर को राइट पॉइंटर से क्रॉस करें और लेफ्ट पॉइंटर के इंडेक्स को वापस करें।

तो, यहाँ ऊपर दिए गए दृष्टिकोण के आधार पर, हमें तत्वों की अदला-बदली के लिए कोड लिखना होगा और उपरोक्त चरणों में बताए गए ऐरे को पार्टीशन करना होगा।

जावास्क्रिप्ट में दो नंबर स्वैप करने के लिए कोड:

function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}

उपरोक्त चरणों में दिए गए विभाजन को करने के लिए कोड:

function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}

पुनरावर्ती ऑपरेशन करें

एक बार जब आप उपरोक्त चरणों का प्रदर्शन करते हैं, तो बाएं पॉइंटर का सूचकांक वापस आ जाएगा और हमें उस हिस्से को विभाजित करने के लिए सरणी को विभाजित करने और त्वरित प्रदर्शन करने के लिए उपयोग करने की आवश्यकता है। इसलिए, इसे डिवाइड और कॉन्कर एल्गोरिथ्म कहा जाता है।

इसलिए, त्वरित सॉर्ट तब तक किया जाता है जब तक कि बाएं एरे और राइट एरे पर सभी तत्वों को सॉर्ट नहीं किया जाता है।

नोट: त्वरित क्रम एक ही सरणी पर किया जाता है और इस प्रक्रिया में कोई नई सरणियाँ नहीं बनाई जाती हैं।

तो, हमें इस विभाजन () को ऊपर वर्णित करने की आवश्यकता है और इसके आधार पर हम सरणी को भागों में विभाजित करते हैं। तो यहां वह कोड है जहां आप इसका उपयोग करते हैं,

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

पूरा त्वरित सॉर्ट कोड:

var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]