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

इंसर्शन सॉर्ट एक सॉर्टिंग एल्गोरिथम है जो एक इन-प्लेस तुलना-आधारित एल्गोरिदम है।

एल्गोरिथम स्थान तत्व द्वारा क्रमबद्ध उप-सरणी में उनकी स्थिति में काम करता है यानी उप-सरणी उस तत्व से पहले जो एक क्रमबद्ध उप-सरणी है।

एल्गोरिदम

Step1 - 1 से n-1 तक लूप करें और करें -

चरण 2.1 - स्थिति i, सरणी [i] पर तत्व का चयन करें।

चरण 2.2 - सॉर्ट किए गए उप-सरणी सरणी में तत्व को उसकी स्थिति में डालें [0] को गिरफ्तार करने के लिए [i]।

एल्गोरिदम को समझने के लिए एक उदाहरण लेते हैं

सरणी =[34, 7, 12, 90, 51]

मेरे लिए =1, arr[1] =7, सबअरे arr[0] - arr[1] में अपनी स्थिति में रखकर।

[7, 34, 12, 90, 51]

i =2 के लिए , arr[2] =12, सबअरे arr[0] - arr[2] में अपनी स्थिति में रखते हुए।

[7, 12, 34, 90, 51]

i =3 के लिए , arr[3] =90, इसके पॉज़िटोन को सबअरे arr[0] - arr[3] में रखकर।

[7, 12, 34, 90, 51]

मेरे लिए =4, एआर [4] =51, इसके पॉज़िटोन में सबरे एआर [0] - एआर [4] में रखकर।

[7, 12, 34, 54, 90]

यहां, हम देखेंगे कि रिकर्सिव इंसर्शन सॉर्ट कैसे काम करता है। यह रिवर्स आधार पर काम करता है यानी हम वर्तमान पुनरावृत्ति की तुलना में n-1 तत्व सरणी को सॉर्ट करने के लिए पुनरावर्ती रूप से पुनरावर्ती सम्मिलन () फ़ंक्शन को कॉल करेंगे। और फिर इस क्रमबद्ध सरणी में जो फ़ंक्शन द्वारा लौटाया जाएगा, हम nth तत्व को उसकी स्थिति में सॉर्ट किए गए सरणी के रूप में सम्मिलित करेंगे।

पुनरावर्ती प्रविष्टि क्रम के लिए कार्यक्रम -

उदाहरण

#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
   if (n <= 1)
      return;
   recursiveInsertionSort( arr, n-1 );
   int nth = arr[n-1];
   int j = n-2;
   while (j >= 0 && arr[j] > nth){
      arr[j+1] = arr[j];
      j--;
   }
   arr[j+1] = nth;
}
int main(){
   int array[] = {34, 7, 12, 90, 51};
   int n = sizeof(array)/sizeof(array[0]);
   printf("Unsorted Array:\t");
      for (int i=0; i < n; i++)
   printf("%d ",array[i]);
      recursiveInsertionSort(array, n);
   printf("\nSorted Array:\t");
   for (int i=0; i < n; i++)
      printf("%d ",array[i]);
   return 0;
}

आउटपुट

Unsorted Array: 34 7 12 90 51
Sorted Array: 7 12 34 51 90