بلبل جي ترتيب جاوا

جيڪڏهن توهان ڪڏهن ٻڌو آهي پروگرامنگ ۾ طريقن کي ترتيب ڏيڻ، گهڻو ڪري اهو هو بلبل ترتيب الگورٿم. اهو هڪ مشهور آهي. هر پروگرامر بلبل جي ترتيب کي ڄاڻي ٿو (يا گهٽ ۾ گهٽ ان جي باري ۾ ٻڌو جڏهن ته سکيا) نه ته اهو دنيا ۾ بهترين ترتيب ڏيڻ وارو الگورتھم آهي، پر اهو آسان آهي. ھي الگورتھم عام طور تي سکيا جي مقصدن لاءِ استعمال ٿيندو آھي يا توھان ان کي حاصل ڪري سگھوٿا پنھنجي جاوا جونيئر انٽرويو ۾ ڪم جي طور تي. Java Bubble sort algorithm سمجھڻ تمام آسان آھي، پر اھو ڪو ڪارائتو نھ آھي. بهرحال، اچو ته ان کي ٻاهر ڪڍيو.

ڇا ترتيب ڏيڻ

سڀ کان پهريان، توهان کي سمجهڻ جي ضرورت آهي ته ڇا ترتيب ڏيڻ عام طور تي آهي ۽ ڇا اسان جاوا پروگرامن ۾ ترتيب ڏئي سگهون ٿا. جيڪڏهن اسان ٻن يا وڌيڪ عنصرن يا شين جو انهن جي ڪنهن به خاصيت سان مقابلو ڪري سگهون ٿا، ان جو مطلب اهو آهي ته انهن کي هن وصف سان ترتيب ڏئي سگهجي ٿو. مثال طور، انگ اکر يا نزولي ترتيب ۾ يا لفظن جي الفابيٽ ۾. تنهن ڪري، عناصر کي هڪ ٻئي سان مقابلو ڪرڻ گهرجي. رستي جي ذريعي، ڇا جي عناصر؟ جاوا ۾، اسان مجموعن جي عناصرن جو مقابلو ڪري سگھون ٿا. مثال طور اسان ترتيب ڏئي سگھون ٿا Array يا ArrayList of integers, Strings وغيره.

بلبل جي ترتيب ڪيئن ڪم ڪندو آهي

اچو ته چئو ته، اسان کي انٽيجرز جي هڪ صف کي ترتيب ڏيڻ جي ضرورت آهي وڌندي ترتيب ۾، يعني ننڍي کان وڏي انگ تائين. پهرين، اسان سڄي صف سان گڏ وڃون ٿا ۽ هر 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 هاڻي حتمي پوزيشن ۾ آهي، ۽ اسان کي ان کي فهرست جي "دم" سان مقابلو ڪرڻ جي ضرورت ناهي، اهو اڳ ۾ ئي ترتيب ڏنل آهي. بلبل جي ترتيب واري الگورتھم جي ٻئي قدم جو نتيجو ايندڙ صف آھي: جيئن توھان ڏسي سگھوٿا، ھي صف اڳ ۾ ئي ترتيب ڏنل آھي. بهرحال بلبل جي ترتيب واري الگورتھم کي گهٽ ۾ گهٽ هڪ ڀيرو وڌيڪ وڃڻ گهرجي. قدم 3. اسان هڪ ڀيرو ٻيهر صفن مان گذري رهيا آهيون. هتي مٽائڻ لاءِ ڪجھ به ناهي، تنهن ڪري جيڪڏهن اسان استعمال ڪري رهيا آهيون ”بهتر“ بلبل ترتيب الگورٿم (پڙهڻ سان ته گهٽ ۾ گهٽ هڪ بدلي اڳئين قدم تي ڪيو ويو هو) هي قدم آخري آهي.

بلبل ترتيب جاوا ڪوڊ

بلبل جي ترتيب جاوا حقيقي

اچو ته بلبل جي ترتيب لاءِ ٻه طريقا ٺاھيون. پهريون، bubbleSort(int[] myArray) هڪ جهاز آهي. اهو هر وقت صف جي ذريعي هلندو آهي. ٻيو، optimized BubbleSort(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]

بلبل جي ترتيب ڪيتري موثر آهي؟

بلبل ترتيب لاڳو ڪرڻ لاء آسان ترين الگورتھم مان هڪ آهي پر اهو ڪارائتو ناهي. ان کي هڪ جوڙي جي ضرورت آهي nested loops. ايستائين جو الورورٿم جي هڪ بهتر ورزن ۾ بدترين صورت ۾ (ڊيٽا سيٽ جو هر عنصر مطلوبه هڪ لاءِ ريورس آرڊر ۾ هوندو آهي) ٻاهرئين لوپ ڊيٽا سيٽ جي هر اين عناصر لاءِ هڪ ڀيرو ٻيهر ورجائي ٿو. اندروني لوپ n جي ڀيٽ ۾ پھريون ڀيرو، ( n-1 ) ٻئي لاء، وغيره. ان ڪري، سڀ n حاصل ڪرڻ لاءِ ، عناصر کي ترتيب ڏيڻ لاءِ، لوپ کي n*(n-1)/2 ڀيرا ڪم ڪرڻو پوندو. اهو سڏي ٿو O (n ² ) وقت جي پيچيدگي ۽ مطلب اهو آهي ته الورورٿم هڪ صف جي 1000 عناصرن لاءِ اٽڪل 500 000 موازنہ ڪندو آهي. بهرحال، بلبل جي ترتيب واري الگورتھم ميموري جي استعمال ۾ تمام مؤثر آهي (ياداشت جي پيچيدگي آهي O(n) ) ۽ حقيقت ۾ تقريبا ترتيب ڏنل ننڍن ڊيٽا سيٽن لاء سٺو آهي.