Java बबल सॉर्ट कैसे लिखें
जब प्रोग्रामर बबल सॉर्ट्स के बारे में बात करते हैं, तो वे उन वॉटर बबल्स के बारे में बात नहीं कर रहे होते हैं जिन्हें आपने शायद अपने जीवन में किसी बिंदु पर फूंका होगा। वे एक सॉर्टिंग एल्गोरिदम के बारे में बात कर रहे हैं जिसका उपयोग आइटम्स की सूची को ऑर्डर करने के लिए किया जाता है।
इस गाइड में, हम बबल सॉर्ट्स के बारे में बात करने जा रहे हैं और वे कैसे काम करते हैं। हम Java का उपयोग करके एक बबल सॉर्ट को इम्प्लीमेंट करने जा रहे हैं ताकि आप समझ सकें कि यह एल्गोरिदम कोड में कैसे ट्रांसलेट होता है। आगे की हलचल के बिना, आइए Java बबल सॉर्ट्स में गोता लगाएं!
Java बबल सॉर्ट क्या है?
एक बबल सॉर्ट एक एल्गोरिदम है जो आसन्न तत्वों की तुलना करके और यदि वे गलत क्रम में दिखाई देते हैं तो उन्हें स्वैप करके मानों को सॉर्ट करता है।
यह प्रक्रिया तब तक दोहराई जाती है जब तक सूची में हर आइटम सही ढंग से ऑर्डर नहीं हो जाता। बबल सॉर्ट्स का उपयोग सूची को आरोही या अवरोही क्रम में सॉर्ट करने के लिए किया जा सकता है।
बबल सॉर्ट्स एल्गोरिदम क्लासेस में सिखाया जाने वाला पहला सॉर्ट है। ऐसा इसलिए है क्योंकि वे अन्य सॉर्ट्स, जैसे इंसर्शन सॉर्ट या सिलेक्शन सॉर्ट की तुलना में समझने में आसान होते हैं, और सॉर्टिंग एल्गोरिदम का एक अच्छा परिचय प्रदान करते हैं।
बबल सॉर्ट्स तब सबसे प्रभावी होते हैं जब डेटा पहले से लगभग सॉर्टेड होता है। हालाँकि, यदि आपका डेटा बिल्कुल भी सॉर्टेड नहीं है, तो एक अन्य प्रकार का सॉर्ट अधिक कुशल हो सकता है।
बबल सॉर्ट्स कैसे काम करते हैं?
इससे पहले कि हम Java बबल सॉर्ट के लिए कोड लिखना शुरू करें, हमें पहले यह समझना होगा कि यह एल्गोरिदम व्यवहार में कैसे इम्प्लीमेंट होता है।
निम्न सूची पर विचार करें:
| 5 | 9 | 2 | 7 |
हमारा बबल सॉर्ट हमारी सूची में पहले और दूसरे तत्वों की तुलना करके शुरू होता है।
यदि पहला तत्व दूसरे तत्व से बड़ा है, तो ये तत्व पोजीशन स्वैप करते हैं। इस मामले में, 5, 9 से बड़ा नहीं है, इसलिए तत्व अपनी वही जगह पर रहते हैं।
फिर, हमारा सॉर्ट हमारी सूची में अगले दो आइटम्स की तुलना करेगा। 9, 2 से बड़ा है, और इसलिए ये दो नंबर स्वैप हो जाते हैं:
| 5 | 2 | 9 | 7 |
यह प्रक्रिया तब तक दोहराई जाती है जब तक सूची में हर आइटम की तुलना नहीं हो जाती। इस मामले में, एक और तुलना करनी है: क्या 9, 7 से बड़ा है? 9, 7 से बड़ा है, इसलिए ये नंबर स्वैप हो जाते हैं:
| 5 | 2 | 7 | 9 |
हमारी सूची लगभग ऑर्डर हो चुकी है। एक बार हर आइटम की तुलना हो जाने के बाद, बबल सॉर्ट फिर से शुरू हो जाएगा जब तक हर तत्व सॉर्ट नहीं हो जाता।
5, 2 से बड़ा है, और इसलिए ये नंबर स्वैप हो जाते हैं।
| 2 | 5 | 7 | 9 |
हमारी सूची अब सही ढंग से ऑर्डर हो गई है। हमारा बबल सॉर्ट नंबर्स की तुलना करता रहेगा जब तक यह सूची के अंत तक नहीं पहुंच जाता, और फिर यह रुक जाएगा। बस इतना ही बबल सॉर्ट के लिए है। एक बार जब आप इसे समझ लेते हैं तो यह निश्चित रूप से उपयोग करने में आसान एल्गोरिदम है।
Java बबल सॉर्ट कैसे लिखें
थ्योरी जानना एक बात है लेकिन आप यहां Java बबल सॉर्ट्स के बारे में जानने आए हैं। हमने बेहतर होगा कि Java में बबल सॉर्ट को इम्प्लीमेंट करने के तरीके पर चर्चा करें।
बबल सॉर्ट्स दो प्रकार के होते हैं:
- स्टैंडर्ड बबल सॉर्ट
- ऑप्टिमाइज़्ड बबल सॉर्ट
स्टैंडर्ड बबल सॉर्ट सभी संभावित तुलनाएं करता है भले ही array सॉर्टेड हो। इससे बबल सॉर्ट को एक्जीक्यूट होने में लगने वाला समय बढ़ जाता है। यह सॉर्ट को कम कुशल बनाता है।
ऑप्टिमाइज़्ड बबल सॉर्ट एक अतिरिक्त वेरिएबल का उपयोग करके ट्रैक करते हैं कि सूची सॉर्टेड है या नहीं। यह हमें अपने सॉर्ट को तब रोकने की अनुमति देता है जैसे ही हमारी सूची सॉर्ट हो जाती है।
आइए स्टैंडर्ड बबल सॉर्ट लिखकर शुरू करें।
स्टैंडर्ड बबल सॉर्ट
शुरू करने के लिए, हम अपने कोड में Arrays लाइब्रेरी इम्पोर्ट करने जा रहे हैं। हम बाद में अपने कोड में सॉर्टेड नंबर्स की अपनी सूची को कंसोल पर प्रिंट करने के लिए इसका उपयोग करेंगे:
import java.util.Arrays;
अब यह रास्ते से हट गया है, हम अपना एल्गोरिदम लिखना शुरू कर सकते हैं।
हम BubbleSort नामक एक क्लास को परिभाषित करके शुरू करेंगे जो हमारे Java प्रोग्राम के लिए कोड स्टोर करता है, और एक फंक्शन जो हमारे सॉर्ट को परफॉर्म करता है:
class BubbleSort { void sortNumbers(int array[]) { int size = array.length; for (int item = 0; item < size - 1; item++) { for (int j = 0; j < size - item - 1; j++) { if (array[j] > array[j + 1]) { int temporary = array[j]; array[j] = array[j + 1]; array[j + 1] = temporary; } } } } }
हमने sortNumbers नामक एक फंक्शन घोषित किया है जो पैरामीटर के रूप में एक वेरिएबल स्वीकार करता है। यह फंक्शन हमारे द्वारा निर्दिष्ट नंबर्स की सूची का आकार कैलकुलेट करके शुरू होता है।
एक बार इसकी गणना हो जाने के बाद, एक for लूप इनिशियलाइज़ किया जाता है। यह लूप हमारे array में हर आइटम के माध्यम से चलता है। हम एक और for लूप इनिशियलाइज़ करते हैं जो हमें array में प्रत्येक आइटम की तुलना करने की अनुमति देता है।
यदि सूची में बाईं ओर का आइटम दाईं ओर के नंबर से बड़ा है, तो मान स्वैप हो जाते हैं। अन्यथा, कुछ नहीं होता।
हम बाईं ओर के मान को "temporary" नामक वेरिएबल को असाइन करके इस स्वैप को करते हैं। हम तुलना के दाईं ओर के मान को बाईं ओर के मान को असाइन करते हैं। फिर, बाईं ओर के मान को temporary वेरिएबल का मान असाइन किया जाता है।
यदि 6 और 5 की तुलना की जा रही होती, तो वे स्वैप हो जाते। तो, हमारी सूची इस तरह दिखाई देती: 6, 5।
हमारा प्रोग्राम अभी कुछ नहीं करता। हमने अभी तक एक मेन प्रोग्राम नहीं लिखा है जो हमारे फंक्शन को कॉल करे और उसे सॉर्ट करने के लिए एक सूची दे।
sortNumbers फंक्शन के नीचे अपने कोड में निम्न कोड जोड़ें:
public static void main(String args[]) { int[] toSort = { 5, 9, 2, 7 }; BubbleSort sortingAlgorithm = new BubbleSort(); sortingAlgorithm.sortNumbers(toSort); System.out.println(Arrays.toString(toSort)); }
हमने toSort नामक एक वेरिएबल घोषित किया है जो उन मानों की सूची को स्टोर करता है जिन्हें हम सॉर्ट करना चाहते हैं। हमने तब BubbleSort क्लास का एक इंस्टेंस sortingAlgorithm नामक घोषित किया है, जिसका उपयोग हम अगली कोड लाइन पर sortNumbers फंक्शन को कॉल करने के लिए करते हैं। जब यह फंक्शन कॉल किया जाता है, तो हमारी सूची सॉर्ट हो जाती है।
अंत में, हम अपने सूची को स्ट्रिंग में बदलने के लिए Arrays.toString() मेथड का उपयोग करते हैं ताकि हम इसे कंसोल पर प्रिंट कर सकें। हमारा कोड लौटाता है:
[2, 5, 7, 9]
अब हमारे पास एक सॉर्टेड array है!
ऑप्टिमाइज़्ड बबल सॉर्ट
हमारे कोड को और अधिक कुशल बनाने का एक तरीका है। अभी, हमारा सॉर्ट तब तक जारी रहता है जब तक इसने सभी संभावित तुलनाएं नहीं कर लीं। इसका मतलब है कि भले ही हमारा array सॉर्टेड हो, सॉर्ट तब तक चलता रहेगा जब तक वे तुलनाएं पूरी नहीं हो जातीं।
हम अपने कोड में एक नया वेरिएबल जोड़कर इस व्यवहार को रोक सकते हैं। यह हमें अपने सॉर्ट को रोकने की अनुमति देगा यदि सूची स्वैप हो गई है। आइए इस वेरिएबल को अपने पहले के sortNumbers फंक्शन में जोड़ें:
class BubbleSort { void sortNumbers(int array[]) { int size = array.length; for (int item = 0; item < size - 1; item++) { boolean hasSwapped = false; for (int j = 0; j < size - item - 1; j++) { if (array[j] > array[j + 1]) { int temporary = array[j]; array[j] = array[j + 1]; array[j + 1] = temporary; hasSwapped = true; } } if (hasSwapped == false) { break; } } } }
हमने अपने कोड में तीन बदलाव किए हैं। अपने पहले for लूप के अंदर हमने "hasSwapped" नामक एक वेरिएबल घोषित किया है। यह वेरिएबल ट्रैक करता है कि स्वैप किया गया है या नहीं। डिफ़ॉल्ट रूप से, यह वेरिएबल "false" पर सेट है। यदि स्वैप किया जाता है, तो इस वेरिएबल का मान "true" पर सेट हो जाता है।
अपने for लूप के अंत में, हमने एक if स्टेटमेंट जोड़ा है यह जांचने के लिए कि hasSwapped false के बराबर है या नहीं। यदि कोई स्वैप नहीं किया गया है, तो array सॉर्टेड है। हम अपने लूप को एक्जीक्यूट होने से रोकने के लिए "break" कीवर्ड का उपयोग करते हैं यदि hasSwapped false के बराबर है।
आइए अपने कोड को पहले लिखे गए मेन प्रोग्राम का उपयोग करके चलाएं और देखें क्या होता है:
[2, 5, 7, 9]
हमारी सूची सॉर्ट हो गई है, लेकिन इस बार हमारा एल्गोरिदम अधिक कुशल है। यदि हम अधिक मानों वाली बड़ी सूची का उपयोग करते, तो इस एल्गोरिदम का बेहतर प्रदर्शन स्पष्ट होता। बस, आपने Java में एक ऑप्टिमाइज़्ड बबल सॉर्ट लिख लिया है!
निष्कर्ष
बबल सॉर्ट्स का उपयोग सूचियों को आरोही या अवरोही क्रम में सॉर्ट करने के लिए किया जाता है। वे आसन्न मानों की तुलना करके और यदि वे गलत क्रम में हैं तो उन्हें स्वैप करके काम करते हैं।
बबल सॉर्ट के दो प्रकार हैं: स्टैंडर्ड और ऑप्टिमाइज़्ड। स्टैंडर्ड बबल सॉर्ट्स पूर्वनिर्धारित संख्या में स्वैप करते हैं जबकि ऑप्टिमाइज़्ड बबल सॉर्ट्स केवल तब तक सॉर्ट करते रहते हैं जब तक सूची सॉर्ट नहीं हो जाती।
अब आप Java में एक विशेषज्ञ की तरह बबल सॉर्ट्स लिखना शुरू करने के लिए तैयार हैं!
