بلبلا ترتیب جاوا

اگر آپ نے کبھی پروگرامنگ میں چھانٹنے کے طریقوں کے بارے میں سنا ہے، تو غالباً یہ ببل سورٹ الگورتھم تھا۔ یہ ایک مشہور ہے۔ ہر پروگرامر ببل کی ترتیب کو جانتا ہے (یا کم از کم سیکھنے کے دوران اس کے بارے میں سنا ہے) اس لیے نہیں کہ یہ دنیا کا بہترین الگورتھم ہے، بلکہ سب سے آسان ہے۔ یہ الگورتھم عام طور پر سیکھنے کے مقاصد کے لیے استعمال ہوتا ہے یا آپ اسے اپنے جاوا جونیئر انٹرویو میں بطور کام حاصل کر سکتے ہیں۔ Java Bubble sort algorithm سمجھنا بہت آسان ہے، تاہم یہ ایک موثر نہیں ہے۔ بہرحال، آئیے اس کا اندازہ لگا لیں۔

چھانٹی کیا ہے

سب سے پہلے، آپ کو یہ سمجھنے کی ضرورت ہے کہ عام طور پر چھانٹنا کیا ہے اور ہم جاوا پروگراموں میں کیا ترتیب دے سکتے ہیں۔ اگر ہم دو یا دو سے زیادہ عناصر یا اشیاء کا ان کی کسی صفت سے موازنہ کر سکتے ہیں، تو اس کا مطلب ہے کہ ان کو اس وصف سے ترتیب دیا جا سکتا ہے۔ مثال کے طور پر، صعودی یا نزولی ترتیب میں اعداد یا حروف تہجی کے لحاظ سے الفاظ۔ لہذا، عناصر کو ایک دوسرے کے ساتھ موازنہ کرنا ضروری ہے. ویسے، کیا عناصر؟ جاوا میں، ہم مجموعہ کے عناصر کا موازنہ کر سکتے ہیں۔ مثال کے طور پر ہم انٹیجرز، سٹرنگز وغیرہ کی 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 کی قدر، اس صف میں سب سے بڑی، فہرست کے آخر میں صحیح پوزیشن پر آ گئی۔ Bubble sort algorithm کے کام کرنے کے پہلے مرحلے کا نتیجہ اگلی صف ہے: مرحلہ 2۔ (7,1), (7,2) اور (7,5) کے ساتھ ایسا ہی کرنا۔ 7 اب آخری پوزیشن میں ہے، اور ہمیں فہرست کے "ٹیل" سے اس کا موازنہ کرنے کی ضرورت نہیں ہے، یہ پہلے سے ترتیب دی گئی ہے۔ Bubble sort algorithm کے کام کرنے کے دوسرے مرحلے کا نتیجہ اگلی صف ہے: جیسا کہ آپ دیکھ سکتے ہیں، یہ صف پہلے سے ترتیب دی گئی ہے۔ ویسے بھی ببل سورٹ الگورتھم کو کم از کم ایک بار اور جانا چاہیے۔ مرحلہ 3۔ ہم ایک بار پھر صف سے گزر رہے ہیں۔ یہاں تبادلہ کرنے کے لیے کچھ نہیں ہے، اس لیے اگر ہم "بہتر" ببل سورٹ الگورتھم استعمال کر رہے ہیں (یہ جانچنے کے ساتھ کہ آیا پچھلے مرحلے پر کم از کم ایک تبادلہ ہوا تھا) یہ مرحلہ آخری ہے۔

جاوا کوڈ بلبلا ترتیب دیں۔

بلبلا ترتیب جاوا احساس

آئیے Bubble sort کے لیے دو طریقے بناتے ہیں۔ پہلا، bubbleSort(int[] myArray) ایک طیارہ ہے۔ یہ ہر بار صف کے ذریعے چلتا ہے۔ دوسرا، 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]

بلبلا چھانٹنا کتنا موثر ہے؟

Bubble sort لاگو کرنے کے لیے سب سے آسان الگورتھم میں سے ایک ہے لیکن یہ موثر نہیں ہے۔ اسے نیسٹڈ لوپس کے جوڑے کی ضرورت ہوتی ہے۔ یہاں تک کہ بدترین صورت میں الگورتھم کے ایک بہتر ورژن میں (ڈیٹا سیٹ کا ہر عنصر مطلوبہ کے الٹ ترتیب میں ہوتا ہے) بیرونی لوپ ڈیٹا سیٹ کے n عناصر میں سے ہر ایک کے لیے ایک بار دہراتا ہے۔ اندرونی لوپ پہلی بار n بار، دوسری بار کے لیے ( n-1 )، ​​وغیرہ۔ لہذا، تمام n ، عناصر کو ترتیب دینے کے لیے، لوپس کو n*(n-1)/2 بار انجام دینے کی ضرورت ہے۔ اسے O(n ² ) وقت کی پیچیدگی کہتے ہیں اور اس کا مطلب ہے کہ الگورتھم ایک صف کے 1000 عناصر کے لیے تقریباً 500 000 موازنہ کرتا ہے۔ تاہم، ببل ترتیب الگورتھم میموری کے استعمال میں کافی موثر ہے (میموری کی پیچیدگی ہے O(n) ) اور تقریباً چھانٹی ہوئی چھوٹی ڈیٹاسیٹس کے لیے واقعی اچھا ہے۔