অ্যালগরিদমঃ বাবল সর্ট

সবচেয়ে সহজ সর্টিং অ্যালগরিদম হচ্ছে Bubble Sort. সর্ট মানে হচ্ছে সাজানো। যেমন আমাদের কাছে কিছু এলোমেলো সংখ্যা রয়েছে। আমরা চাচ্ছি যেগুলোকে ছোট থেকে বড় আকারে সাজাতে। এ সাজানো বড় থেকে ছোট হতে পারে বা ছোট থেকে বড় হতে পারে। ইংরেজিতে যাকে বলে Sorting। এই সাজানোর আইডিয়াটা অনেক সহজ মনে হলেও বাস্তব জীবনে এর অনেক ব্যবহার রয়েছে।
সর্টিং এর জন্য বাবল সর্ট করে কি, প্রথমে প্রথম দুইটা সংখ্যার মধ্যে তুলনা করে। তুলনা করে দেখে কোন নাম্বারটা ছোট, কোনটা বড়। আমরা যদি ছোট থেকে বড়তে সাজাতে চাই, তাহলে যদি প্রথমটা থেকে দ্বিতীয়টা ছোট হয়, তাহলে প্রথম সংখ্যার জায়গায় দ্বিতীয়টা বসায়। দ্বিতীয় সংখ্যার জায়গায় প্রথম সংখ্যা বসায়। এরপর দ্বিতীয় সংখ্যার সাথে তৃতীয় সংখ্যার তুলনা করে। তৃতীয়টার সাথে সাথে চতুর্থ সংখ্যা, এভাবে শেষটা পর্যন্ত।

এভাবে একবার শেষ পর্যন্ত গেলে আমরা একেবারে শেষের নাম্বারটি সবচেয়ে বড় নাম্বার পেয়ে যাই। এভাবে দ্বিতীয়বার আবার প্রথম থেকে শুরু করে। দ্বিতীয়বার শেষে দুইটা সবচেয়ে বড় নাম্বার পেয়ে যাই। আমাদের কাছে যত গুলো নাম্বার রয়েছে, তত বার নাম্বার গুলো তুলনা করার পর আমরা সর্টেড বা সাজানো নাম্বার পেয়ে যাবো। অ্যালগরিদমটার সুডোকোডটা এমনঃ

for i = (n - 1) to 1
      for j = 0 to (i - 1)      
         if list[j] > list[j+1] then
            swap( list[j], list[j+1] )
   

ধরি আমাদের কাছে রয়েছেঃ 4, 8, 2, 7, 1। আমরা এই নাম্বার গুলোকে ছোট থেকে বড় আকারে সাজাবো।

4

8

2

7

1

প্রথমবার 4 এবং 8 এর মধ্যে তুলনা করবে। যেহেতু 4 থেকে 8 বড়, তাই কোন swap বা জায়গা বদল হবে না।

4

8

2

7

1

দ্বিতীয় বার 8 এবং 2 এর মধ্যে তুলনা হবে। যেহেতু 8 থেকে 2 ছোট, তাই এই সংখ্যা দুইটা জায়গা বদল করবে।

4

2

8

7

1

এরপরের বার 8 এর সাথে 7 এর তুলনা হবে। যেহেতু 8 থেকে 7 ছোট, তাই এরা জায়গা বদল করবে।

4

2

7

8

1

এবার 8 এবং 1 এর মধ্যে তুলনা হবে। যেহেতু 8 থেকে 1 ছোট, তাই এরা জায়গা বদল করবে।

4

2

7

1

8

এই মুহুর্তে 8 হচ্ছে সবচেয়ে বড় নাম্বার। এবং এটি একেবারে শেষে রয়েছে। মানে আমরা সবচেয়ে বড় সংখ্যাটি পেয়ে গিয়েছি। এরপর আবার শুরু থেকে একই ভাবে তুলনা করা হবে। এবং আমরা 8 এর পরের সবচেয়ে বড় সংখ্যা পেয়ে যাবো। একসময় আমাদের এলোমেলো নাম্বার গুলো সাজানো অবস্থায় পাবো।

বাবল সর্ট সহজ। কিন্তু অনেক স্লো। প্রথম বার আমরা সংখ্যা গুলোর মধ্যে তুলনা করি (n – 1) বার, দ্বিতীয়বার (n – 2) বার … এভাবে টোটালঃ (n – 1) + (n – 2) + …. + 2 + 1 বার।

আমরা সিরিজের অংক গুলো করেছি। মনে পড়ে না? এ সিরিজটির যোগফলঃ n(n-1)/2 যা এভাবেও লিখতে পারিঃ n^2 / 2 – n/2।

n যখন অনেক বড় একটা সংখ্যা হয়, তখন আমরা দুই দিয়ে ভাগ করা এবং n/2 বাদ দিতে পারি। তখন অ্যালগরিদমটির কমপ্লেক্সিটি দাঁড়ায়ঃ O(n^2)

নিজে নিজে এবার এই অ্যালগরিদমটি ইমপ্লিমেন্ট করার চেষ্টা করুন। না পারলে নিচের কোড দেখতে পারেন। সি প্রোগ্রামিং এ বাবল সর্ট এর ইমপ্লিমেন্টেশনঃ

#include<stdio.h>


void bubble_sort(int[], int);

void main()
{
   int list[] = {4,8,2,7,1};

   bubble_sort(list, 5); // passing the list and total number to sort
}

void bubble_sort(int list[], int n) {
   int i, j, k, temp;


   for (i = 1; i < n; i++) {
      for (j = 0; j < n - i; j++) 
            { if (list[j] > list[j + 1]) {
            temp = list[j];
            list[j] = list[j + 1];
            list[j + 1] = temp;
         }
      }
   }



    printf("Sorted list: \n", i);

      for (k = 0; k < n; k++) {
         printf("%d \n", list[k]);
      }

}

বাবল সর্টের এনিমেশনঃ

এ ছাড়া visualgo.net তেও বাবল সর্ট কিভাবে কাজ করে, কোড কিভাবে কাজ করে তা সম্পর্কে বিস্তারত এনিমেশন আকারে দেখা যাবে।