चयन सॉर्टिंग Java उदाहरण सहित कार्यक्रम
जेम्स हार्टमैन
⚡ स्मार्ट सारांश
चयन क्रमबद्ध करें Java यह सरणी के अव्यवस्थित भाग को बार-बार स्कैन करता है, शेष सबसे छोटा मान ढूंढता है, और उसे उसकी स्थिति में स्वैप कर देता है, इनपुट क्रम की परवाह किए बिना अधिकतम n-1 विनिमय के साथ काम पूरा करता है।
चयन सॉर्ट कैसे काम करता है?
चयन सॉर्ट एक सरल सॉर्टिंग एल्गोरिथ्म को इस प्रकार कार्यान्वित करता है:
- एल्गोरिथ्म बार-बार सबसे कम तत्व की खोज करता है।
- वर्तमान तत्व को सबसे कम मान वाले तत्व से बदलें
- चयन सॉर्ट के प्रत्येक पुनरावृत्ति/पास के साथ, तत्वों की अदला-बदली हो जाती है।
इसलिए प्रत्येक पास निम्नलिखित के साथ व्यवहार करता है सरणी दो क्षेत्रों के रूप में: एक क्रमबद्ध ब्लॉक जो बाईं ओर से बढ़ता है और एक अव्यवस्थित ब्लॉक जो दाईं ओर से सिकुड़ता है। एल्गोरिदम अव्यवस्थित ब्लॉक में चलता है, उसे मिलने वाले सबसे छोटे मान के सूचकांक को याद रखता है, और उस मान को पहली अव्यवस्थित स्थिति से बदल देता है।
क्योंकि प्रति पास केवल एक ही अदला-बदली होती है, इसलिए n तत्वों की एक सरणी को अधिकतम n-1 अदला-बदली के बाद क्रमबद्ध किया जाता है। यही विशेषता इस रूटीन को अन्य शुरुआती स्तर के रूटीन से अलग करती है। Java सॉर्टिंग एल्गोरिदम, जो डेटा को कहीं अधिक बार स्थानांतरित करते हैं।
RSI tracनीचे दिया गया उदाहरण {860, 8, 200, 9} नामक सैंपल एरे को ठीक उसी तरह दिखाता है जैसे अगले सेक्शन में दिया गया प्रोग्राम रन टाइम पर प्रिंट करता है।
| पास | मुद्रित तुलनाएँ | सबसे छोटा मान पाया गया | स्वैप के बाद ऐरे |
|---|---|---|---|
| प्रारंभ | - | - | 860 8 200 9 |
| 1 | 860 और 8, 8 और 200, 8 और 9 | 8 | 8 860 200 9 |
| 2 | 860 और 200, 200 और 9 | 9 | 8 9 200 860 |
| 3 | 200 और 860 | 200 | 8 9 200 860 |
उसमें दो बातें हैं tracकुछ बिंदुओं पर ध्यान देना आवश्यक है। पहला, तीसरे चरण में क्रम में कोई परिवर्तन न होने के बावजूद भी अदला-बदली की सूचना मिलती है, क्योंकि शेष सबसे छोटा मान पहले से ही वर्तमान सूचकांक पर मौजूद है और प्रोग्राम तत्व को स्वयं से बदल देता है। दूसरा, प्रत्येक चरण में तुलनाओं की संख्या एक-एक करके घटती जाती है (तीन, फिर दो, फिर एक), जो पृष्ठ पर आगे दिए गए जटिलता आंकड़ों के पीछे का पैटर्न है।
Java चयन सॉर्ट को लागू करने के लिए कार्यक्रम
नीचे दी गई क्लास का नाम SelectionSortAlgo है और यह com.guru99 पैकेज में स्थित है। main() मेथड सैंपल ऐरे को डिक्लेयर करता है, उसे प्रिंट करता है, सॉर्टिंग के लिए selection() मेथड को सौंपता है और फिर से प्रिंट करता है। सहायक printArray() मेथड सभी एलिमेंट्स को एक ही लाइन में लिखता है, जिससे पठनीय पास-बाय-पास लॉग बनता है।
selection() फ़ंक्शन के अंदर, बाहरी लूप सॉर्ट किए गए और अनसॉर्ट किए गए क्षेत्रों के बीच की सीमा को चिह्नित करता है, वेरिएबल index अब तक देखे गए सबसे छोटे मान की स्थिति को रखता है, और प्रत्येक पास के अंत में तीन असाइनमेंट स्वैप करते हैं।
package com.guru99; public class SelectionSortAlgo { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("------Before Selection Sort-----"); printArray(myArray); selection(myArray);//sorting array using selection sort System.out.println("-----After Selection Sort-----"); printArray(myArray); } public static void selection(int[] array) { for (int i = 0; i < array.length - 1; i++) { System.out.println("Sort Pass Number "+(i+1)); int index = i; for (int j = i + 1; j < array.length; j++) { System.out.println("Comparing "+ array[index] + " and " + array[j]); if (array[j] < array[index]){ System.out.println(array[index] + " is greater than " + array[j] ); index = j; } } int smallerNumber = array[index]; array[index] = array[i]; array[i] = smallerNumber; System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
आउटपुट:
क्लास को कंपाइल और रन करने पर नीचे दिया गया कंसोल लॉग प्राप्त होता है, जिसमें प्रत्येक पास के लिए आउटपुट का एक ब्लॉक होता है।
------Before Selection Sort----- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Comparing 8 and 200 Comparing 8 and 9 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 860 and 200 860 is greater than 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 9 200 860 -----After Selection Sort----- 8 9 200 860
इस उदाहरण को पहली बार चलाने पर शुरुआती लोगों को दो समस्याओं का सामना करना पड़ता है। क्योंकि फ़ाइल घोषित करती है package com.guru99;स्रोत को एक मेल खाने वाले स्थान पर रहना चाहिए। com/guru99 यदि क्लास को डायरेक्ट्री में नहीं रखा जाता है, तो कंपाइलर पैकेज या क्लास-नाम बेमेल होने की रिपोर्ट करेगा। ऐसे में क्लास को उसके पूर्ण रूप से योग्य नाम से लॉन्च किया जाना चाहिए। java com.guru99.SelectionSortAlgoक्योंकि सादा java SelectionSortAlgo NoClassDefFoundError उत्पन्न करता है।
लूप की सीमाएँ एक और आम समस्या हैं। बाहरी लूप यहाँ रुक जाता है। array.length - 1 और आंतरिक लूप यहाँ से शुरू होता है i + 1किसी भी सीमा को बदलने से एक अतिरिक्त खाली पास उत्पन्न होता है या ArrayIndexOutOfBoundsException उत्पन्न होता है।
चयन क्रम की समय और स्थान जटिलता
प्रोग्राम का आंतरिक लूप हमेशा ऐरे के अंत तक चलता है, इसलिए एल्गोरिदम डेटा के स्वरूप के बावजूद समान संख्या में तुलनाएँ करता है। n तत्वों वाले ऐरे के लिए यह कुल संख्या n(n-1)/2 होती है, जो चार तत्वों वाले नमूने के लिए छह के बराबर होती है, और ऊपर दिया गया आउटपुट वास्तव में छह "तुलना" पंक्तियाँ प्रिंट करता है।
| मामला | तुलना | स्वैप | समय की जटिलता | सहायक स्थान |
|---|---|---|---|---|
| सर्वश्रेष्ठ (एरे पहले से ही क्रमबद्ध है) | एन(एन-1)/2 | N-1 | ओ (एन²) | ओ (1) |
| औसत (यादृच्छिक क्रम) | एन(एन-1)/2 | N-1 | ओ (एन²) | ओ (1) |
| सबसे खराब (उल्टे क्रम में) | एन(एन-1)/2 | N-1 | ओ (एन²) | ओ (1) |
उन समान आकृतियों की पंक्ति से तीन परिणाम निकलते हैं:
- सिलेक्शन सॉर्टिंग अनुकूलनशील नहीं है। सॉर्ट किए गए इनपुट की लागत ठीक उतनी ही होती है जितनी कि उल्टे इनपुट की, इसलिए इसमें जल्दी बाहर निकलने का कोई शॉर्टकट नहीं है। बबल शॅाट प्रदान करता है।
- स्वैप काउंट इस एल्गोरिदम की सबसे बड़ी खूबी है। इसमें अधिकतम n-1 एक्सचेंज होते हैं, जो कि अन्य सरल सॉर्ट्स द्वारा किए जाने वाले मूव्स की वर्ग संख्या से कहीं कम है।
- मेमोरी का उपयोग स्थिर है। केवल लूप काउंटर और दो अस्थायी चर index और smallerNumber की आवश्यकता होती है, इसलिए सहायक स्थान O(1) है और सॉर्टिंग उसी स्थान पर होती है।
व्यावहारिक सीमा द्विघात वृद्धि है। ऐरे के आकार को दोगुना करने से तुलना का कार्य लगभग चार गुना हो जाता है, इसलिए सिलेक्शन सॉर्ट शिक्षण, छोटे ऐरे और एम्बेडेड कोड के लिए उपयुक्त है, न कि उत्पादन डेटा सेट के लिए, जहाँ O(n log n) एल्गोरिदम सही विकल्प हैं।
चयन क्रम के लाभ और हानियाँ
यह समझना कि एल्गोरिदम कहाँ मदद करता है और कहाँ नुकसान पहुँचाता है, यह तय करना आसान बना देता है कि इसका उपयोग कब उचित है।
फायदे
- इसका तर्क संक्षिप्त और पठनीय है, यही कारण है कि यह एक मानक प्रारंभिक छँटाई अभ्यास है। सम्मिलन सॉर्ट.
- यह डेटा को उसी स्थान पर सॉर्ट करता है, इसलिए किसी दूसरे ऐरे को आवंटित नहीं किया जाता है और इनपुट के साथ मेमोरी का उपयोग नहीं बढ़ता है।
- यह ऐरे में अधिकतम n-1 बार ही लिखता है, जो ऐसे स्टोरेज पर मायने रखता है जहां लिखने की प्रक्रिया धीमी होती है या माध्यम को खराब कर देती है।
- इसका चलने का समय पूरी तरह से अनुमानित है, क्योंकि तुलनाओं की संख्या केवल ऐरे की लंबाई पर निर्भर करती है।
नुकसान
- प्रत्येक मामला O(n²) है, इसलिए एल्गोरिदम बड़े संग्रहों के लिए उपयुक्त नहीं है।
- यह पहले से सॉर्ट किए गए ऐरे का पता नहीं लगा सकता है और इसलिए कभी भी समय से पहले समाप्त नहीं होता है।
- ऊपर दिखाया गया क्लासिक रूप अस्थिर है, इसलिए दो बराबर मान विपरीत क्रम में आ सकते हैं।
- यह लगभग क्रमबद्ध डेटा पर इंसर्शन सॉर्ट की तुलना में अधिक बार तुलना करता है, जहां इंसर्शन सॉर्ट रैखिक समय के करीब पहुंचता है।
संक्षेप में, सिलेक्शन सॉर्ट का चुनाव तब करें जब ऐरे छोटा हो और प्रत्येक राइट प्रक्रिया महंगी हो, और जब डेटा सेट बड़ा हो या पहले से ही सॉर्टेड के करीब हो तो इससे बचें।
चयन क्रम बनाम Bubblई सॉर्ट बनाम इंसर्शन सॉर्ट
ये तीनों एल्गोरिदम द्विघात, इन-प्लेस तुलना सॉर्ट हैं, फिर भी इनपुट का आकार बदलने पर वे अलग तरह से व्यवहार करते हैं।
| कसौटी | चयन छांटना | Bubblई सॉर्ट | सम्मिलन सॉर्ट |
|---|---|---|---|
| सर्वोत्तम स्थिति समय | ओ (एन²) | पर) | पर) |
| औसत और सबसे खराब स्थिति का समय | ओ (एन²) | ओ (एन²) | ओ (एन²) |
| सबसे खराब स्थिति में अदला-बदली या बदलाव। | एन-1 स्वैप | n(n-1)/2 स्वैप | n(n-1)/2 शिफ्ट तक |
| स्थिर | नहीं | हाँ | हाँ |
| क्रमबद्ध इनपुट के अनुकूल | नहीं | हाँ | हाँ |
| सहायक स्थान | ओ (1) | ओ (1) | ओ (1) |
| विशिष्ट उपयोग | सबसे कम लेखन की आवश्यकता | क्रमबद्ध डेटा को सिखाना और पहचानना | छोटे या लगभग क्रमबद्ध सरणियाँ |
यह तालिका साक्षात्कार में पूछे जाने वाले एक आम प्रश्न का उत्तर देती है। सिलेक्शन सॉर्ट डेटा के आदान-प्रदान की संख्या के मामले में बेहतर है, बबल सॉर्ट पहले से क्रमबद्ध इनपुट को पहचानने में बेहतर है, और इंसर्शन सॉर्ट आमतौर पर व्यवहार में तीनों में सबसे तेज़ है क्योंकि वास्तविक डेटा अक्सर आंशिक रूप से क्रमबद्ध होता है। कुछ दर्जन तत्वों से अधिक होने पर इनमें से कोई भी मर्ज सॉर्ट या क्विकसॉर्ट से प्रतिस्पर्धा नहीं कर सकता।
