मेन्यू

चयन सी में सी + + उदाहरण के साथ

selection sort c with examples

समस्याओं को खत्म करने के लिए हमारे साधन का प्रयास करें

उदाहरणों में C ++ में चयन में एक गहराई देखें।

जैसा कि नाम से ही पता चलता है, चयन सॉर्ट तकनीक सबसे पहले सरणी में सबसे छोटे तत्व का चयन करती है और इसे सरणी में पहले तत्व के साथ स्वैप करती है।

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

=> यहां परफेक्ट सी ++ ट्रेनिंग गाइड देखें।

चयन छांटना

आप क्या सीखेंगे:

परिचय

चयन सॉर्ट काफी सरल छँटाई तकनीक है क्योंकि तकनीक में हर पास में सबसे छोटा तत्व ढूंढना और उसे सही स्थिति में रखना शामिल है।

जब सॉर्ट की जाने वाली सूची छोटे आकार की होती है, तो चयन सॉर्ट कुशलता से काम करता है, लेकिन सूची को आकार में बढ़ने के लिए इसका प्रदर्शन बुरी तरह प्रभावित होता है।

इसलिए हम कह सकते हैं कि डेटा की बड़ी सूची के लिए चयन प्रकार उचित नहीं है।

सामान्य एल्गोरिथम

चयन प्रकार के लिए सामान्य एल्गोरिदम नीचे दिया गया है:

मैं कंपनियों के लिए उत्पादों का परीक्षण करना चाहता हूं

चयन सॉर्ट (ए, एन)

चरण 1 : K = 1 से N-1 के लिए चरण 2 और 3 दोहराएं
चरण 2 : कॉल रूटीन सबसे छोटा (A, K, N, POS)
चरण 3 : A (POS) के साथ स्वैप A (K)
(पाश का अंत)
चरण 4 : बाहर जाएं

दिनचर्या सबसे छोटी (A, K, N, POS)

  • चरण 1 : (इनिशियलाइज़ करें) सेट करें smallestElem = A (K)
  • चरण 2 : (आरंभ करें) POS = K सेट करें
  • चरण 3 : J = K + 1 से N -1 के लिए, दोहराएं
    अगर छोटी से छोटी> ए (जे)
    छोटा सेट करें = ए (जे)
    सेट पीओएस = जे
    (यदि समाप्त हुआ)
    (पाश का अंत)
  • चरण 4 : पीओएस लौटाएं

स्यूडोकोड चयन के लिए क्रमबद्ध करें

Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j)

इस चयन सॉर्ट एल्गोरिथ्म का वर्णन करने के लिए एक उदाहरण नीचे दिखाया गया है।

चित्रण

चयन क्रमबद्ध चित्रण

पास २

पास ३

पास ४

इस चित्रण के लिए सारणीबद्ध प्रतिनिधित्व नीचे दिखाया गया है:

अनारक्षित सूचीकम से कम तत्वक्रमबद्ध सूची
{18,10,7,20,2}दो{}
{18,10,7,20}।{दो}
{18,10,20}१०{2.7}
{18.20}१।{2,7,10)
{बीस}बीस{2,7,10,18}
{}{2,7,10,18,20}

दृष्टांत से, हम देखते हैं कि हर पास के साथ अगले सबसे छोटे तत्व को सॉर्ट किए गए सरणी में अपनी सही स्थिति में रखा जाता है। उपरोक्त उदाहरण से, हम देखते हैं कि 5 तत्वों की एक सरणी को क्रमबद्ध करने के लिए, चार पास की आवश्यकता थी। इसका मतलब सामान्य रूप से, एन तत्वों की एक सरणी को सॉर्ट करने के लिए, हमें एन -1 पास की कुल आवश्यकता है।

नीचे दिए गए C ++ में चयन सॉर्ट एल्गोरिथ्म का कार्यान्वयन है।

C ++ उदाहरण

#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<' Input list of elements to be Sorted '; for(int i=0;i<10;i++) { cout<

आउटपुट:

छांटे जाने वाले तत्वों की इनपुट सूची

11 5 2 20 42 53 23 34 101 22

तत्वों की क्रमबद्ध सूची है

2 5 11 20 22 23 34 42 53 101

सरणी को सॉर्ट करने के लिए आवश्यक पासों की संख्या: 10

जैसा कि उपरोक्त कार्यक्रम में दिखाया गया है, हम सरणी में अन्य सभी तत्वों के साथ सरणी में पहले तत्व की तुलना करके चयन प्रकार शुरू करते हैं। इस तुलना के अंत में, सरणी में सबसे छोटा तत्व पहले स्थान पर रखा गया है।

अगले पास में, उसी दृष्टिकोण का उपयोग करके, सरणी में अगला सबसे छोटा तत्व अपनी सही स्थिति में रखा गया है। यह एन तत्वों तक या पूरे सरणी को छाँटने तक जारी रहता है।

जावा उदाहरण

अगला, हम जावा भाषा में चयन सॉर्ट तकनीक को लागू करते हैं।

class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println(' Input list to be sorted... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println(' printing sorted elements... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j)

आउटपुट:

इनपुट सूची को क्रमबद्ध किया जाना है ...

11 5 2 20 42 53 23 34 101 22

छँटाई तत्वों की छपाई ...

2 5 11 20 22 23 34 42 53 101

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

इस प्रकार चयन प्रकार को लागू करने के लिए सबसे सरल एल्गोरिथ्म है, जैसा कि हमें बस सरणी में अगले सबसे छोटे तत्व को बार-बार ढूंढना है और इसे अपने उचित स्थान पर तत्व के साथ स्वैप करना है।

चयन क्रमबद्धता की जटिलता विश्लेषण

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

इसलिए, इनपुट सरणी के आकार N को देखते हुए, चयन सॉर्ट एल्गोरिथ्म में निम्नलिखित समय और जटिलता मूल्य होते हैं।

सबसे खराब स्थिति समय जटिलताओ (एन 2); ओ (n) स्वैप
सबसे अच्छा मामला समय जटिलताओ (एन 2); ओ (n) स्वैप
औसत समय जटिलताओ (एन 2); ओ (n) स्वैप
अंतरिक्ष की जटिलताओ (1)

O की समय जटिलता ( एन दो) मुख्यतः दो छोरों के उपयोग के कारण है। ध्यान दें कि चयन प्रकार तकनीक कभी भी O (n) स्वैप से अधिक नहीं लेती है और यह फायदेमंद होता है जब मेमोरी राइट ऑपरेशन महंगा साबित होता है।

निष्कर्ष

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

इसका मतलब है कि हम कुशलता से डेटा संरचनाओं को सॉर्ट कर सकते हैं जैसे चयन प्रकार का उपयोग करके एरे।

इस ट्यूटोरियल में, हमने चयन प्रकारों पर विस्तार से चर्चा की है, जिसमें C ++ और Java भाषाओं का उपयोग करके चयन प्रकार लागू करना शामिल है। चयन प्रकार के पीछे तर्क है कि सूची में सबसे छोटे तत्व को बार-बार खोजना और उसे उचित स्थिति में रखना।

अगले ट्यूटोरियल में, हम प्रविष्टि सॉर्ट के बारे में विस्तार से जानेंगे, जिसे अन्य दो तकनीकों की तुलना में अधिक कुशल तकनीक कहा जाता है, जिनके बारे में हमने अब तक चर्चा की है यानी बबल सॉर्ट और चयन सॉर्ट।

=> C ++ प्रशिक्षण ट्यूटोरियल के ए-जेड को देखने के लिए यहां देखें।

अनुशंसित पाठ

^