बबल सॉर्ट जावा

यदि आपने कभी प्रोग्रामिंग में छँटाई के तरीकों के बारे में सुना है, तो सबसे अधिक संभावना है कि यह बबल सॉर्ट एल्गोरिथम था। यह एक प्रसिद्ध है। हर प्रोग्रामर बबल सॉर्ट जानता है (या सीखने के दौरान कम से कम इसके बारे में सुना है) इसलिए नहीं कि यह दुनिया में सबसे अच्छा सॉर्टिंग एल्गोरिदम है, बल्कि सबसे आसान है। यह एल्गोरिथ्म आमतौर पर सीखने के उद्देश्यों के लिए उपयोग किया जाता है या आप इसे अपने जावा जूनियर साक्षात्कार में एक कार्य के रूप में प्राप्त कर सकते हैं। जावा बबल सॉर्ट एल्गोरिथम समझने में बहुत आसान है, हालांकि यह कुशल नहीं है। वैसे भी, आइए इसका पता लगाएं।

छँटाई क्या है

सबसे पहले, आपको यह समझने की आवश्यकता है कि सामान्य रूप से छँटाई क्या है और हम जावा प्रोग्राम में क्या छँटाई कर सकते हैं। यदि हम दो या दो से अधिक तत्वों या वस्तुओं की तुलना उनकी किसी विशेषता से कर सकते हैं, तो इसका अर्थ है कि उन्हें इस विशेषता द्वारा क्रमबद्ध किया जा सकता है। उदाहरण के लिए, आरोही या अवरोही क्रम में संख्याएँ या वर्णानुक्रम में शब्द। इसलिए, तत्वों को एक दूसरे के साथ तुलनीय होना चाहिए। वैसे, किस के तत्व? Java में, हम Collections के Elements की तुलना कर सकते हैं। उदाहरण के लिए हम पूर्णांकों, स्ट्रिंग्स आदि के Array या ArrayList को सॉर्ट कर सकते हैं।

बबल सॉर्ट कैसे काम करता है

मान लीजिए, हमें पूर्णांकों की एक सरणी को आरोही क्रम में, यानी सबसे छोटी से सबसे बड़ी संख्या तक क्रमबद्ध करने की आवश्यकता है। सबसे पहले, हम पूरे ऐरे के साथ जा रहे हैं और हर 2 पड़ोसी तत्वों की तुलना करते हैं। यदि वे गलत क्रम में हैं (बायां पड़ोसी दाएं से बड़ा है), हम उन्हें अदला-बदली करते हैं। अंत में पहले पास पर यह सबसे बड़ा तत्व दिखाई देगा (यदि हम आरोही क्रम में क्रमबद्ध करें)। आप कह सकते हैं, सबसे बड़ा तत्व "पॉप अप"। बबल सॉर्ट एल्गोरिथम नाम का यही कारण है। हम पहले चरण को पहले से अगले-से-अंतिम तत्व तक दोहराते हैं। हमें अगला-से-अंतिम स्थान पर दूसरा सबसे बड़ा तत्व मिला है। और इसी तरह। यदि पिछले चरण में कम से कम एक एक्सचेंज किया गया था, तो हम एल्गोरिथम को थोड़ा सुधार सकते हैं। यदि ऐसा नहीं है तो हम अपने सरणी के साथ चलना बंद कर देते हैं।

बुलबुला छँटाई उदाहरण

आइए पूर्णांकों की सरणी को क्रमबद्ध करें, एक, जिसे आप चित्र पर नीचे देख सकते हैं। चरण 1: हम सरणी से गुजर रहे हैं। एल्गोरिथ्म पहले दो तत्वों (सूचकांक 0 और 1 के साथ), 8 और 7 से शुरू होता है, और जाँचता है कि क्या वे सही क्रम में हैं। जाहिर है, 8> 7, तो हम उन्हें अदला-बदली करते हैं। अगला, हम दूसरे और तीसरे तत्वों (सूचकांक 1 और 2) को देखते हैं, अब ये 8 और 1 हैं। उसी कारण से, हम उन्हें स्वैप करते हैं। तीसरी बार हम 8 और 2 और कम से कम 8 और 5 की तुलना करते हैं। हमने कुल मिलाकर चार एक्सचेंज किए: (8, 7), (8, 1), (8, 2) और (8, 5)। 8 का मान, इस सरणी में सबसे बड़ा, सूची के अंत में सही स्थिति में पॉप अप हुआ। बबल सॉर्ट एल्गोरिथम के पहले चरण के काम करने का परिणाम अगली सरणी है: चरण 2. (7,1), (7,2) और (7,5) के साथ भी ऐसा ही करना। 7 अब अंतिम स्थिति में है, और हमें इसकी तुलना सूची के "पूंछ" से करने की आवश्यकता नहीं है, यह पहले से ही क्रमबद्ध है। बबल सॉर्ट एल्गोरिदम के काम करने के दूसरे चरण का परिणाम अगली सरणी है: जैसा कि आप देख सकते हैं, यह सरणी पहले से ही क्रमबद्ध है। वैसे भी बबल सॉर्ट एल्गोरिथम को कम से कम एक बार और चलना चाहिए। चरण 3। हम एक बार फिर सरणी से गुजर रहे हैं। यहां स्वैप करने के लिए कुछ भी नहीं है, इसलिए यदि हम "बेहतर" बबल सॉर्ट एल्गोरिथ्म का उपयोग कर रहे हैं (यह जांचने के साथ कि क्या पिछले चरण में कम से कम एक एक्सचेंज किया गया था) तो यह चरण अंतिम है।

बबल सॉर्ट जावा कोड

बबल सॉर्ट जावा प्राप्ति

चलिए बबल सॉर्ट के लिए दो तरीके बनाते हैं। पहला वाला, बबलसॉर्ट (इंट [] मायएरे) एक विमान है। यह हर बार सरणी के माध्यम से चलता है। दूसरा वाला, OptimizedBubbleSort(int myArray[]) एल्गोरिथम को रोककर अनुकूलित किया गया है यदि आंतरिक लूप किसी स्वैप का कारण नहीं बनता है। काउंटर आपको दिखाता है कि छँटाई करते समय आपने कितने कदम उठाए। यहाँ हमें बबल सॉर्ट जावा प्राप्ति मिली है:

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

बबल सॉर्ट जावा एल्गोरिथम कार्य का परिणाम:

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

बबल सॉर्ट कितना कुशल है?

बबल सॉर्ट लागू करने के लिए सबसे आसान एल्गोरिदम में से एक है लेकिन यह कुशल नहीं है। इसके लिए नेस्टेड लूप्स की एक जोड़ी की आवश्यकता होती है। यहां तक ​​​​कि सबसे खराब स्थिति में एल्गोरिथ्म के एक अनुकूलित संस्करण में (डेटा सेट का प्रत्येक तत्व वांछित के विपरीत क्रम में है) बाहरी लूप डेटा सेट के प्रत्येक n तत्वों के लिए एक बार पुनरावृत्त करता है। आंतरिक पाश पहली बार n बार दोहराता है, ( n-1 ) दूसरी बार, और इसी तरह। इसलिए, सभी n तत्वों को क्रमबद्ध करने के लिए, लूप को n*(n-1)/2 बार निष्पादित करने की आवश्यकता है। यह ओ (एन ² ) कहता हैसमय जटिलता और इसका मतलब है कि एल्गोरिथ्म एक सरणी के 1000 तत्वों के लिए लगभग 500 000 तुलना करता है। हालाँकि, मेमोरी उपयोग में बबल सॉर्ट एल्गोरिथ्म बहुत प्रभावी है (मेमोरी जटिलता O(n) है ) और लगभग सॉर्ट किए गए छोटे डेटासेट के लिए वास्तव में अच्छा है।