सम्मिलन क्रम (Insertion Sort) डेटा को क्रमबद्ध करने के लिए उपयोग किए जाने वाले क्रमबद्ध एल्गोरिदम में से एक है जो तत्वों को ताश के पत्तों की तरह सम्मिलित करके क्रमबद्ध करता है। सभी तत्वों को बाएं से दाएं व्यवस्थित किया जाता है फिर पहले को पहले से क्रमबद्ध मानकर, बाकी को बाईं ओर क्रमबद्ध सूची में सम्मिलित करते हैं। प्रत्येक तत्व की तुलना बाईं सूची में प्रत्येक तत्व से तब तक की जाती है जब तक यह अपनी सही स्थिति पर सम्मिलित नहीं हो जाता।
सम्मिलन क्रम एल्गोरिदम
int arr[5]= { 5,4,2,1,3 };
int i, j ;
इंडेक्स j=i+1 से j<सरणी आकार तक ट्रैवर्स करें
प्रत्येक तत्व arr[j] के लिए इसकी तुलना सूची arr[0 से i] में तत्वों से तब तक करें जब तक ऐसा तत्व नहीं मिल जाता कि arr[i]
arr[j] को सूची में रखें और सभी बड़े तत्वों को एक स्थान दाएं ले जाएं।
समाप्त
पुनरावर्ती सम्मिलन क्रम
यदि सरणी लंबाई 1 है तो वापस लौटें।
इंडेक्स 0 से सरणी आकार-1 तक तत्वों को पुनरावर्ती रूप से क्रमबद्ध करें
अंतिम तत्व को क्रमबद्ध सरणी में सम्मिलित करें
उदाहरण
इनपुट - Arr[] = { 5,7,2,3,1,4 }; लंबाई=6
आउटपुट - क्रमबद्ध सरणी: 1 2 3 4 5 7
व्याख्या -
5 7 2 3 1 4 → 5 पहले से क्रमबद्ध 5 7 2 3 1 4 → 7 सही जगह पर 2 5 7 3 1 4 → 2 की तुलना 5,7 से और सम्मिलित 2 3 5 7 1 4 → 3 की तुलना 5,7 से और सम्मिलित 1 2 3 5 7 4 → 1 की तुलना 2,3,5,7 से और सम्मिलित 1 2 3 4 5 7 → 4 की तुलना 5,7 से और सम्मिलित
इनपुट - Arr[] = { 1, 2, 3, 3, 2 };
आउटपुट - क्रमबद्ध सरणी: 1 2 2 3 3
व्याख्या -
1, 2, 3, 3, 2 → 1 पहले से क्रमबद्ध 1, 2, 3, 3, 2 → 2 सही जगह पर 1, 2, 3, 3, 2 → 3 सही जगह पर 1, 2, 3, 3, 2 → 3 सही जगह पर 1, 2, 2, 3, 3 → 2 की तुलना 3,3 से और सम्मिलित
उपयोग किया गया दृष्टिकोण
बबल क्रम के पुनरावर्ती दृष्टिकोण में, आधार मामला सरणी लंबाई = 1 है। अन्यथा सिंगल for लूप का उपयोग करके सरणी को ट्रैवर्स करें और तदनुसार तत्वों को स्वैप करें।
इनपुट सरणी Arr[] और लंबाई के रूप में इसमें तत्वों की संख्या लें।
फ़ंक्शन recurbublSort(int arr[], int len) सरणी और इसकी लंबाई लेता है और बबल क्रम का उपयोग करके सरणी को पुनरावर्ती रूप से क्रमबद्ध करता है।
temp वेरिएबल लें।
यदि सरणी लंबाई 1 है तो void लौटाएं।
अन्यथा सिंगल for लूप का उपयोग करके सरणी को ट्रैवर्स करें और प्रत्येक तत्व arr[i]>arr[i+1] के लिए उन तत्वों को स्वैप करें।
temp=arr[i], arr[i]=arr[i+1] और arr[i+1]=temp सेट करें।
अब पिछले लूप ने सबसे बड़े तत्व को अंतिम स्थान पर रखा इसलिए लंबाई को 1 से घटाएं।
recurbublSort(arr,len) को पुनरावर्ती कॉल करें।
सभी कॉल के अंत में, जब len 1 हो जाता है तो हम पुनरावर्तन से बाहर आ जाएंगे और सरणी क्रमबद्ध हो जाएगी।
main के अंदर क्रमबद्ध सरणी प्रिंट करें।
उदाहरण
#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
