सी ++ प्रोग्राम रिकर्सिव इंसर्शन सॉर्ट

इंसर्शन सॉर्ट कार्ड के डेक जैसे तत्वों को सम्मिलित करके डेटा को सॉर्ट करने के लिए उपयोग किए जाने वाले सॉर्टिंग एल्गोरिदम में से एक है। सभी तत्वों को बाएं से दाएं व्यवस्थित किया जाता है, फिर पहले को पहले से सॉर्ट किया गया मानते हुए, बाईं ओर सॉर्ट की गई सूची में आराम डालें। प्रत्येक तत्व की तुलना बाईं सूची में प्रत्येक तत्व के साथ तब तक की जाती है जब तक कि उसे उसकी सही स्थिति में न डाला जाए।

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

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

• इंट आई, जे;

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

  . तक ट्रैवर्स

• प्रत्येक तत्व के लिए arr[j] इसकी तुलना arr[0 to i] सूची के तत्वों से करें जब तक कि तत्व ऐसा न मिल जाए कि arr[i]=arr[j]।

• गिरफ्तारी [j] को सूची में रखें और सभी बड़े तत्वों को एक स्थान पर दाईं ओर ले जाएं।

• अंत

पुनरावर्ती इंसर्शन सॉर्ट

• अगर सरणी की लंबाई 1 है तो वापस आएं।

• अनुक्रमणिका 0 से सरणी आकार-1 तक के तत्वों को पुनरावर्ती रूप से क्रमबद्ध करें

• क्रमबद्ध सरणी में अंतिम तत्व डालें

उदाहरण

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

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

स्पष्टीकरण -

5 7 2 3 1 4 → 5 already sorted
5 7 2 3 1 4 → 7 at correct place
2 5 7 3 1 4 → 2 compared with 5,7 and inserted
2 3 5 7 1 4 → 3 compared with 5,7 and inserted
1 2 3 5 7 4 → 1 compared with 2,3,5,7 and inserted
1 2 3 4 5 7 → 4 compared with 5,7 and inserted

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

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

स्पष्टीकरण -

1, 2, 3, 3, 2 → 1 already sorted
1, 2, 3, 3, 2 → 2 at correct place
1, 2, 3, 3, 2 → 3 at correct place
1, 2, 3, 3, 2 → 3 at correct place
1, 2, 2, 3, 3 → 2 compared with 3,3 and inserted

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

बबल प्रकार के पुनरावर्ती दृष्टिकोण में, आधार मामला सरणी लंबाई =1 है। अन्यथा लूप के लिए एकल का उपयोग करके सरणी को पार करें और तदनुसार तत्वों को स्वैप करें।

• इनपुट ऐरे Arr[] और लंबाई को उसमें तत्वों की संख्या के रूप में लें।

• फ़ंक्शन recurbublSort(int arr[], int len) सरणी और उसकी लंबाई लेता है और बबल सॉर्ट का उपयोग करके सरणी को पुनरावर्ती रूप से सॉर्ट करता है।

• एक परिवर्तनशील अस्थायी लें।

• यदि सरणी की लंबाई 1 है तो शून्य लौटें।

• अन्यथा लूप के लिए सिंगल का उपयोग करके सरणी को पार करें और प्रत्येक तत्व arr[i]>arr[i+1] के लिए, उन तत्वों को स्वैप करें।

• अस्थायी सेट करें [i], गिरफ्तार [i] =गिरफ्तारी [i + 1] और गिरफ्तारी [i + 1] =अस्थायी।

• अब लंबाई में 1 की कमी करें क्योंकि पिछले लूप ने सबसे बड़े तत्व को अंतिम स्थान पर रखा है।

• recurbublSort(arr,len) पर पुनरावर्ती कॉल करें।

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

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void recurbublSort(int arr[], int len){
   int temp;

   if (len == 1){
      return;
   }
   for (int i=0; i<len-1; i++){
      if (arr[i] > arr[i+1]){
         temp=arr[i];
         arr[i]=arr[i+1];
         arr[i+1]=temp;
      }
   }
   len=len-1;
   recurbublSort(arr, len);
}
int main(){
   int Arr[] = {21, 34, 20, 31, 78, 43, 66};
   int length = sizeof(Arr)/sizeof(Arr[0]);

   recurbublSort(Arr, length);

   cout<<"Sorted array : ";
   for(int i=0;i<length;i++){
      cout<<Arr[i]<<" ";
   }

   return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा

Sorted array : 20 21 31 34 43 66 78