शेल सॉर्ट

इस ट्यूटोरियल में, आप सीखेंगे कि शेल किस प्रकार काम करता है। साथ ही, आपको C, C ++, Java और पायथन में शेल प्रकार के कार्यशील उदाहरण मिलेंगे।

शैल सॉर्ट एक एल्गोरिथ्म है जो सबसे पहले तत्वों को एक दूसरे से दूर करता है और क्रमबद्ध रूप से तत्वों के बीच के अंतराल को कम करता है। यह सम्मिलन प्रकार का एक सामान्यीकृत संस्करण है।

शेल सॉर्ट में, एक विशिष्ट अंतराल पर तत्वों को सॉर्ट किया जाता है। उपयोग किए गए अनुक्रम के आधार पर तत्वों के बीच का अंतराल धीरे-धीरे कम हो जाता है। शेल सॉर्ट का प्रदर्शन किसी दिए गए इनपुट सरणी के लिए उपयोग किए जाने वाले अनुक्रम के प्रकार पर निर्भर करता है।

उपयोग किए गए कुछ इष्टतम क्रम हैं:

• शेल का मूल अनुक्रम: N/2 , N/4 ,… , 1
• नुथ की वेतन वृद्धि: 1, 4, 13,… , (3k - 1) / 2
• सेडगेविक की वृद्धि: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
• हिब्बर्ड का वेतन वृद्धि: 1, 3, 7, 15, 31, 63, 127, 255, 511…
• पापेरनोव और स्टेज़िव इंक्रीमेंट: 1, 3, 5, 9, 17, 33, 65,…
• प्रैट: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

शेल कैसे काम करता है?

1. मान लीजिए, हमें निम्नलिखित सरणी को क्रमबद्ध करने की आवश्यकता है। प्रारंभिक सरणी
2. हम (N/2, N/4,… 1अपने एल्गोरिथ्म में अंतराल के रूप में शेल के मूल अनुक्रम का उपयोग कर रहे हैं )।
   पहले लूप में, यदि सरणी का आकार है N = 8, तो अंतराल के अंतराल पर पड़े तत्वों N/2 = 4की तुलना की जाती है और स्वैप किया जाता है यदि वे क्रम में नहीं हैं।
   1. 4 तत्व के साथ 0 तत्व की तुलना की जाती है।
   2. यदि 0 तत्व 4 वें से अधिक है, तो 4 वें तत्व को पहले tempचर में संग्रहीत किया जाता है और 0thतत्व (यानी अधिक से अधिक तत्व) को 4thस्थिति में संग्रहीत किया जाता है और संग्रहीत तत्व tempको 0thस्थिति में संग्रहीत किया जाता है । एन / 2 अंतराल पर तत्वों को पुनर्व्यवस्थित करें
      यह प्रक्रिया सभी शेष तत्वों के लिए चलती है। N / 2 अंतराल पर सभी तत्वों को पुनर्व्यवस्थित करें
3. दूसरे लूप में, एक अंतराल N/4 = 8/4 = 2लिया जाता है और फिर से इन अंतरालों पर पड़े तत्वों को छांटा जाता है। N / 4 अंतराल पर तत्वों को पुनर्व्यवस्थित करें
   आप इस बिंदु पर भ्रमित हो सकते हैं। वर्तमान अंतराल पर पड़े सरणी के सभी तत्वों की तुलना की जाती है।
   4 वें और 2ndस्थिति के तत्वों की तुलना की जाती है। 2 और 0thस्थिति के तत्वों की तुलना भी की जाती है। वर्तमान अंतराल पर पड़े सरणी के सभी तत्वों की तुलना की जाती है।
4. शेष तत्वों के लिए भी यही प्रक्रिया चलती है। N / 4 अंतराल पर सभी तत्वों को पुनर्व्यवस्थित करें
5. अंत में, जब अंतराल N/8 = 8/8 =1तब 1 के अंतराल पर पड़े हुए सरणी तत्व छांटे जाते हैं। सरणी अब पूरी तरह से सॉर्ट की गई है। एन / 8 अंतराल पर तत्वों को पुनर्व्यवस्थित करें

शेल सॉर्ट एल्गोरिथम

 शेलशॉर्ट (सरणी, आकार) अंतराल के लिए मैं <- आकार / 2n नीचे 1 से प्रत्येक अंतराल के लिए "i" सरणी में सभी तत्वों को अंतराल पर "i" अंत गोले में सॉर्ट करें

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++

# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)

// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 

// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 

// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); ) 

जटिलता

शेल सॉर्ट एक अस्थिर छँटाई एल्गोरिथ्म है क्योंकि यह एल्गोरिथ्म अंतराल के बीच में पड़े तत्वों की जांच नहीं करता है।

समय जटिलता

• सबसे खराब मामला जटिलता : शेल सॉर्ट के लिए वर्स्ट केस जटिलता से कम या बराबर हमेशा से कम या बराबर होता है । Poonen प्रमेय के अनुसार, खोल प्रकार के लिए सबसे खराब स्थिति जटिलता है या या या बीच में कुछ।O(n2)
O(n2)
Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
• सर्वश्रेष्ठ मामले की जटिलता : O(n*log n)
  जब सरणी पहले से ही हल हो जाती है, तो प्रत्येक अंतराल (या वेतन वृद्धि) के लिए तुलना की कुल संख्या सरणी के आकार के बराबर होती है।
• औसत मामला जटिलता : O(n*log n)
  यह चारों ओर है ।O(n1.25)

जटिलता चुने गए अंतराल पर निर्भर करती है। उपरोक्त जटिलताएं अलग-अलग वेतन वृद्धि अनुक्रमों के लिए अलग-अलग हैं। सर्वश्रेष्ठ वेतन वृद्धि क्रम अज्ञात है।

अंतरिक्ष जटिलता:

शेल सॉर्ट के लिए अंतरिक्ष जटिलता है O(1)।

शैल क्रमबद्ध अनुप्रयोग

शेल प्रकार का उपयोग तब किया जाता है जब:

• स्टैक कॉलिंग ओवरहेड है। uClibc पुस्तकालय इस प्रकार का उपयोग करता है।
• पुनरावृत्ति एक सीमा से अधिक है। bzip2 कंप्रेसर इसका उपयोग करता है।
• जब करीबी तत्व दूर होते हैं तो सम्मिलन प्रकार अच्छा प्रदर्शन नहीं करता है। शेल सॉर्ट करीबी तत्वों के बीच की दूरी को कम करने में मदद करता है। इस प्रकार, प्रदर्शन किए जाने वाले स्वैपिंग की संख्या कम होगी।