বাবল সর্ট অ্যালগরিদম – Bubble Sort Algorithm

Post updated on 28th November, 2016 at 01:36 pm

ধরো, তোমাকে ১০০০, ৫০০, ১০০, ৫০, ২০, ১০ ইত্যাদি টাকার কিছু নোট দিলাম। বললাম সবগুলো নোট ও সিকি-আধুলি যা দেয়া হয়েছে সবগুলোকে ছোট থেকে বড় আকারে সাজাও। তখন তুমি কী করবে?

প্রথমে দেখবে সবচেয়ে বড় নোটটা কত? এটাকে সবার শেষে পাঠাবে। অর্থাৎ ১০০০ টাকার নোটটা সবার শেষে চলে যাবে। এরপর এই ১০০০ টাকার নোট বাদে যেই নোটগুলো তোমার হাতে আছে এগুলোর মধ্যে সবচেয়ে বড়টাকে ১০০০ টাকার নোটের আগে স্থান দিবে। ধর সেই নোটটা ৫০০ টাকার। তাহলে তুমি দুইটা ধাপে দুইটা নোটকে জায়গা মত প্লেস করতে পেরেছ। প্রথম ধাপের কাজ শেষ হবার পর তোমার টাকার বান্ডিলের সর্বশেষ নোটটি (element-টি) ঠিক ঠাক মত সাজানো হয়ে গেছে (sorted)। দ্বিতীয় ধাপে ৫০০ টাকাকে যখন ১০০০ এর আগে প্লেস করলে তখন তোমার টাকার বান্ডিলের সর্বশেষ দুটি ইলিমেন্ট সজ্জিত বা sorted হয়ে গেছে। এভাবে প্রতিটি ধাপে একটি করে নোট তার নিজ পজিশনে বসে যাবে। আর একটা নোট তার নিজ পজিশনে বসার পর সেটা থেকে শেষ পর্যন্ত সবগুলো নোটই সাজানো অবস্থায় থাকে (ধরো, …, ১০০, ৫০০, ১০০০)। তাই পরের ধাপে বাকি যে কটা নোট সাজানো হয় নি সেগুলোর থেকে সবচেয়ে বড়টাকে তার নিজ পজিশনে বসাতে হবে। এভাবে সাজাতে সাজাতে যদি কোন একটা ধাপে এমন পাওয়া যায় যে কোন নোটকে সাজানোর জন্য তাকে সামনে বা পিছনে নিতে হচ্ছে না তাহলে বুঝতে হবে তোমার সব নোটগুলো সাজানো হয়ে গেছে। এভাবে তোমার হাতে যদি ১০টা নোট থাকে তাহলে সর্বোচ্চ ৯ টা ধাপে তুমি সবগুলো নোটকে সাজিয়ে ফেলা যাবে।

• কাউন্টিং সর্ট – সবচেয়ে সহজ সর্টিং অ্যালগরিদম

এই নোট সাজানোর জটিলতম (!) কাজটা তুমি জীবনে কখনো না কখনো করেছ। যদি করে থাক তার মানে তুমি অলরেডি বাবল সর্ট জানো। উপরের যেই পদ্ধতিতে নোটগুলোকে সাজানো হল কম্পিউটার সায়েন্সে এই পদ্ধতির নামই বাবল সর্ট এলগরিদম। Bubble Sort এর আরেক নাম Sinking Sort. উপরের স্টেপগুলোই কোড আকারে লিখা যায় এভাবেঃ

#include<stdio.h>

int main()
{
    int arr[10], i, j, temp, number_of_elements = 5;
    bool isSwapped;

    printf("Input %d numbers to an Array: ", number_of_elements);
    for(i=0; i<number_of_elements; i++)
    {
        scanf("%d", &arr[i]);
    }

    //Start Bubble Sort
    for(i=0; i<number_of_elements-1; i++)
    {
        isSwapped = false;

        for(j=0; j<number_of_elements-1-i; j++)
        {
            if(arr[j]>arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;

                isSwapped = true;
            }
        }

        //No element is swapped in this step. That means the array already sorted
        //So no need to run another step. That's why break the Loop
        if(isSwapped == false)
            break;
    }

    //Print sorted Array
    for(i=0; i<number_of_elements; i++)
        printf("%d ", arr[i]);


    return 0;
}

অ্যারেতে ইনপুট নেয়া ডেটাগুলোর থেকে প্রথম ডেটাকে অর্থাৎ arr[0] কে তার পাশের ডেটার সাথে arr[1] তুলনা করা হবে। যদি arr[0] এর মান arr[1] এর চেয়ে ছোট হয় তাহলে আমাদের কিছুই করার দরকার নাই। কিন্তু বড় হয়ে গেলে কী করতে হবে? আমরা চাচ্ছি অ্যারের সংখ্যাগুলোকে ছোট থেকে বড় আকারে সাজাতে। তাই প্রথমটা বড় হলে তাদের দুইজনকে swap করে দিতে হবে।

• দুটি সংখ্যা সোয়াপ (SWAP) করার তিনটি পদ্ধতি

১৫ নাম্বার লাইনে শুরু হওয়া লুপের সাহায্যে কনট্রোল করা হচ্ছে এই অ্যারেটা সর্ট করতে কতটা স্টেপে কাজ করতে হবে তা। আর তার ভিতরের ১৯ নাম্বার লাইনের লুপের সাহায্যে কন্ট্রোল করা হচ্ছে অ্যারের কোন পজিশন পর্যন্ত লুপ ঘুরিয়ে সোয়াপ করার কাজটা করতে হবে সেটা। প্রথম লুপটা ঘুরার কন্ডিশন (i<number_of_elements-1)। এর মানে হচ্ছে number_of_elements এর মান ৫ হলে লুপটা ঘুরবে ৪ বার। লুপ ভ্যারিয়েবল i এর ইনিশিয়ালাইজেশন হয়েছিল 0 দিয়ে। তাই i এর মান 3 থাকা পর্যন্ত এই কনডিশন সত্য হবে।

দ্বিতীয় লুপের ভিতরে প্রতিবার অ্যারের শুরু থেকে প্রতিটা ইলিমেন্ট চেক করার কাজ করা হয়েছে if(arr[j]>arr[j+1]) দিয়ে। এই লুপটার কনডিশনে বলা আছে (j<number_of_elements-1-i). যদি (j<number_of_elements-1) বলা থাকত তাহলে বুঝতেই পারছো লুপটা প্রথম লুপের মত ৪ বারই ঘুরবে। আর প্রতি বারই অ্যারের সবগুলো ইন্ডেক্সকেই চেক করতে থাকবে। কিন্তু আমাদের প্রতিবার চেক করার দরকার নাই। কারণ প্রতিটা স্টেপের কাজ শেষে অ্যারের শেষ থেকে একটা করে ইন্ডেক্সের মান সর্টেড হয়ে যায়। প্রথম স্টেপ শেষে অ্যারের arr[4] এর মানটা সর্টেড হয়ে যায়। দ্বিতীয় স্টেপ শেষে অ্যারের arr[3] এর মান সর্টেড হয়ে যায়। ৩ নাম্বার স্টেপ শেষে তার মানে অ্যারের শেষ ৩টা ইন্ডেক্স এর মান সর্টেড হয়ে যাবে। তাহলে চতুর্থ স্টেপে আমি অ্যারের কোন ইন্ডেক্সগুলোর মধ্যে চেক করবো? শেষ ৩টা ইন্ডেক্স বাদ দিয়ে প্রথম ইন্ডেক্সগুলা চেক করব, তাই না? কারণ শেষ ৩টা ইন্ডেক্স তো সর্টেড হয়েই আছে। অতএব বলা যায়, অ্যারের শুরু থেকে যত নাম্বার স্টেপের কাজ হচ্ছে তার আগ পর্যন্ত চেকিং এর কাজ হবে। প্রথম লুপের লুপ ভ্যারিয়েবল হচ্ছে i. এটা দিয়েই স্টেপ নাম্বার বুঝানো হচ্ছে। তাই দ্বিতীয় লুপের কনডিশনে (j<number_of_elements-1-i) বলে স্টেপ নাম্বার বাদ দেয়া হয়েছে।

৩৩ নাম্বার লাইনে if(isSwapped == false) এই কনডিশনটা চেক করা হয়েছে। দ্বিতীয় লুপের ভিতরে দেখ, যদি একটা স্টেপের মধ্যে দুইটা ইন্ডেক্সের ভ্যালু সোয়াপ হয় অর্থাৎ if(arr[j]>arr[j+1]) সত্য হয় তাহলে নাম্বার দুটি সোয়াপ করার পরে isSwapped = true; করে দেয়া হয়েছে। অর্থাৎ আমরা একটা ট্র্যাক রাখছি যে এই স্টেপে অন্তত একবার হলেও দুটি সংখ্যার মধ্যে সোয়াপ হয়েছে কিনা। যদি সোয়াপ হয় তাহলেও পরের স্টেপে আবারো চেক করা লাগবে কোন সংখ্যা সোয়াপ হওয়া ছাড়া আছে কিনা। কিন্তু যদি কোন একটা স্টেপে একবারও সোয়াপ না হয় তাহলে isSwapped এর মান false থাকবে। কেননা ঐ স্টেপের শুরুতেই ১৭ নাম্বার লাইনে এর মান false ছিল। যদি কোন স্টেপে একবারও সোয়াপ না হয় তাহলে বুঝতে হবে Array-টা সর্টেড হয়ে গেছে। যদি সর্টেড হয়েই যায় তাহলে outer loop (স্টেপ ক্যালকুলেট করার লুপ) break করে সর্টিং এর কাজ শেষ করতে হবে। এতে অনেকগুলো স্টেপে অযথা লুপ ঘুরানো থেকে বাঁচা যায়। অনেক সময় সেভ হয়। নিচের কোডে প্রতিটা স্টেপে কিভাবে কাজ হচ্ছে সেটা দেখতে পারবে। কোডটা নেয়া হয়েছে Tutorials Point থেকে।

#include <stdio.h>
#include <stdbool.h>

#define MAX 10

//int list[MAX] = {1,2,3,4,5,6,7,8,9,10};
int list[MAX] = {1,8,4,6,0,3,5,2,7,9};

void display(){
   int i;
   printf("[");

   // navigate through all items
   for(i = 0; i < MAX; i++){
      printf("%d ",list[i]);
   }

   printf("]\n");
}

void bubbleSort() {
   int temp;
   int i,j;

   bool swapped = false;

   // loop through all numbers
   for(i = 0; i < MAX-1; i++) {
      swapped = false;

      // loop through numbers falling ahead
      for(j = 0; j < MAX-1-i; j++) {
         printf("     Items compared: [ %d, %d ] ", list[j],list[j+1]);

         // check if next number is lesser than current no
         //   swap the numbers.
         //  (Bubble up the highest number)

         if(list[j] > list[j+1]) {
            temp = list[j];
            list[j] = list[j+1];
            list[j+1] = temp;

            swapped = true;
            printf(" => swapped [%d, %d]\n",list[j],list[j+1]);
         }else {
            printf(" => not swapped\n");
         }

      }

      // if no number was swapped that means
      //   array is sorted now, break the loop.
        if(!swapped) {
            break;
        }

      printf("Iteration %d#: ",(i+1));
      display();
   }

}

main(){
   printf("Input Array: ");
   display();
   printf("\n");

   bubbleSort();
   printf("\nOutput Array: ");
   display();
}

উপরের কোডের ৭ নাম্বার লাইনকে কমেন্ট করে ৬ নাম্বার লাইনের কমেন্ট উঠিয়ে দিয়ে রান করো। দেখবে একটা iteration হয়েছে বা একটা স্টেপেই সর্টিং এর কাজ শেষ হয়েছে। এই কোডেই এবার ৫৪, ৫৫, ৫৬ নাম্বার লাইনটাকে কমেন্ট করে রান করো। দেখ ৯ টা ইটারেশন হয়েছে। বুঝতেই পারছো লুপ ব্রেক করার কারণে আমাদের প্রোগ্রাম কতটা ইফিসিয়েন্ট হয়েছে!

অল্প সংখ্যক ডেটাকে সর্ট করার জন্য বাবল সর্ট ব্যবহার করা যেতে পারে। অনেক বেশি ডেটাকে সর্ট করতে এ অ্যালগরিদম ব্যবহার করলে কাজটা অনেল স্লো হয়ে যায়। কারণ এই অ্যালগরিদমের কমপ্লেক্সিটি O(n²).

Bubble Sort Algorithm এর visualization দেখতে পারো এখান থেকে।

কোথাও অস্পষ্টতা থাকলে বা ভুল চোখে পড়লে কমেন্ট করে জানাবেন প্লিজ। ধন্যবাদ এত বড় পোস্টটা পড়ার জন্য। 🙂