বাবল সর্ট

বাবল সর্ট (ইংরেজিঃ Bubble sort) সর্টিং অ্যালগোরিদমগুলোর মধ্যে সবচেয়ে সহজ এবং ছোট অ্যালগোরিদম।

বাবল সর্ট ব্লক চিত্র

এই অ্যালগোরিদমে যে প্রক্রিয়াটি অনুসরণ করা হয় তা হল প্রথমে একটি অ্যারের উপাদান নির্দিষ্ট করে ধরে নেওয়া হয়। তারপর সেই অ্যারের উপাদানের সাথে অন্যান্য উপাদানগুলোকে তুলনা করা হয়। যদি পাশাপাশি উপাদান দুটির মধ্যে আগের উপাদানটি যদি পরেরটির চেয়ে বড় হয় (ছোট থেকে বড় ক্রমে সাজানোর জন্য) অথবা ছোট হয় (বড় থেকে ছোট ক্রমে সাজানোর জন্য) তাহলে উপাদান দুটির পারস্পরিক স্থান পরিবর্তন (swap) করা হয়। এভাবে সবগুলো উপাদান একবার করে নিয়ে যতক্ষণ পর্যন্ত উপাদানগুলোর পারস্পরিক স্থান পরিবর্তন হবে ততক্ষণ পর্যন্ত একই কাজের পুনরাবৃত্তি করা হয়।পারস্পরিক স্থান পরিবর্তন না হওয়ার মানে হল অ্যারেটির সর্টিং হয়ে গেছে।

বিশ্লেষণ

বাবল সর্ট এর উদাহরণ

মনে করি, একটি অ্যারের উপাদানগুলো যথাক্রমে "5 1 4 2 8", এবং এই উপাদানগুলোকে ছোট থেকে বড় ক্রমে সাজাতে হবে । প্রতি ধাপে, গাঢ় উপাদান গুলোর মধ্যে তুলনা করা হবে । এর জন্য তিনটি ধাপ প্রয়োজন ।

প্রথম ধাপ

( 5 1 4 2 8 ) $\to$ ( 1 5 4 2 8 ), এখানে, প্রথম দুটি উপাদানের মধ্যে তুলনা করবে, এবং যেহেতু 5 > 1 সেহেতু স্থান পরিবর্তন করবে।
( 1 5 4 2 8 ) $\to$ ( 1 4 5 2 8 ), যেহেতু 5 > 4 সেহেতু স্থান পরিবর্তন করবে.।
( 1 4 5 2 8 ) $\to$ ( 1 4 2 5 8 ), যেহেতু 5 > 2 সেহেতু স্থান পরিবর্তন করবে।
( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ), এখন, যেহেতু (8 > 5), সেহেতু স্থান পরিবর্তন করবে না।

দ্বিতীয় ধাপ

( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 )
( 1 4 2 5 8 ) $\to$ ( 1 2 4 5 8 ), যেহেতু 4 > 2 সেহেতু স্থান পরিবর্তন করবে।
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
এখন, এই উপাদানগুলো ক্রমানুসারে আছে,কিন্তু অ্যালগোরিদমটি অ্যারের উপাদানগুলো সর্ট হয়েছে বা ক্রমানুসারে আছে কি না সেটা নিশ্চিত নয়। উপাদানগুলো ক্রমানুসারে আছে সেটা নির্ধারণ করার জন্য উপাদানগুলোর স্থান পরিবর্তন না করে পুনরায় একটি পূর্ণাঙ্গ ধাপের দরকার হয় ।

তৃতীয় ধাপ

( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )

অ্যালগোরিদম

function bubble_sort (array, length) 
{
    var i, j;
    for(i from 0 to length-1)
    {
        for(j from 0 to length-1-i)					
        {
	    if (array[j] > array[j+1])
            swap(array[j], array[j+1])
        }
    }
}

সি কোড

 typedef int element[MAX];
 void bubble_sort(element t) 
 {
	int i, j, tmp;
 	for(i = 1; i < MAX; i++)
 		for(j = 0; j < MAX-i; j++)
 			if(t[j] > t[j+1])										   
			{
 				tmp = t[j+1];
 				t[j+1] = t[j];
 				t[j] = tmp;
 			}
 }