shell sort c with examples
C ++ में शेल सॉर्ट तकनीक: एक संपूर्ण अवलोकन।
शैल सॉर्ट को अक्सर सम्मिलन सॉर्ट पर सुधार के रूप में कहा जाता है। सम्मिलन प्रकार में, हम तत्वों की तुलना करने के लिए 1 से वेतन वृद्धि लेते हैं और उन्हें उनकी उचित स्थिति में डालते हैं।
शेल सॉर्ट में, सूची को छोटे सब्लिस्ट की संख्या में तोड़कर अलग किया जाता है। यह आवश्यक नहीं है कि सूचियों को सन्निहित तत्वों के साथ होना चाहिए। इसके बजाय, शेल सॉर्ट तकनीक वेतन वृद्धि i का उपयोग करती है, जिसे 'गैप' भी कहा जाता है और इसका उपयोग उन तत्वों की सूची बनाने के लिए किया जाता है जो 'i' तत्व अलग हैं।
=> पूर्ण सी ++ ट्यूटोरियल सूची देखने के लिए यहां देखें।
सबसे अच्छा यूट्यूब एमपी 3 एप्लिकेशन में कनवर्ट करें
आप क्या सीखेंगे:
सामान्य एल्गोरिथम
शेल प्रकार के लिए सामान्य एल्गोरिथ्म नीचे दिया गया है।
शेल_सोर्ट (ए, एन)
जहां ए - सूची को क्रमबद्ध किया जाना है; एन - गैप_साइज
set gap_size = N, flag = 1
जबकि gap_size> 1 या ध्वज = 1, दोहराएँ
शुरू
झंडा लगाना = ०
set gap_size = (गैप_साइज़ + 1) / 2
समाप्त
i = 0 से i के लिए<(N-gap_size) repeat
शुरू
अगर A (i + gap_size)> A (i)
स्वैप A (i + gap_size), A (i)
झंडा लगाना = ०
समाप्त
समाप्त
इस प्रकार उपरोक्त एल्गोरिथ्म में, हम पहले N सेट करते हैं, जो शेल ए का उपयोग करके सरणी A को सॉर्ट करने के लिए गैप है। अगले चरण में, हम अंतराल का उपयोग करके सरणी को उप-सरणियों में विभाजित करते हैं। फिर अगले चरण में, हम प्रत्येक उप-सरणियों को क्रमबद्ध करते हैं ताकि लूप के अंत में हमें एक सॉर्ट किया गया सरणी मिल सके।
इसके बाद, आइए एक चित्रात्मक प्रतिनिधित्व का उपयोग करके शेल प्रकार को बेहतर ढंग से समझने के लिए एक विस्तृत उदाहरण पर विचार करें।
चित्रण
आइए एक उदाहरण के साथ शैल प्रकार को चित्रित करें।
10 तत्वों के निम्नलिखित सरणी पर विचार करें।
यदि हम 3 का अंतर प्रदान करते हैं, तो हमारे पास प्रत्येक तत्व के साथ निम्नलिखित उप-सूचियाँ होंगी, जो 3 तत्वों के अलावा है। हम फिर इन तीन उपशास्त्रीयों को क्रमबद्ध करते हैं।
क्रमबद्ध उप-सूची और परिणामी सूची जो हम तीन क्रमबद्ध उपसूची के संयोजन के बाद प्राप्त करते हैं, नीचे दी गई हैं।
सॉर्ट किए गए सबरेज़ को मर्ज करने के बाद हमने जो उपर्युक्त सरणी प्राप्त की है, वह लगभग छांट ली गई है। अब हम इस सूची पर सम्मिलन प्रकार का प्रदर्शन कर सकते हैं और संपूर्ण सरणी को क्रमबद्ध कर सकते हैं। यह अंतिम चरण आपके संदर्भ के लिए नीचे दिखाया गया है।
जैसा कि ऊपर देखा गया है, शेल सॉर्ट करने के बाद और सॉर्ट किए गए सब्लिस्ट्स को मर्ज करने के बाद, हमें सूची को पूरी तरह से सॉर्ट करने के लिए केवल तीन चालों की आवश्यकता थी। इस प्रकार हम देख सकते हैं कि हम सरणी को क्रमबद्ध करने के लिए आवश्यक चरणों की संख्या को काफी कम कर सकते हैं।
उप-सूची बनाने के लिए वेतन वृद्धि का विकल्प शेल प्रकार की एक अनूठी विशेषता है।
C ++ उदाहरण
आइए हम नीचे C ++ में शेल प्रकार के कार्यान्वयन को देखते हैं।
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18,24,8,95,101}, i; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i आउटपुट:
क्रमबद्ध किया जाना है:
45 23 53 43 18 24 8 95 101
शेल प्रकार के बाद सरणी:
8 18 23 24 43 45 53 95 101
हमने उसी सूची का उपयोग किया है जिसका उपयोग हमने चित्रण में किया था और हम देख सकते हैं कि हम शुरू में दो उप-सूचियाँ बनाकर शुरू करते हैं और फिर अंतर को और कम कर देते हैं। एक बार उप सूची निर्दिष्ट अंतराल के अनुसार बनाई जाती है, हम प्रत्येक उप सूचियों को क्रमबद्ध करते हैं। सभी उप सूचियों को क्रमबद्ध करने के बाद, हमें लगभग छांटी गई सूची मिलती है। अब इस सूची को मूल सम्मिलन प्रकार का उपयोग करके क्रमबद्ध किया जा सकता है जो बहुत कम चालें लेगा।
अगला, जावा भाषा का उपयोग करते हुए शेल प्रकार को लागू करते हैं।
जावा उदाहरण
// Java class for ShellSort class ShellSort { //function to sort the array using shell sort int sort(int arr()) { int N = arr.length; // Start with a big gap, then narrow the gap for (int gap = N/2; gap > 0; gap /= 2) { //sort sub lists created by applying gap for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } } class Main{ public static void main(String args()) { int arr() = {45,23,53,43,18,24,8,95,101}; int N = arr.length; System.out.println('Array to be sorted: '); for (int i=0; i आउटपुट:
क्रमबद्ध किया जाना है:
45 23 53 43 18 24 8 95 101
शेल प्रकार के बाद सरणी:
8 18 23 24 43 45 53 95 101
हमने सी ++ और जावा प्रोग्राम दोनों में शेल प्रकार के लिए एक ही तर्क लागू किया है। इस प्रकार जैसा कि जावा कार्यक्रम में ऊपर बताया गया है, हम पहले सरणी को उप-वर्गों में विभाजित करते हैं और फिर उन्हें एक पूर्ण सॉर्ट किए गए सरणी को प्राप्त करने के लिए सॉर्ट करते हैं।
निष्कर्ष
शैल सॉर्ट अत्यधिक कुशल एल्गोरिथ्म है जो सम्मिलन प्रकार पर सुधार करने के लिए आता है।
जब सम्मिलन प्रकार 1 के द्वारा अपने तत्वों को बढ़ाता है, तो शेल सॉर्ट पैरामीटर 'गैप' का उपयोग करके सरणी को उप-सरणियों में विभाजित करता है जिनके तत्व 'अंतर' हैं। फिर हम संपूर्ण सॉर्ट किए गए सरणी को प्राप्त करने के लिए सम्मिलन प्रकार का उपयोग करके व्यक्तिगत सूची को सॉर्ट कर सकते हैं।
शैल सॉर्ट प्रविष्टि सॉर्ट की तुलना में तेज़ी से कार्य करता है और प्रविष्टि सॉर्ट की तुलना में सरणी को सॉर्ट करने के लिए कम चाल लेता है। हमारा आगामी ट्यूटोरियल डेटा संरचनाओं को छांटने के लिए ढेर सॉर्ट तकनीक के बारे में सभी का पता लगाएगा।
=> स्क्रैच से C ++ जानने के लिए यहाँ जाएँ।
अनुशंसित पाठ
- चयन सी में सी + + उदाहरण के साथ
- MongoDB सॉर्ट () उदाहरण के साथ विधि
- सिंटैक्स, विकल्प और उदाहरण के साथ यूनिक्स सॉर्ट कमांड
- उदाहरणों के साथ C ++ में बबल सॉर्ट
- उदाहरणों के साथ C ++ में प्रविष्टि सॉर्ट करें
- उदाहरणों के साथ C ++ में मर्ज करें
- उदाहरणों के साथ C ++ में ढेर छाँटें
- उदाहरणों के साथ C ++ में त्वरित क्रमबद्ध