यह सॉर्टिंग तकनीक कार्ड सॉर्टिंग तकनीक के समान है, दूसरे शब्दों में हम इंसर्शन सॉर्ट तंत्र का उपयोग करके कार्ड सॉर्ट करते हैं। इस तकनीक के लिए, हम डेटा सेट से एक तत्व चुनते हैं और चुने गए तत्व को डेटा सेट में वापस डालने के लिए जगह बनाने के लिए डेटा तत्वों को शिफ्ट करते हैं।
इंसर्शन सॉर्ट तकनीक की जटिलता
समय जटिलता: सर्वोत्तम मामले के लिए O(n), औसत और सबसे खराब स्थिति के लिए O(n2)
स्पेस जटिलता: O(1)
इनपुट − असॉर्टेड सूची: 9 45 23 71 80 55 आउटपुट − सॉर्टिंग के बाद सरणी: 9 23 45 55 71 80
एल्गोरिदम
insertionSort(array, size)
इनपुट: डेटा की एक सरणी, और सरणी में कुल संख्या
आउटपुट: क्रमबद्ध सरणी
शुरुआत i := 1 से size-1 तक करें key := array[i] j := i जब तक j > 0 AND array[j-1] > key करें array[j] := array[j-1]; j := j – 1 हो गया array[j] := key हो गया अंत
उदाहरण कोड
#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
