शेल सॉर्टिंग तकनीक इंसर्शन सॉर्ट पर आधारित है। इंसर्शन सॉर्ट में कभी-कभी सही स्थान पर आइटम डालने के लिए बड़े ब्लॉक को शिफ्ट करने की आवश्यकता होती है। शेल सॉर्ट का उपयोग करके, हम बड़ी संख्या में शिफ्टिंग से बच सकते हैं। सॉर्टिंग विशिष्ट अंतराल के साथ की जाती है। प्रत्येक पास के बाद अंतराल को छोटे अंतराल बनाने के लिए कम किया जाता है।
शेल सॉर्ट तकनीक की जटिलता
समय जटिलता: सर्वोत्तम मामले के लिए O(n log n), और अन्य मामलों के लिए, यह गैप अनुक्रम पर निर्भर करता है।
स्पेस जटिलता: O(1)
इनपुट − असॉर्टेड सूची: 23 56 97 21 35 689 854 12 47 66 आउटपुट − सॉर्टिंग के बाद सरणी: 12 21 23 35 47 56 66 97 689 854
एल्गोरिदम
shellSort(array, size)
इनपुट: डेटा की एक सरणी, और सरणी में कुल संख्या
आउटपुट: क्रमबद्ध सरणी
शुरुआत gap := size / 2 के लिए, जब gap > 0 और gap को gap / 2 से अपडेट किया जाता है तो करें j:= gap से size– 1 तक करें k := j-gap से 0 तक, गैप मान से घटाकर करें यदि array[k+gap] >= array[k] ब्रेक अन्यथा array[k + gap] को array[k] से स्वैप करें हो गया हो गया हो गया अंत
उदाहरण कोड
#include<iostream> using namespace std; void swapping(int &a, int &b) { //a और b की सामग्री स्वैप करें int temp; temp = a; a = b; b = temp; } void display(int *array, int size) { for(int i = 0; i<size; i++) cout << array[i] << " "; cout << endl; } void shellSort(int *arr, int n) { int gap, j, k; for(gap = n/2; gap > 0; gap = gap / 2) { //प्रारंभ में gap = n/2, gap /2 से घटाकर for(j = gap; j<n; j++) { for(k = j-gap; k>=0; k -= gap) { if(arr[k+gap] >= arr[k]) break; else swapping(arr[k+gap], arr[k]); } } } } 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); shellSort(arr, n); cout << "सॉर्टिंग के बाद सरणी: "; display(arr, n); }
आउटपुट
तत्वों की संख्या दर्ज करें: 10 तत्व दर्ज करें: 23 56 97 21 35 689 854 12 47 66 सॉर्टिंग से पहले सरणी: 23 56 97 21 35 689 854 12 47 66 सॉर्टिंग के बाद सरणी: 12 21 23 35 47 56 66 97 689 854
