चयन क्रम (Selection Sort) डेटा को क्रमबद्ध करने के लिए उपयोग किए जाने वाले क्रमबद्ध एल्गोरिदम में से एक है जो सरणी की शुरुआत से पुनरावृति करता है और प्रत्येक तत्व को सूची में सबसे छोटे तत्व से बदलता है। जैसे-जैसे हम आगे बढ़ते हैं, बाईं सरणी क्रमबद्ध होती है, और दाईं सरणी अक्रमबद्ध रहती है। प्रत्येक चाल अगले सबसे छोटे को इंडेक्स की वर्तमान स्थिति पर स्वैप करके रखती है।
चयन क्रम एल्गोरिदम
int arr[5]= { 5,4,2,1,3 };
int i, j ;
इंडेक्स i=0 से i<सरणी आकार -1 तक ट्रैवर्स करें
इंडेक्स j=i+1 से सरणी आकार - 1 तक ट्रैवर्स करें
सबसे छोटा ढूंढें और उसका इंडेक्स संग्रहीत करें।pos
पाए गए इंडेक्स pos पर तत्व को arr[i] से स्वैप करें
समाप्त
पुनरावर्ती चयन क्रम
न्यूनतम तत्व का इंडेक्स ढूंढें
यदि पाया गया सबसे छोटा तत्व इंडेक्स सरणी आकार के बराबर है, तो वापस लौटें।
अन्यथा वर्तमान तत्व को सबसे छोटे तत्व से स्वैप करें
क्रमबद्ध तत्वों को छोड़कर शेष सरणी के लिए उपरोक्त चरणों को पुनरावर्ती रूप से करें
उदाहरण
इनपुट - Arr[] = { 5,7,2,3,1,4 }; लंबाई=6
आउटपुट - क्रमबद्ध सरणी: 1 2 3 4 5 7
व्याख्या-
पहला पास :- 5 7 2 3 1 4 → स्वैप → 1 2 7 3 5 4 1 2 7 3 5 4 → कोई स्वैप नहीं 1 2 7 3 5 4 → स्वैप → 1 2 3 7 5 4 1 2 3 7 5 4 → स्वैप → 1 2 3 4 5 7 1 2 3 4 5 7 → कोई स्वैप नहीं
इनपुट - Arr[] = { 1, 2, 3, 3, 2 };
आउटपुट - क्रमबद्ध सरणी: 1 2 2 3 3
व्याख्या -
1 2 3 3 2 → कोई स्वैप नहीं 1 2 3 2 3 → कोई स्वैप नहीं 1 2 3 2 3 → स्वैप → 1 2 2 3 3 1 2 2 3 3 → कोई स्वैप नहीं
उपयोग किया गया दृष्टिकोण
चयन क्रम के पुनरावर्ती दृष्टिकोण में, आधार मामला न्यूनतम इंडेक्स = सरणी आकार-1 है। अन्यथा सरणी से न्यूनतम ढूंढें, वर्तमान इंडेक्स से स्वैप करें और दाईं अक्रमबद्ध सरणी को पुनरावर्ती रूप से क्रमबद्ध करें।
इनपुट सरणी Arr[] और लंबाई के रूप में इसमें तत्वों की संख्या लें।
फ़ंक्शन findMin(int arr[], int i, int j) सरणी और उसके इंडेक्स लेता है और arr[i+1] से arr[j] के बीच न्यूनतम तत्व का इंडेक्स लौटाता है।
minpos वेरिएबल लें।
यदि i और j दोनों समान हैं, तो न्यूनतम तत्व के इंडेक्स के रूप में i लौटाएं क्योंकि दोनों समान हैं।
अन्यथा minpos = findMin(arr, i + 1, j) का उपयोग करके इंडेक्स i+1 से j तक पुनरावर्ती रूप से देखें।
यदि (arr[i] < arr[minpos]) तो { minpos=i; } सेट करें और minpos लौटाएं।
फ़ंक्शन recurselectSort(int arr1[], int len1, int pos1) इनपुट सरणी लेता है और चयन क्रम में पुनरावर्तन का उपयोग करके इसे आरोही क्रम में क्रमबद्ध करता है।
यदि pos1 == len1 तो कोई न्यूनतम नहीं मिला, तो वापस लौटें।
अन्यथा minpos1 = findMin(arr1, pos1, len1-1) सेट करें
यदि वर्तमान pos1 इंडेक्स और न्यूनतम तत्व इंडेक्स minpos1 समान नहीं हैं, तो temp का उपयोग करके इन इंडेक्स पर तत्वों को स्वैप करें।
recurselectSort(arr1, len1, pos1 + 1) का उपयोग करके शेष सरणी के लिए पुनरावर्ती करें।
सभी कॉल के अंत में, जब len 1 हो जाता है तो हम पुनरावर्तन से बाहर आ जाएंगे और सरणी क्रमबद्ध हो जाएगी।
main के अंदर क्रमबद्ध सरणी प्रिंट करें।
उदाहरण
#include <iostream> using namespace std; int findMin(int arr[], int i, int j){ int minpos; if (i == j){ return i; } minpos = findMin(arr, i + 1, j); if(arr[i]<arr[minpos]){ minpos=i; } return (minpos); } void recurselectSort(int arr1[], int len1, int pos1){ int temp; int minpos1; if (pos1 == len1){ return; } minpos1 = findMin(arr1, pos1, len1-1); if (minpos1 != pos1){ temp=arr1[pos1]; arr1[pos1]=arr1[minpos1]; arr1[minpos1]=temp; } recurselectSort(arr1, len1, pos1 + 1); } int main(){ int Arr[] = {1,5,3,0,9,3,5}; int length = sizeof(Arr)/sizeof(Arr[0]); recurselectSort(Arr,length,0); cout<<"Sorted Array using recursive Selection sort: "<<endl; for (int i = 0; i<length ; i++){ cout << Arr[i] << " "; } return 0; } आउटपुट
उपरोक्त कोड चलाने पर निम्नलिखित आउटपुट उत्पन्न होगा:
Sorted Array using recursive Selection sort: 0 1 3 3 5 5 9