सी ++ में रिकर्सिव चयन क्रमबद्ध करें

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

चयन सॉर्ट एल्गोरिथम

• int arr[5]={ 5,4,2,1,3 };

• इंट आई, जे;

• अनुक्रमणिका i=0 से i<सरणी आकार -1

  . तक ट्रैवर्स

  • अनुक्रमणिका j=i+1 से सरणी आकार - 1

    . तक ट्रैवर्स

  • सबसे छोटा ढूंढें और उसके index.pos को संगृहीत करें

• एरर[i]

  . के साथ पाए गए इंडेक्स पॉज़ पर तत्व स्वैप करें

• अंत

पुनरावर्ती चयन सॉर्ट

• न्यूनतम तत्व की अनुक्रमणिका खोजें

• यदि पाया गया सबसे छोटा तत्व सूचकांक सरणी आकार के बराबर है, तो वापस लौटें।

• अन्यथा वर्तमान तत्व को सबसे छोटे तत्व से बदलें

• क्रमबद्ध तत्वों को छोड़कर शेष सरणी के लिए उपरोक्त चरणों को पुनरावर्ती रूप से निष्पादित करें

उदाहरण

इनपुट - एआर [] ={ 5,7,2,3,1,4}; लंबाई=6

आउटपुट - क्रमबद्ध सरणी:1 2 3 4 5 7

स्पष्टीकरण -

First Pass :-
5 7 2 3 1 4 → swap → 1 2 7 3 5 4
1 2 7 3 5 4 → no swap
1 2 7 3 5 4 → swap → 1 2 3 7 5 4
1 2 3 7 5 4 → swap → 1 2 3 4 5 7
1 2 3 4 5 7 → no swap

इनपुट − Arr[] ={ 1, 2, 3, 3, 2 };

आउटपुट - क्रमबद्ध सरणी:1 2 2 3 3

स्पष्टीकरण -

1 2 3 3 2 → no swap
1 2 3 2 3 → no swap
1 2 3 2 3 → swap → 1 2 2 3 3
1 2 2 3 3 → no swap

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

चयन प्रकार के पुनरावर्ती दृष्टिकोण में, आधार मामला न्यूनतम सूचकांक =सरणी आकार -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 की तलाश करें।

• if(arr[i]

• फ़ंक्शन recurselectSort(int arr1[], int len1, int pos1) इनपुट सरणी लेता है और चयन क्रम में रिकर्सन का उपयोग करके इसे आरोही क्रम में क्रमबद्ध करता है।

• अगर pos1 ==len1 तो कोई न्यूनतम नहीं मिला, तो वापस आएं।

• अन्य सेट minpos1 =findMin(arr1, pos1, len1-1)

• यदि वर्तमान pos1 अनुक्रमणिका और न्यूनतम तत्व अनुक्रमणिका minpos1 समान नहीं हैं, तो इन अनुक्रमणिका में अस्थायी का उपयोग करके तत्वों को स्वैप करें।

• recurselectSort(arr1, len1, pos1 + 1) का उपयोग करके शेष सरणी के लिए रिकर्स करें।

• सभी कॉलों के अंत में, जब लेन 1 हो जाती है तो हम रिकर्सन से बाहर आ जाएंगे और सरणी को सॉर्ट किया जाएगा।

• मुख्य के अंदर क्रमबद्ध सरणी को प्रिंट करें।

उदाहरण

#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