इंसर्शन सॉर्ट

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

इंसर्शन सॉर्ट तकनीक की जटिलता

• टाइम कॉम्प्लेक्सिटी: बेस्ट केस के लिए O(n), औसत और सबसे खराब केस के लिए O(n^2)
• स्पेस कॉम्प्लेक्सिटी: O(1)

इनपुट और आउटपुट

इनपुट: अनसॉर्टेड लिस्ट: 9 45 23 71 80 55
आउटपुट: सॉर्टिंग से पहले ऐरे: 9 45 23 71 80 55
सॉर्टिंग के बाद ऐरे: 9 23 45 55 71 80

एल्गोरिदम

insertionSort(array, size)

इनपुट: डेटा का एक ऐरे, और ऐरे में कुल संख्या
आउटपुट: सॉर्टेड ऐरे

Begin
    for i := 1 to size - 1 do
        key := array[i]
        j := i
        while j > 0 AND array[j-1] > key do
            array[j] := array[j-1]
            j := j - 1
        done
        array[j] := key
    done
End

उदाहरण

#include <iostream>
using namespace std;

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void insertionSort(int *array, int size) {
    int key, j;
    for(int i = 1; i < size; i++) {
        key = array[i]; // मान लें
        j = i;
        while(j > 0 && array[j-1] > key) {
            array[j] = array[j-1];
            j--;
        }
        array[j] = key; // सही जगह पर इन्सर्ट करें
    }
}

int main() {
    int n;
    cout << "एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    int arr[n]; // दिए गए एलिमेंट्स की संख्या के साथ ऐरे बनाएं
    cout << "एलिमेंट्स दर्ज करें:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "सॉर्टिंग से पहले ऐरे: ";
    display(arr, n);
    insertionSort(arr, n);
    cout << "सॉर्टिंग के बाद ऐरे: ";
    display(arr, n);
}

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 6
एलिमेंट्स दर्ज करें: 9 45 23 71 80 55
सॉर्टिंग से पहले ऐरे: 9 45 23 71 80 55
सॉर्टिंग के बाद ऐरे: 9 23 45 55 71 80