جاوا میں بلبلے کی ترتیب کو نافذ کرنا

چھانٹنے والے الگورتھم کی کافی بڑی تعداد ہے، ان میں سے بہت سے بہت مخصوص ہیں اور مسائل کی ایک تنگ رینج کو حل کرنے اور مخصوص قسم کے ڈیٹا کے ساتھ کام کرنے کے لیے تیار کیے گئے ہیں۔ لیکن اس تمام تنوع کے درمیان، سب سے آسان الگورتھم مناسب طور پر ببل ترتیب ہے، جسے کسی بھی پروگرامنگ زبان میں لاگو کیا جا سکتا ہے۔ اس کی سادگی کے باوجود، یہ بہت سے پیچیدہ الگورتھم کو زیر کرتا ہے۔ ایک اور اتنا ہی اہم فائدہ اس کی سادگی ہے، اور اس وجہ سے، آپ کے سامنے کوئی اضافی لٹریچر رکھے بغیر، اسے فوری طور پر یاد کیا اور نافذ کیا جا سکتا ہے۔

تعارف

پورا جدید انٹرنیٹ ڈیٹا بیس میں جمع کردہ مختلف قسم کے ڈیٹا ڈھانچے کی ایک بڑی تعداد پر مشتمل ہے۔ وہ صارفین کے ذاتی ڈیٹا سے لے کر انتہائی ذہین خودکار نظاموں کے سیمنٹک کور تک ہر قسم کی معلومات کو محفوظ کرتے ہیں۔ یہ کہنے کی ضرورت نہیں کہ ڈیٹا کی چھانٹی اس بڑی تعداد میں ساختی معلومات میں انتہائی اہم کردار ادا کرتی ہے۔ ڈیٹا بیس میں کسی بھی معلومات کو تلاش کرنے سے پہلے چھانٹنا ایک لازمی مرحلہ ہوسکتا ہے، اور الگورتھم کو چھانٹنے کا علم پروگرامنگ میں بہت اہم کردار ادا کرتا ہے۔

مشینی آنکھوں اور انسانی آنکھوں کے ذریعے چھانٹنا

آئیے تصور کریں کہ آپ کو مختلف بلندیوں کے 5 کالموں کو صعودی ترتیب میں ترتیب دینے کی ضرورت ہے۔ ان کالموں کا مطلب کسی بھی قسم کی معلومات (اسٹاک کی قیمتیں، کمیونیکیشن چینل بینڈوتھ وغیرہ) ہو سکتا ہے؛ آپ اسے مزید واضح کرنے کے لیے اس کام کے اپنے کچھ ورژن پیش کر سکتے ہیں۔ ٹھیک ہے، مثال کے طور پر، ہم اونچائی کے لحاظ سے Avengers کو ترتیب دیں گے: کمپیوٹر پروگرام کے برعکس، چھانٹنا آپ کے لیے مشکل نہیں ہوگا، کیونکہ آپ پوری تصویر دیکھ سکتے ہیں اور فوراً اندازہ لگا سکتے ہیں کہ اونچائی کے لحاظ سے چھانٹی کو کامیابی سے مکمل کرنے کے لیے کس ہیرو کو کہاں منتقل کرنے کی ضرورت ہے۔ آپ نے شاید پہلے ہی اندازہ لگا لیا ہے کہ اس ڈیٹا ڈھانچے کو صعودی ترتیب میں ترتیب دینے کے لیے، Hulk اور Iron Man کے مقامات کو تبدیل کرنا کافی ہے:

ہو گیا!

اور یہ ترتیب کو کامیابی سے مکمل کرے گا۔ تاہم، کمپیوٹر، آپ کے برعکس، کچھ حد تک بیوقوف ہے اور پورے ڈیٹا ڈھانچے کو مجموعی طور پر نہیں دیکھتا۔ اس کا کنٹرول پروگرام ایک وقت میں صرف دو اقدار کا موازنہ کر سکتا ہے۔ اس مسئلے کو حل کرنے کے لیے، اسے اپنی یادداشت میں دو نمبر رکھنا ہوں گے اور ان پر موازنہ آپریشن کرنا ہوگا، اور پھر نمبروں کے دوسرے جوڑے پر جانا ہوگا، اور اسی طرح جب تک کہ تمام ڈیٹا کا تجزیہ نہ ہوجائے۔ لہذا، کسی بھی ترتیب دینے والے الگورتھم کو تین مراحل کی شکل میں بہت آسان بنایا جا سکتا ہے:

• دو عناصر کا موازنہ کریں؛
• ان میں سے ایک کو تبدیل یا کاپی کریں؛
• اگلے عنصر پر جائیں؛

مختلف الگورتھم ان کارروائیوں کو مختلف طریقوں سے انجام دے سکتے ہیں، لیکن ہم اس بات پر غور کریں گے کہ بلبلے کی ترتیب کیسے کام کرتی ہے۔

بلبلا ترتیب الگورتھم

ببل چھانٹنا سب سے آسان سمجھا جاتا ہے، لیکن اس الگورتھم کو بیان کرنے سے پہلے، آئیے تصور کریں کہ آپ اونچائی کے لحاظ سے Avengers کو کس طرح ترتیب دیں گے اگر آپ ایک مشین کی طرح، ایک وقت میں صرف دو ہیروز کا ایک دوسرے سے موازنہ کر سکیں۔ زیادہ تر امکان ہے کہ، آپ مندرجہ ذیل طریقے سے (سب سے زیادہ بہترین) کریں گے:

• آپ ہماری صف کے عنصر صفر پر جائیں (بلیک بیوہ)؛
• صفر عنصر (سیاہ بیوہ) کا پہلے (ہلک) سے موازنہ کریں۔
• اگر پوزیشن صفر پر عنصر زیادہ ہے، تو آپ ان کو تبدیل کرتے ہیں؛
• دوسری صورت میں، اگر صفر کی پوزیشن پر عنصر چھوٹا ہے، تو آپ انہیں ان کی جگہ پر چھوڑ دیتے ہیں۔
• دائیں پوزیشن پر جائیں اور موازنہ کو دہرائیں (ہلک کا کیپٹن سے موازنہ کریں)

اس طرح کے الگورتھم کے ساتھ ایک پاس میں پوری فہرست سے گزرنے کے بعد، چھانٹنا مکمل طور پر مکمل نہیں ہوگا۔ لیکن دوسری طرف، فہرست میں سب سے بڑا عنصر انتہائی دائیں پوزیشن پر چلا جائے گا۔ یہ ہمیشہ ہوتا رہے گا، کیونکہ جیسے ہی آپ کو سب سے بڑا عنصر مل جائے گا، آپ اس وقت تک جگہوں کو مسلسل تبدیل کرتے رہیں گے جب تک کہ آپ اسے بالکل آخر تک نہ لے جائیں۔ یعنی جیسے ہی پروگرام ہلک کو صف میں "تلاش" کرتا ہے، یہ اسے فہرست کے بالکل آخر تک لے جائے گا: یہی وجہ ہے کہ اس الگورتھم کو ببل سورٹ کہا جاتا ہے، کیونکہ اس کے آپریشن کے نتیجے میں، فہرست میں سب سے بڑا عنصر صف کے بالکل اوپر ہوگا، اور تمام چھوٹے عناصر کو ایک پوزیشن بائیں طرف منتقل کردیا جائے گا: چھانٹنا مکمل کرنے کے لیے، آپ کو صف کے آغاز پر واپس جانا ہوگا اور اوپر بیان کیے گئے پانچ مراحل کو دوبارہ دہرانا ہوگا، دوبارہ بائیں سے دائیں منتقل کرنا ہوگا، ضرورت کے مطابق عناصر کا موازنہ اور منتقل کرنا ہوگا۔ لیکن اس بار آپ کو صف کے اختتام سے پہلے الگورتھم ایک عنصر کو روکنے کی ضرورت ہے، کیونکہ ہم پہلے ہی جانتے ہیں کہ سب سے بڑا عنصر (ہلک) بالکل صحیح پوزیشن میں ہے: تو پروگرام میں دو لوپس ہونے چاہئیں۔ زیادہ وضاحت کے لیے، اس سے پہلے کہ ہم پروگرام کے کوڈ کا جائزہ لیں، آپ اس لنک پر ببل کی ترتیب کے کام کرنے کا ایک تصور دیکھ سکتے ہیں: ببل کی ترتیب کے کام کرنے کا تصور

جاوا میں بلبلے کی ترتیب کا نفاذ

یہ ظاہر کرنے کے لیے کہ جاوا میں چھانٹنا کس طرح کام کرتا ہے، پروگرام کوڈ یہ ہے:

• 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 بھی ہو سکتی ہے - یہ صورت ہے اگر ڈیٹا کو ابتدائی طور پر الٹ ترتیب میں ترتیب دیا جائے۔ اس حقیقت کے باوجود کہ یہ ایک سست ترتیب دینے والا الگورتھم ہے، یہ جاننا اور سمجھنا بہت ضروری ہے کہ یہ کیسے کام کرتا ہے، اور جیسا کہ پہلے ذکر کیا گیا ہے، یہ زیادہ پیچیدہ الگورتھم کی بنیاد ہے۔ جے جی ڈی!