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

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

यह एल्गोरिदम एलिमेंट को सॉर्टेड सब-एरे में उसकी सही स्थिति पर रखकर काम करता है, यानी एलिमेंट से पहले का सब-एरे जो पहले से सॉर्टेड होता है।

एल्गोरिदम

चरण 1 - 1 से n-1 तक लूप चलाएं और निम्न करें -

चरण 2.1 - पोजीशन i पर स्थित एलिमेंट array[i] को चुनें।

चरण 2.2 - इस एलिमेंट को सॉर्टेड सब-एरे array[0] से arr[i] में उसकी सही स्थिति पर इन्सर्ट करें।

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

एरे = [34, 7, 12, 90, 51]

i = 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]

i = 4 के लिए, arr[4] = 51, इसे सबएरे arr[0] - arr[4] में इसकी स्थिति पर रखते हैं।

[7, 12, 34, 51, 90]

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

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

उदाहरण

#include 
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