DAA - चयन सॉर्ट

इस प्रकार की छंटाई को कहा जाता है Selection Sortचूंकि यह बार-बार तत्वों को छांटकर काम करता है। यह निम्नानुसार काम करता है: पहले सरणी में सबसे छोटा पाते हैं और पहली स्थिति में तत्व के साथ इसका आदान-प्रदान करते हैं, फिर दूसरे सबसे छोटे तत्व का पता लगाते हैं और दूसरी स्थिति में तत्व के साथ इसका आदान-प्रदान करते हैं, और इस तरह से तब तक जारी रखते हैं जब तक कि पूरी सरणी न हो जाए सॉर्ट किया गया।

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

चयन सॉर्टिंग सॉर्टिंग तकनीकों में सबसे सरल है और यह छोटी फ़ाइलों के लिए बहुत अच्छी तरह से काम करता है। इसका एक बहुत महत्वपूर्ण अनुप्रयोग है क्योंकि प्रत्येक आइटम वास्तव में सबसे अधिक बार ले जाया जाता है।

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

फिर भी, चयन सॉर्ट एल्गोरिथ्म के लिए आवश्यक समय, सॉर्ट किए जाने वाले सरणी के मूल क्रम के लिए बहुत संवेदनशील नहीं है: परीक्षा यदि A[j] < min x हर मामले में ठीक उसी समय निष्पादित किया जाता है।

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

बबल सॉर्ट प्रत्येक चरण में अधिकतम शेष तत्वों का चयन करता है, लेकिन कुछ ऑर्डर को सरणी के अनसोल्ड हिस्से को प्रदान करने वाले कुछ प्रयासों को बर्बाद कर देता है।
चयन प्रकार सबसे खराब और औसत दोनों मामलों में द्विघात है, और अतिरिक्त मेमोरी की आवश्यकता नहीं है।

प्रत्येक के लिए i से 1 सेवा n - 1, एक विनिमय और है n - i तुलना, तो कुल की है n - 1 एक्सचेंज और

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 तुलना।

ये अवलोकन, कोई भी बात नहीं है कि इनपुट डेटा क्या है।

सबसे खराब स्थिति में, यह द्विघात हो सकता है, लेकिन औसत मामले में, यह मात्रा है O(n log n)। इसका तात्पर्य है किrunning time of Selection sort is quite insensitive to the input।

कार्यान्वयन

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}