हॉल्टिंग कन्वेंशन
जब किसी सूची में तत्वों की संख्या सम होती है, तो सूची को आधा करने का अर्थ है कि सूची का शाब्दिक पहला भाग पहला भाग है, और सूची का शाब्दिक दूसरा भाग दूसरा भाग है। पूरी सूची का मध्य (मध्य) तत्व, पहली सूची का अंतिम तत्व है। इसका मतलब है कि मध्य सूचकांक लंबाई / 2 - 1 है, क्योंकि सूचकांक की गिनती शून्य से शुरू होती है। लंबाई सूची में तत्वों की संख्या है। उदाहरण के लिए, यदि तत्वों की संख्या 8 है, तो सूची के पहले भाग में 4 तत्व हैं और सूची के दूसरे भाग में भी 4 तत्व हैं। यह ठीक है। चूंकि सूचकांक की गिनती 0 से शुरू होती है, मध्य सूचकांक 3 = 8/2 - 1 है।
मामले के बारे में क्या, जब सूची या उप-सूची में तत्वों की संख्या विषम है? प्रारंभ में, लंबाई अभी भी 2 से विभाजित है। परंपरा के अनुसार, इस विभाजन के पहले भाग में तत्वों की संख्या लंबाई / 2 + 1/2 है। सूचकांक की गिनती शून्य से शुरू होती है। मध्य सूचकांक लंबाई / 2 - 1/2 द्वारा दिया जाता है। इसे परंपरा के अनुसार मध्य पद माना जाता है। उदाहरण के लिए, यदि किसी सूची में तत्वों की संख्या 5 है, तो मध्य सूचकांक 2 = 5/2 - 1/2 है। और, सूची के पहले भाग में तीन तत्व और दूसरे भाग में दो तत्व हैं। पूरी सूची का मध्य तत्व सूचकांक 2 पर तीसरा तत्व है, जो मध्य सूचकांक है क्योंकि सूचकांक की गिनती 0 से शुरू होती है।
इस प्रकार विभाजन पूर्णांक अंकगणित का एक उदाहरण है।
तीन मानों का माध्यक
प्रश्न: अनुक्रम की माध्यिका क्या है?
सी बी ए
समाधान:
सूची को आरोही क्रम में व्यवस्थित करें:
ए बी सी
मध्य पद, B, माध्यिका है। यह वह परिमाण है जो अन्य दो परिमाणों के बीच स्थित है।
किसी सूची में माध्यिका की तलाश करना उस तरह का नहीं है। उदाहरण के लिए, बिना छांटे गए 19 तत्वों की सूची में, पहले तत्व के लिए माध्यिका, मध्य तत्व और अंतिम तत्व की आवश्यकता हो सकती है। ये तीन मान आरोही क्रम में नहीं हो सकते हैं; और इसलिए, उनकी अनुक्रमणिका को ध्यान में रखा जाना चाहिए।
त्वरित सॉर्ट के साथ, पूरी सूची और उप-सूचियों के लिए माध्यिका की आवश्यकता होती है। एक सूची (सरणी) में तीन मानों के माध्यिका को देखने के लिए स्यूडोकोड है:
मध्य: =मैं(कम+उच्च) / 2मैंअगरआगमन[मध्य] <आगमन[कम]
अदला-बदली[कम]गिरफ्तारी के साथ[मध्य]
अगरआगमन[उच्च] <आगमन[कम]
अदला-बदली[कम]गिरफ्तारी के साथ[उच्च]
अगरआगमन[मध्य] <आगमन[उच्च]
अदला-बदली[मध्य]गिरफ्तारी के साथ[उच्च]
प्रधान आधार: =आगमन[उच्च]
एआर शब्द का अर्थ है सरणी। यह कोड खंड माध्यिका की तलाश करता है और कुछ छँटाई भी करता है। यह कोड खंड सरल दिखता है, लेकिन यह काफी भ्रमित करने वाला हो सकता है। तो, निम्नलिखित स्पष्टीकरण पर ध्यान दें:
इस ट्यूटोरियल में छँटाई एक सूची तैयार करेगी जहाँ पहला मान सबसे छोटा मान है, और अंतिम मान सबसे बड़ा मान है। अक्षर के साथ, A, Z से छोटा है।
यहाँ, धुरी परिणामी माध्यिका है। निम्न सूची या उप-सूची का निम्नतम सूचकांक है (जरूरी नहीं कि न्यूनतम मूल्य के लिए); उच्च सूची या उप-सूची का उच्चतम सूचकांक है (जरूरी नहीं कि उच्चतम मूल्य के लिए), और मध्य पारंपरिक मध्य सूचकांक है (जरूरी नहीं कि पूरी सूची के मध्य मूल्य के लिए)।
तो, प्राप्त किया जाने वाला माध्य निम्नतम सूचकांक के मूल्य, मध्य सूचकांक के मूल्य और उच्चतम सूचकांक के मूल्य के बीच है।
कोड में, पारंपरिक मध्य सूचकांक पहले प्राप्त किया जाता है। इस शुरुआत में, सूची को क्रमबद्ध नहीं किया गया है। तीन मूल्यों की तुलना और आरोही क्रम में कुछ पुनर्व्यवस्था एक ही समय में होनी है। पहला if-statement निम्नतम सूचकांक और मध्य सूचकांक के मूल्य की तुलना करता है। यदि मध्य सूचकांक का सूचकांक निम्नतम सूचकांक से कम है, तो दो मान स्थिति की अदला-बदली करते हैं। यह छँटाई शुरू करता है और सूची या उप-सूची में मूल्यों की व्यवस्था को बदलता है। दूसरा if-statement उच्चतम सूचकांक और निम्नतम सूचकांक के मूल्य की तुलना करता है। यदि उच्चतम सूचकांक का सूचकांक निम्नतम सूचकांक से कम है, तो दो मान स्थिति की अदला-बदली करते हैं। यह सूची या उप-सूची में मूल्यों की व्यवस्था को कुछ छँटाई और बदलता रहता है। तीसरा if-statement मध्य सूचकांक और उच्चतम सूचकांक के मूल्य की तुलना करता है। यदि उच्चतम सूचकांक का सूचकांक मध्य सूचकांक से कम है, तो दो मान स्थिति की अदला-बदली करते हैं। यहां कुछ छँटाई या पुनर्व्यवस्था भी हो सकती है। यह तीसरी अगर-हालत पिछले दो की तरह नहीं है।
इन तीन स्वैप के अंत में, विचाराधीन तीन मानों का मध्य मान A[उच्च] होगा, जिसकी मूल सामग्री को कोड खंड में बदल दिया गया होगा। उदाहरण के लिए, क्रमबद्ध अनुक्रम पर विचार करें:
सी बी ए
हम पहले से ही जानते हैं कि माध्यिका B है। हालाँकि, यह सिद्ध होना चाहिए। यहाँ उद्देश्य उपरोक्त कोड खंड का उपयोग करके इन तीन मानों का माध्यिका प्राप्त करना है। पहला if-statement B और C की तुलना करता है। यदि B, C से कम है, तो B और C की स्थिति बदली जानी चाहिए। B, C से छोटा है, इसलिए नई व्यवस्था बन जाती है:
बी सी ए
ध्यान दें, निम्नतम सूचकांक और मध्य सूचकांक के मान बदल गए हैं। दूसरा अगर-स्टेटमेंट ए और बी की तुलना करता है। अगर ए बी से कम है, तो ए और बी की स्थिति को बदलना होगा। A, B से छोटा है, इसलिए नई व्यवस्था बन जाती है:
ए सी बी
ध्यान दें, उच्चतम सूचकांक और निम्नतम सूचकांक के मान बदल गए हैं। तीसरा इफ-स्टेटमेंट सी और बी की तुलना करता है। यदि सी, बी से कम है, तो सी और बी की स्थिति को स्वैप करना होगा। C, B से कम नहीं है, इसलिए कोई अदला-बदली नहीं होती है। नई व्यवस्था पूर्व की तरह बनी हुई है, अर्थात्:
ए सी बी
बी माध्यिका है, जो है, ए [उच्च], और यह धुरी है। तो, धुरी सूची या उप-सूची के अंतिम छोर पर पैदा होती है।
अदला-बदली समारोह
क्विक सॉर्ट द्वारा आवश्यक एक अन्य विशेषता स्वैपिंग फ़ंक्शन है। स्वैपिंग फ़ंक्शन, दो चर के मानों का आदान-प्रदान करता है। स्वैपिंग फ़ंक्शन के लिए स्यूडोकोड है:
स्वैप को परिभाषित करें(एक्स,तथा)अस्थायी: =एक्स
एक्स: =तथा
तथा: =अस्थायी
यहाँ, x और y वास्तविक मूल्यों को संदर्भित करते हैं, न कि प्रतियों को।
इस आलेख में छँटाई एक सूची तैयार करेगी जहाँ पहला मान सबसे छोटा मान है, और अंतिम मान सबसे बड़ा मान है।
लेख सामग्री
त्वरित क्रमबद्ध एल्गोरिदम
एक क्रमबद्ध सूची को क्रमबद्ध करने का सामान्य तरीका पहले दो मानों पर विचार करना है। यदि वे क्रम में नहीं हैं, तो उन्हें क्रम में रखें। इसके बाद, पहले तीन मानों पर विचार करें। यह देखने के लिए पहले दो को स्कैन करें कि तीसरा मान कहां फिट बैठता है और इसे उचित रूप से फिट करता है। फिर, पहले चार मूल्यों पर विचार करें। यह देखने के लिए पहले तीन मानों को स्कैन करें कि चौथा मान कहां फिट बैठता है और इसे उचित रूप से फिट करता है। इस प्रक्रिया को तब तक जारी रखें जब तक कि पूरी सूची क्रमबद्ध न हो जाए।
यह प्रक्रिया, जिसे कंप्यूटर प्रोग्रामिंग भाषा में ब्रूट-फोर्स सॉर्ट के रूप में भी जाना जाता है, बहुत धीमी है। क्विक सॉर्ट एल्गोरिथम बहुत तेज प्रक्रिया के साथ आता है।
क्विकसॉर्ट एल्गोरिथम के चरण इस प्रकार हैं:
- सुनिश्चित करें कि क्रमबद्ध सूची में सॉर्ट करने के लिए कम से कम 2 नंबर हैं।
- सूची के लिए अनुमानित केंद्रीय मान प्राप्त करें, जिसे पिवट कहा जाता है। माध्यिका, जैसा कि ऊपर वर्णित है, धुरी प्राप्त करने का एक तरीका है। अलग-अलग तरीके अपने फायदे और नुकसान के साथ आते हैं। - बाद में देख।
- सूची का विभाजन। इसका मतलब है, पिवट को सूची में रखें। इस प्रकार, बाईं ओर के सभी तत्व पिवट मान से कम हैं, और दाईं ओर के सभी तत्व पिवट मान से अधिक या उसके बराबर हैं। विभाजन के विभिन्न तरीके हैं। प्रत्येक विभाजन विधि अपने फायदे और नुकसान के साथ आती है। बंटवारा फूट डालो और जीतो के प्रतिमान में विभाजित है।
- नई उप-सूची युग्मों के लिए चरण 1, 2, और 3 को पुनरावर्ती रूप से दोहराएं जो पूरी सूची के सॉर्ट होने तक उभर कर आते हैं। यह फूट डालो और जीतो के प्रतिमान में विजय प्राप्त कर रहा है।
त्वरित सॉर्ट स्यूडोकोड है:
एल्गोरिथम क्विकसॉर्ट(आगमन,कम,उच्च)हैअगरकम<उच्च तो
प्रधान आधार(कम,उच्च)
पी: =PARTITION(आगमन,कम,उच्च)
जल्दी से सुलझाएं(आगमन,कम,पी- 1)
जल्दी से सुलझाएं(आगमन,पी+ 1,उच्च)
एक विभाजन छद्म कोड
इस ट्यूटोरियल में प्रयुक्त विभाजन स्यूडोकोड है:
एल्गोरिथम विभाजन(आगमन,कम,उच्च)हैप्रधान आधार: =आगमन[उच्च]
मैं: =कम
जे: =उच्च
करना
करना
++मैं
जबकि(आगमन[मैं] <प्रधान आधार)
करना
-जे
जबकि(आगमन[जे] >प्रधान आधार)
अगर (मैं<जे)
अदला-बदली[मैं]गिरफ्तारी के साथ[जे]
जबकि(मैं<जे)
अदला-बदली[मैं]गिरफ्तारी के साथ[उच्च]
वापसीमैं
नीचे दिए गए त्वरित क्रम के उदाहरण में, इस कोड का उपयोग किया जाता है:
त्वरित क्रम का चित्रण
वर्णमाला के अक्षरों की निम्नलिखित क्रमबद्ध सूची (सरणी) पर विचार करें:
क्यू डब्ल्यू ई आर टी वाई यू आई ओ पी
निरीक्षण द्वारा, क्रमबद्ध सूची है:
ई आई ओ पी क्यू आर टी यू डब्ल्यू वाई
सॉर्ट की गई सूची अब उपरोक्त एल्गोरिथम और स्यूडोकोड सेगमेंट का उपयोग करके, अनसोल्ड सूची से सिद्ध होगी:
क्यू डब्ल्यू ई आर टी वाई यू आई ओ पी
पहली धुरी arr[0]=Q, arr[4]=T, और arr[9]=P से निर्धारित होती है, और इसे Q के रूप में पहचाना जाता है और सूची के सबसे दाईं ओर रखा जाता है। तो, किसी भी पिवट फ़ंक्शन सॉर्टिंग वाली सूची बन जाती है:
पी डब्ल्यू ई आर टी वाई यू आई ओ क्यू
वर्तमान धुरी Q है। धुरी प्रक्रिया ने कुछ छोटी छँटाई की और P को पहले स्थान पर रखा। परिणामी सूची को पुनर्व्यवस्थित (विभाजित) करना पड़ता है, जैसे कि, बाईं ओर के सभी तत्व मूल्य में छोटे होते हैं, फिर धुरी और धुरी के दाईं ओर के सभी तत्व, धुरी के बराबर या उससे अधिक होते हैं। कंप्यूटर निरीक्षण द्वारा विभाजन नहीं कर सकता। तो, यह इंडेक्स और उपरोक्त विभाजन एल्गोरिदम का उपयोग करके करता है।
निम्न और उच्च इंडेक्स अब 0 और 9 हैं। इसलिए, कंप्यूटर इंडेक्स 0 से स्कैन करके शुरू होगा जब तक कि यह एक इंडेक्स तक नहीं पहुंच जाता, जिसका मान पिवट के बराबर या उससे अधिक है और अस्थायी रूप से वहां रुक जाता है। यह उच्च (दाएं) छोर, इंडेक्स 9 से नीचे आते हुए भी स्कैन करेगा, जब तक कि यह एक ऐसे इंडेक्स तक नहीं पहुंच जाता जिसका मान पिवट से कम या उसके बराबर है और अस्थायी रूप से वहीं रुक जाता है। इसका अर्थ है रुकने की दो स्थितियाँ। यदि i, वृद्धिशील सूचकांक चर, निम्न से अभी तक घटते सूचकांक चर के बराबर या उससे अधिक नहीं है, तो उच्च से j, तो इन दो मानों की अदला-बदली की जाती है। वर्तमान स्थिति में, दोनों सिरों से स्कैनिंग W और O पर रुक गई है। तो सूची बन जाती है:
पी ओ ई आर टी वाई यू आई डब्ल्यू क्यू
धुरी अभी भी Q है। विपरीत दिशाओं में स्कैनिंग जारी है और तदनुसार रुक जाती है। यदि i अभी तक j के बराबर या उससे बड़ा नहीं है, तो दो मान जिस पर दोनों सिरों से स्कैन करना बंद कर दिया गया है, अदला-बदली कर दी जाती है। इस बार, दोनों सिरों से स्कैनिंग R और I पर रुक गई। इसलिए, सूची की व्यवस्था बन जाती है:
पी ओ ई आई टी वाई यू आर डब्ल्यू क्यू
धुरी अभी भी Q है। विपरीत दिशाओं में स्कैनिंग जारी है और तदनुसार रुक जाती है। यदि i अभी तक j के बराबर या उससे बड़ा नहीं है, तो जिन दो मानों पर स्कैनिंग रुकी है, उन्हें स्वैप किया जाता है। इस बार, दोनों सिरों से स्कैनिंग i के लिए T पर और j के लिए I पर रुक गई। मैं और जे मिले हैं या पार कर चुके हैं। तो, कोई अदला-बदली नहीं हो सकती है। सूची समान रहती है:
पी ओ ई आई टी वाई यू आर डब्ल्यू क्यू
इस बिंदु पर, छँटाई में धुरी, Q को अपनी अंतिम स्थिति में रखा जाना चाहिए। यह गिरफ्तारी [i] को एआर [उच्च] के साथ स्वैप करके, टी और क्यू को स्वैप करके किया जाता है। सूची बन जाती है:
पी ओ ई आई क्यू वाई यू आर डब्ल्यू टी
इस बिंदु पर, पूरी सूची के लिए विभाजन समाप्त हो गया है। धुरी = क्यू ने अपनी भूमिका निभाई है। अब तीन उप-सूचियाँ हैं, जो इस प्रकार हैं:
पी ओ ई आई क्यू वाई यू आर डब्ल्यू टी
विभाजन प्रतिमान में विभाजन और विजय (छँटाई) है। Q अपनी सही छँटाई स्थिति में है। Q के बाईं ओर का प्रत्येक तत्व Q से छोटा है, और Q के दाईं ओर का प्रत्येक तत्व Q से बड़ा है। हालाँकि, बाईं सूची को अभी भी क्रमबद्ध नहीं किया गया है; और सही सूची अभी भी क्रमबद्ध नहीं है। लेफ्ट सब-लिस्ट और राइट सब-लिस्ट को सॉर्ट करने के लिए पूरे क्विक सॉर्ट फंक्शन को रिकर्सिवली कॉल करना पड़ता है। क्विक सॉर्ट की इस रिकॉलिंग को जारी रखना है; नई उप-सूचियां तब तक विकसित होंगी जब तक कि पूरी मूल सूची पूरी तरह से क्रमबद्ध नहीं हो जाती। क्विक सॉर्ट फंक्शन के प्रत्येक रिकॉल के लिए, संबंधित राइट सब-लिस्ट में भाग लेने से पहले बाईं उप-सूची में पहले भाग लिया जाता है। प्रत्येक उप-सूची के लिए एक नई धुरी प्राप्त करनी होगी।
उप-सूची के लिए:
पी ओ ई आई
P, O और I के लिए धुरी (माध्यिका) निर्धारित की जाती है। धुरी ओ होगी। इस उप-सूची के लिए, और पूरी सूची से संबंधित, नई गिरफ्तारी [निम्न] गिरफ्तारी [0] है, और नई गिरफ्तारी [उच्च] अंतिम गिरफ्तारी है [i-1] = गिरफ्तारी [ ४-१] = एआर [३], जहां मैं पिछले विभाजन से अंतिम धुरी सूचकांक है। पिवट () फ़ंक्शन को कॉल करने के बाद, नया पिवट मान, पिवट = ओ। पिवट फ़ंक्शन और पिवट मान के बीच भ्रमित न हों। पिवट फ़ंक्शन कुछ छोटी छँटाई कर सकता है और पिवट को उप-सूची के सबसे दाईं ओर रख सकता है। यह उप-सूची बन जाती है,
आई पी ई ओ
इस योजना के साथ, फ़ंक्शन कॉल के बाद धुरी हमेशा उप-सूची या सूची के दाहिने छोर पर समाप्त होती है। दोनों सिरों से स्कैनिंग arr[0] और arr[3] से शुरू होती है जब तक कि i और j मिलते या क्रॉस नहीं करते। तुलना पिवट = ओ के साथ की जाती है। पहला स्टॉप पी और ई पर होता है। उनकी अदला-बदली की जाती है, और नई उप-सूची बन जाती है:
आई ई पी ओ
दोनों सिरों से स्कैनिंग जारी है, और नए स्टॉप I के लिए P और j के लिए E पर हैं। अब i और j मिल गए हैं या पार हो गए हैं। तो उप-सूची समान रहती है:
आई ई पी ओ
उप-सूची या सूची का विभाजन तब समाप्त होता है जब धुरी को उसकी अंतिम स्थिति में रखा जाता है। तो, arr[i] और arr[high] के लिए नए मानों की अदला-बदली की जाती है। यानी P और O की अदला-बदली की जाती है। नई उप-सूची बन जाती है:
मैं ई ओ पी
ओ अब पूरी सूची के लिए अपने अंतिम स्थान पर है। धुरी के रूप में इसकी भूमिका समाप्त हो गई है। उप-सूची को वर्तमान में तीन और सूचियों में विभाजित किया गया है, जो इस प्रकार हैं:
मैं ई ओ पी
इस बिंदु पर, पहली सही उप-सूची के त्वरित क्रम को कॉल करना होगा। हालांकि इसे नहीं कहा जाएगा। इसके बजाय, इसे नोट किया जाएगा और आरक्षित किया जाएगा, जिसे बाद में बुलाया जाएगा। चूंकि विभाजन समारोह के बयानों को क्रियान्वित किया जा रहा था, फ़ंक्शन के शीर्ष से, यह बाईं उप-सूची के लिए त्वरित सॉर्ट है जिसे अभी कॉल किया जाना चाहिए (पिवट () के बाद) कहा जाता है। इसे सूची के लिए बुलाया जाएगा:
अर्थात
यह I और E के माध्यिका की तलाश से शुरू होगा। यहाँ, arr[low] = I, arr[mid] = I और arr[high] = E. तो माध्यिका, पिवट, को पिवट एल्गोरिथम द्वारा निर्धारित किया जाना चाहिए , I. हालांकि, उपरोक्त धुरी छद्म कोड ई के रूप में धुरी का निर्धारण करेगा। यह त्रुटि यहां होती है क्योंकि उपरोक्त छद्म कोड तीन तत्वों के लिए है न कि दो। नीचे दिए गए कार्यान्वयन में, कोड में कुछ समायोजन है। उप-सूची बन जाती है,
ई मैं
फ़ंक्शन कॉल के बाद पिवट हमेशा उप-सूची या सूची के दाहिने छोर पर समाप्त होता है। दोनों सिरों से स्कैनिंग arr[0] और arr[1] से शुरू होती है, जब तक कि i और j मिलें या क्रॉस न करें। तुलना पिवट = I के साथ की जाती है। पहला और एकमात्र स्टॉप I और E पर है: I पर i और E के लिए j। अब i और j मिले हैं या पार कर चुके हैं। तो, उप-सूची समान रहती है:
ई मैं
उप-सूची या सूची का विभाजन तब समाप्त होता है जब धुरी को उसकी अंतिम स्थिति में रखा जाता है। तो, arr[i] और arr[high] के लिए नए मानों की अदला-बदली की जाती है। यहाँ ऐसा होता है कि arr[i] = I और arr[high] = I. तो, वही मान अपने आप बदल जाता है। नई उप-सूची बन जाती है:
ई मैं
मैं अब पूरी सूची के लिए अपने अंतिम स्थान पर हूं। धुरी के रूप में इसकी भूमिका समाप्त हो गई है। उप-सूची अब दो और सूचियों में विभाजित है, जो हैं,
ई मैं
अब, धुरी अब तक क्यू, ओ, और आई है। धुरी अपने अंतिम स्थान पर समाप्त होती है। किसी एकल तत्व की उप-सूची, जैसे कि उपरोक्त P, भी अपने अंतिम स्थान पर समाप्त होती है।
इस बिंदु पर, पहली बाईं उप-सूची को पूरी तरह से सॉर्ट किया गया है। और छँटाई प्रक्रिया अब यहाँ है:
ई आई ओ पी क्यू वाई यू आर डब्ल्यू टी
पहली सही उप-सूची:
वाई यू आर डब्ल्यू टी
अभी भी क्रमबद्ध करने की आवश्यकता है।
प्रथम अधिकार उप-सूची पर विजय प्राप्त करना
याद रखें कि पहली दाहिनी उप-सूची के लिए त्वरित सॉर्ट कॉल को नोट किया गया था और निष्पादित होने के बजाय आरक्षित किया गया था। इस बिंदु पर, इसे निष्पादित किया जाएगा। और इसलिए, नई गिरफ्तारी [निम्न] = गिरफ्तार [५] = गिरफ्तारी [क्यूपिवोट इंडेक्स + १], और नई गिरफ्तारी [उच्च] गिरफ्तारी [९] बनी हुई है। गतिविधियों का एक समान सेट जो पहली बाईं उप-सूची के लिए हुआ था, यहां होगा। और यह पहली सही उप-सूची को क्रमबद्ध किया गया है:
आर टी यू डब्ल्यू वाई
और मूल अवर्गीकृत सूची को इस प्रकार क्रमबद्ध किया गया है:
ई आई ओ पी क्यू आर टी यू डब्ल्यू वाई
जावा कोडिंग
जावा में एल्गोरिदम डालना उपरोक्त सभी छद्म कोड खंडों को एक वर्ग में जावा विधियों में रखना है। यह मत भूलो कि कक्षा में एक मुख्य () विधि होनी चाहिए जो कि क्विकॉर्ट () फ़ंक्शन को अनसोल्ड एरे के साथ कॉल करेगी।
धुरी () विधि
जावा पिवट () विधि जो मान, पिवट लौटाती है, होनी चाहिए:
शून्यप्रधान आधार(charआगमन[], NSकम, NSउच्च) {NSमध्य= (कम+उच्च) / 2;
अगर (आगमन[मध्य] <आगमन[कम])
विनिमय(आगमन,कम,मध्य);
अगर (आगमन[उच्च] <आगमन[कम])
विनिमय(आगमन,कम,उच्च);
अगर ((उच्च-कम) > 2) {
अगर (आगमन[मध्य] <आगमन[उच्च])
विनिमय(आगमन,मध्य,उच्च);
}
}
स्वैप () विधि
स्वैप () विधि होनी चाहिए:
शून्यविनिमय(charआगमन[], NSएक्स, NSतथा) {charअस्थायी=आगमन[एक्स];
आगमन[एक्स] =आगमन[तथा];
आगमन[तथा] =अस्थायी;
}
क्विकॉर्ट () विधि
Quicksort() विधि होनी चाहिए:
शून्यजल्दी से सुलझाएं(charआगमन[], NSकम, NSउच्च) {अगर (कम<उच्च) {
प्रधान आधार(आगमन,कम,उच्च);
NSपी=PARTITION(आगमन,कम,उच्च);
जल्दी से सुलझाएं(आगमन,कम,पी- 1);
जल्दी से सुलझाएं(आगमन,पी+ 1,उच्च);
}
}
विभाजन () विधि
विभाजन () विधि होनी चाहिए:
NSPARTITION(charआगमन[], NSकम, NSउच्च) {charप्रधान आधार=आगमन[उच्च];
NSमैं=कम;
NSजे=उच्च;
करना {
करना
++मैं;
जबकि(आगमन[मैं] <प्रधान आधार);
करना
-जे;
जबकि(आगमन[जे] >प्रधान आधार);
अगर (मैं<जे)
विनिमय(आगमन,मैं,जे);
}जबकि(मैं<जे);
विनिमय(आगमन,मैं,उच्च);
वापसीमैं;
}
मुख्य () विधि
मुख्य () विधि हो सकती है:
सह लोकस्थिर शून्यमुख्य(डोरी[]args) {charआगमन[] = {'क्यू', 'में', 'तथा', 'आर', 'टी', 'तथा', 'यू', 'मैं', 'या', 'पी'};
TheClass QuickSort= नयाकक्षा();
जल्दी से सुलझाएं।जल्दी से सुलझाएं(आगमन, 0, 9);
प्रणाली।बाहर.प्रिंट्लन('सॉर्ट किए गए तत्व:');
के लिये(NSमैं=0;मैं<10;मैं++) {
प्रणाली।बाहर.प्रिंट(आगमन[मैं]);प्रणाली।बाहर.प्रिंट('');
}
प्रणाली।बाहर.प्रिंट्लन();
}
उपरोक्त सभी विधियों को एक वर्ग में रखा जा सकता है।
निष्कर्ष
क्विक सॉर्ट एक सॉर्टिंग एल्गोरिथम है जो डिवाइड-एंड-कॉनकॉर प्रतिमान का उपयोग करता है। यह एक क्रमबद्ध सूची को दो या तीन उप-सूचियों में विभाजित करके शुरू होता है। इस ट्यूटोरियल में, क्विक सॉर्ट ने एक सूची को तीन उप-सूचियों में विभाजित किया है: एक बाईं उप-सूची, एक एकल तत्व की एक मध्य सूची, और एक सही उप-सूची। त्वरित क्रम में जीतना किसी सूची या उप-सूची को विभाजित करते समय, पिवट मान का उपयोग करके विभाजित करना है। इस ट्यूटोरियल ने जावा कंप्यूटर भाषा में क्विक सॉर्ट के एक कार्यान्वयन की व्याख्या की है।
लेखक के बारे में
गुलदाउदी Forcha
प्रथम सिद्धांतों और संबंधित श्रृंखला से गणित एकीकरण के खोजकर्ता। तकनीकी शिक्षा में मास्टर डिग्री, इलेक्ट्रॉनिक्स और कंप्यूटर सॉफ्टवेयर में विशेषज्ञता। बीएससी इलेक्ट्रॉनिक्स। मेरे पास कंप्यूटिंग और दूरसंचार में मास्टर स्तर का ज्ञान और अनुभव भी है। २०,००० लेखकों में से, मैं devarticles.com पर ३७वां सर्वश्रेष्ठ लेखक था। मैं इन क्षेत्रों में 10 से अधिक वर्षों से काम कर रहा हूं।
सभी पोस्ट देखेंसंबंधित Linux HINT POSTS
- जावा में स्ट्रिंग्स की तुलना करना
- जावा में हैश मैप का उपयोग कैसे करें
- जावा में त्वरित क्रमबद्ध समझाया गया
- जावा में बाइनरी ट्री प्रीऑर्डर ट्रैवर्सल
- जावा में मर्ज सॉर्ट समझाया गया
- जावा में स्कैनर का उपयोग कैसे करें
- जावा फाइल करने के लिए लिखें