جاوا ۾ بلبل جي ترتيب کي لاڳو ڪرڻ

اتي ڪافي تعداد ۾ ترتيب ڏيڻ وارا الگورتھم آھن، انھن مان گھڻا خاص آھن ۽ ترقي ڪيا ويا آھن انھن کي حل ڪرڻ لاءِ ھڪڙي تنگ رينج جي مسئلن کي حل ڪرڻ ۽ خاص قسم جي ڊيٽا سان ڪم ڪرڻ لاءِ. پر انهن سڀني قسمن جي وچ ۾، آسان ترين الگورتھم مناسب طور تي بلبل ترتيب آهي، جيڪو ڪنهن به پروگرامنگ ٻولي ۾ لاڳو ڪري سگهجي ٿو. ان جي سادگي جي باوجود، اهو ڪيترن ئي پيچيده الگورتھم کي هيٺ رکي ٿو. هڪ ٻيو اهم فائدو ان جي سادگي آهي، ۽ تنهن ڪري، اهو ياد ڪري سگهجي ٿو ۽ فوري طور تي لاڳو ٿئي ٿو، بغير ڪنهن اضافي ادب جي توهان جي سامهون.

تعارف

سڄو جديد انٽرنيٽ ڊيٽابيس ۾ گڏ ڪيل ڊيٽا جي جوڙجڪ جي مختلف قسمن جي وڏي تعداد تي مشتمل آهي. اهي ھر قسم جي معلومات کي ذخيرو ڪن ٿا، صارفين جي ذاتي ڊيٽا کان وٺي انتهائي ذھني خودڪار سسٽم جي سيمينٽڪ ڪور تائين. چوڻ جي ضرورت ناهي، ڊيٽا جي ترتيب ڏنل معلومات جي هن وڏي مقدار ۾ هڪ انتهائي اهم ڪردار ادا ڪري ٿي. ڊيٽابيس ۾ ڪنهن به معلومات کي ڳولڻ کان اڳ ترتيب ڏيڻ هڪ لازمي قدم ٿي سگهي ٿو، ۽ ترتيب ڏيڻ جي علم الورورٿم پروگرامنگ ۾ تمام اهم ڪردار ادا ڪري ٿو.

مشين جي اکين ۽ انساني اکين ذريعي ترتيب ڏيڻ

اچو ته تصور ڪريو ته توهان کي ترتيب ڏيڻ جي ضرورت آهي 5 ڪالمن کي مختلف اونچائي جي ترتيب ۾. انهن ڪالمن جو مطلب ٿي سگهي ٿو ڪنهن به قسم جي معلومات (اسٽاڪ جي قيمت، ڪميونيڪيشن چينل بينڊوڊٿ، وغيره)؛ توهان هن ڪم جا پنهنجا ڪجهه ورجن پيش ڪري سگهو ٿا ته جيئن ان کي وڌيڪ واضح ڪيو وڃي. خير، مثال طور، اسان اونچائي جي حساب سان Avengers ترتيب ڏينداسين: ڪمپيوٽر پروگرام جي برعڪس، ترتيب ڏيڻ توهان لاءِ ڏکيو نه هوندو، ڇاڪاڻ ته توهان پوري تصوير ڏسي سگهو ٿا ۽ فوري طور تي اندازو لڳائي سگهو ٿا ته ڪهڙي هيرو کي منتقل ڪرڻ جي ضرورت آهي جتي ترتيب ڏيڻ جي اوچائي ڪاميابي سان مڪمل ٿيڻ لاءِ. توهان شايد اڳ ۾ ئي اندازو لڳايو آهي ته هن ڊيٽا جي جوڙجڪ کي ترتيب ڏيڻ جي ترتيب ۾، صرف هولڪ ۽ آئرن مين جي جڳهن کي تبديل ڪريو:

ٿي ويو!

۽ هي ترتيب ڪاميابي سان مڪمل ڪندو. بهرحال، ڪمپيوٽر، توهان جي برعڪس، ڪجهه بيوقوف آهي ۽ مڪمل طور تي سڄي ڊيٽا جي جوڙجڪ کي ڏسڻ ۾ نٿو اچي. ان جي ڪنٽرول پروگرام صرف هڪ وقت ۾ ٻه قدر compare ڪري سگهو ٿا. هن مسئلي کي حل ڪرڻ لاء، هن کي پنهنجي يادگيري ۾ ٻه نمبر رکڻو پوندو ۽ انهن تي هڪ مقابلي واري آپريشن کي انجام ڏيڻو پوندو، ۽ پوء ٻئي نمبرن جي جوڙي ڏانهن وڃو، ۽ ائين ئي جيستائين سڀني ڊيٽا جو تجزيو ڪيو وڃي. تنهن ڪري، ڪنهن به ترتيب ڏيڻ واري الگورتھم کي ٽن مرحلن جي صورت ۾ تمام آسان بڻائي سگهجي ٿو:

• ٻن عنصرن جي ڀيٽ ڪريو؛
• تبديل ڪريو يا انھن مان ھڪڙو نقل ڪريو؛
• ايندڙ عنصر ڏانھن وڃو؛

مختلف الگورتھم انهن عملن کي مختلف طريقن سان انجام ڏئي سگھن ٿا، پر اسان اڳتي وڌنداسين ته ڪيئن بلبل جي ترتيب ڪم ڪري ٿي.

بلبل ترتيب الگورٿم

بلبل جي ترتيب کي سڀ کان آسان سمجهيو ويندو آهي، پر هن الگورتھم کي بيان ڪرڻ کان اڳ، اچو ته تصور ڪريون ته توهان اونچائي جي حساب سان Avengers کي ڪيئن ترتيب ڏيو ٿا، جيڪڏهن توهان هڪ مشين وانگر، صرف ٻن هيروز کي هڪ ٻئي سان ڀيٽ ڪري سگهو ٿا. گهڻو ڪري، توهان هيٺيان ڪندا (سڀ کان وڌيڪ بهتر):

• توهان اسان جي صف جي عنصر صفر ڏانهن وڃو (ڪاري ويه)؛
• پهرين (Hulk) سان صفر عنصر (ڪاري وايو) جو مقابلو ڪريو؛
• جيڪڏهن عنصر صفر پوزيشن تي وڌيڪ آهي، توهان انهن کي تبديل ڪريو؛
• ٻي صورت ۾، جيڪڏهن صفر جي پوزيشن تي عنصر ننڍڙو آهي، توهان انهن کي انهن جي جڳهن تي ڇڏي ڏيو؛
• ساڄي پاسي واري پوزيشن ڏانھن وڃو ۽ مقابلي کي ورجايو (ھلڪ جو ڪئپٽن سان مقابلو ڪريو)

توھان کان پوءِ توھان پوري لسٽ ذريعي ھڪڙي پاس ۾ اھڙي الگورتھم سان، ترتيب مڪمل طور تي مڪمل نه ٿيندي. پر ٻئي طرف، فهرست ۾ سڀ کان وڏو عنصر پري ساڄي پوزيشن ڏانهن منتقل ڪيو ويندو. اهو هميشه ٿيندو، ڇاڪاڻ ته جيترو جلدي توهان سڀ کان وڏو عنصر ڳوليندا آهيو، توهان مسلسل جڳهن کي تبديل ڪندا رهندا جيستائين توهان ان کي آخر تائين منتقل نه ڪندا. اهو آهي، جيترو جلدي پروگرام "ڳولندو" هولڪ کي صف ۾، اهو کيس اڳتي وڌايو ويندو فهرست جي آخر تائين: اهو ئي سبب آهي ته هن الگورتھم کي بلبل ترتيب سڏيو ويندو آهي، ڇاڪاڻ ته ان جي عمل جي نتيجي ۾، فهرست ۾ سڀ کان وڏو عنصر صف جي بلڪل چوٽي تي هوندو، ۽ سڀني ننڍن عناصر کي هڪ پوزيشن کاٻي پاسي منتقل ڪيو ويندو: ترتيب ڏيڻ کي مڪمل ڪرڻ لاءِ، توهان کي صف جي شروعات ڏانهن موٽڻ جي ضرورت پوندي ۽ مٿي بيان ڪيل پنجن قدمن کي ٻيهر ورجائڻو پوندو، ٻيهر کاٻي کان ساڄي طرف منتقل ڪرڻ، ضروري طور تي عناصر کي موازنہ ۽ منتقل ڪرڻ. پر هن ڀيري توهان کي الورورٿم کي بند ڪرڻ جي ضرورت آهي هڪ عنصر صف جي آخر کان اڳ، ڇاڪاڻ ته اسان اڳ ۾ ئي ڄاڻون ٿا ته سڀ کان وڏو عنصر (Hulk) بلڪل صحيح پوزيشن ۾ آهي: تنهنڪري پروگرام کي ٻه لوپ هجڻ گهرجن. وڌيڪ وضاحت لاءِ، ان کان اڳ جو اسان پروگرام جي ڪوڊ جو جائزو وٺون، توهان هن لنڪ کي استعمال ڪري سگهو ٿا هڪ بصري ڏسڻ لاءِ ته ڪيئن بلبل جي ترتيب ڪم ڪري ٿي: ببل جي ترتيب ڪيئن ڪم ڪري ٿي

جاوا ۾ بلبل جي ترتيب کي لاڳو ڪرڻ

ظاهر ڪرڻ لاءِ ته جاوا ۾ ڪيئن ترتيب ڏيڻ ڪم ڪري ٿو، هتي پروگرام جو ڪوڊ آهي:

• 5 عناصر جي هڪ صف ٺاهي؛
• ان ۾ بدلائيندڙن جي عروج کي اپ لوڊ ڪري ٿو؛
• صف جي مواد کي ڏيکاري ٿو؛
• بلبل جي ترتيب کي لاڳو ڪري ٿو؛
• ترتيب ڏنل صف کي ٻيهر ڏيکاري ٿو.

توھان ھيٺ ڏنل ڪوڊ ڏسي سگھو ٿا، ۽ ان کي پنھنجي پسنديده IntelliJ IDE ۾ پڻ ڊائون لوڊ ڪري سگھو ٿا. اهو هيٺ ڏنل تجزيو ڪيو ويندو:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

ڪوڊ ۾ تفصيلي تبصرن جي باوجود، اسان پروگرام ۾ پيش ڪيل ڪجهه طريقن جي وضاحت پيش ڪندا آهيون. اهم طريقا جيڪي پروگرام ۾ مکيه ڪم ڪن ٿا ArrayBubble ڪلاس ۾ لکيل آهن. ڪلاس ۾ ھڪڙي ٺاھيندڙ ۽ ڪيترائي طريقا شامل آھن:

• into- هڪ صف ۾ عناصر داخل ڪرڻ جو طريقو؛
• printer- لڪير جي ترتيب واري صف جي مواد کي ڏيکاري ٿو؛

• toSwap- جيڪڏهن ضروري هجي ته عناصر کي ٻيهر ترتيب ڏيو. هن کي ڪرڻ لاء، هڪ عارضي متغير استعمال ڪيو ويندو آهي dummy، جنهن ۾ پهرين نمبر جي قيمت لکيل آهي، ۽ پهرين نمبر جي جاء تي ٻئي نمبر جي قيمت لکيل آهي. عارضي متغير مان مواد وري ٻئي نمبر تي لکيل آهن. هي ٻن عناصر کي مٽائڻ لاء هڪ معياري ٽيڪنڪ آهي.

  ۽ آخر ۾ مکيه طريقو:

• bubbleSorter- جيڪو مکيه ڪم ڪري ٿو ۽ صف ۾ محفوظ ڪيل ڊيٽا کي ترتيب ڏئي ٿو، اسان ان کي الڳ الڳ پيش ڪنداسين:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

هتي توهان کي ٻه ڳڻپيندڙن تي ڌيان ڏيڻ گهرجي: خارجي out۽ اندروني in. خارجي ڪائونٽرout صف جي پڇاڙيءَ کان قدرن کي ڳڻڻ شروع ڪري ٿو ۽ هر نئين پاس سان آهستي آهستي گھٽجي ٿو. outهر نئين پاس سان، متغير کي وڌيڪ کاٻي طرف منتقل ڪيو ويو آهي ته جيئن اڳ ۾ ئي ترتيب ڏنل قدرن تي اثر انداز نه ٿئي صف جي ساڄي پاسي. اندروني ڪائونٽرin صف جي شروعات کان قدرن کي ڳڻڻ شروع ڪري ٿو ۽ تدريجي طور تي هر نئين پاس تي هڪ وڌائي ٿو. واڌارو inٿئي ٿو جيستائين اهو پهچي وڃي out(موجوده پاس ۾ آخري تجزياتي عنصر). اندروني لوپ inٻن ڀرپاسي سيلز in۽ in+1. جيڪڏھن inھڪڙو وڏو تعداد ان کان وڌيڪ ۾ ذخيرو ٿيل آھي in+1، پوء طريقو سڏيو ويندو آھي toSwap، جيڪو انھن ٻنھي نمبرن جي جڳھ کي تبديل ڪري ٿو.

نتيجو

بلبل جي ترتيب وارو الگورتھم ھڪڙو سست آھي. جيڪڏهن صف N عناصر تي مشتمل آهي، ته پوءِ N-1 جو مقابلو ڪيو ويندو پهرين پاس تي، N-2 ٻئي تي، پوءِ N-3 وغيره. اھو آھي، پاسن جو ڪل تعداد ڪيو ويندو: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 اھڙي طرح، ترتيب ڏيڻ وقت، الگورتھم اٽڪل 0.5x (N ^2) موازن کي انجام ڏئي ٿو. N = 5 لاءِ، موازن جو تعداد لڳ ڀڳ 10 ٿيندو، N = 10 لاءِ موازن جو تعداد وڌي 45 ٿي ويندو. اھڙيءَ طرح جيئن جيئن عنصرن جو تعداد وڌندو آھي، تيئن تيئن ترتيب ڏيڻ جي پيچيدگيءَ ۾ اضافو ٿيندو آھي: الورورٿم جي رفتار متاثر ٿئي ٿي نه رڳو پاسن جي تعداد سان، پر ان سان گڏوگڏ اجازتن جي تعداد جي ذريعي جيڪا ٿيڻ جي ضرورت آهي. بي ترتيب واري ڊيٽا لاءِ، اجازتن جو تعداد اوسط (N^2) / 4، جيڪو لڳ ڀڳ اڌ جيترو آهي پاسن جي تعداد جي برابر. بهرحال، بدترين صورت ۾، اجازتن جو تعداد پڻ ٿي سگهي ٿو N^2 / 2 - اهو معاملو آهي جيڪڏهن ڊيٽا شروعاتي طور تي ريورس آرڊر ۾ ترتيب ڏنل آهي. ان حقيقت جي باوجود ته هي هڪ بلڪه سست ترتيب ڏيڻ وارو الگورتھم آهي، اهو ڄاڻڻ ۽ سمجهڻ تمام ضروري آهي ته اهو ڪيئن ڪم ڪري ٿو، ۽، جيئن اڳ ذڪر ڪيو ويو آهي، اهو وڌيڪ پيچيده الگورتھم جو بنياد آهي. جي جي ڊي!