সর্টিং মানেই যে কোন কিছু সাজানো, তা আমরা কম বেশি সবাই জানি। কম্পিউটার সায়েন্সের একটি গুরুত্বপূর্ণ বিষয় হচ্ছে অ্যালগরিদম, আর এই অ্যালগরিদমের মধ্যে সর্টিং অনেক গুরুত্বপূর্ণ একটি অংশ।
যতগুলো সর্টিং অ্যালগরিদম আছে, তার মধ্যে আমাদের কাছে সিলেকশন সর্টিং সহজ মনে হলেও, অনেকের কাছেই এই বাবল সর্ট (Bubble Sort) অনেক সহজ মনে হয়। আসলে সহজ মনে হবারই কথা, কেননা বাবল সর্ট অ্যালগরিদম আসলেই অনেক সহজ একটি সর্টিং অ্যালগরিদম।
বাবল সর্ট অ্যালগরিদম আমার কাছে বেশ মজা লাগে। তুমি প্রথম থেকে শেষ পর্যন্ত পাশাপাশি দুটি দুটি করে সংখ্যা নিতে থাকো, যদি দেখো আগের সংখ্যা পরের সংখ্যা থেকে বোড়, তাহলে অদলবদল করো। এই কাজ তোমাকে n সংখ্যক বার করতে হবে, কেননা বাবল সর্ট অ্যালগরিদম কিন্তু Ο(n2) সময় লাগাবে।
বাবল সর্ট অ্যালগরিদমে Ο(n2) সময় লাগে, এর কারণ হচ্ছে প্রথম বার যখন তুমি বাম থেকে ডানে যাবে, তখন সবচেয়ে বড়টি অবশয়ই একদম ডান মাথায় গিয়ে পৌঁছাবে। পরের বার দ্বিতীয় বড়টি ঠিক জায়গায় যাবে, এভাবে প্রতিবার একোটি একোটি করে সংখ্যা সঠিক স্থানে যাবে। তাই n বার এই কাজ করলে সব সংখ্যা সঠিক জায়গায় চলে যাবে।
বাবল সর্ট কিভাবে কাজ করে?
বাবল সর্ট অ্যালগরিদম কিভাবে কাজ করে তা বোঝার জন্য চলো প্রথমেই একোতি আনসর্টেড অ্যারে নেওয়া যাক। যাহেতু বাবল সর্ট Ο(n2) সময় নেই, তাই চেস্টা করবো যত ছোট বা কম ডেটা নেওয়া যায়।
বাবল সর্ট শুরু হয় প্রথম দুটি আইতেমের মধ্যে তুলনার মাধ্যমে। আর এই তুলনার মাধ্যমে খুজে বের করা হয় সব থেকে বড় আইটেম।
আমাদের নেওয়া অ্যারেতে শুরুতেই আছে ১৪ এবং ৩৩। যেহেতু ৩৩, ১৪ থেকে বড় তাই এখানে আগে থেকেই সর্টেড আছে, অর্থাৎ কোন পরিবর্তন হবে না। এখন আমাদেরকে ৩৩ এবং ২৭ এর মধ্যে তুলনা করে দকেহতে হবে কে বড়, আর কে ছোট।
এখানে আমরা দেখছি যে, ২৭ থেকে ৩৩ বড়, আর এই কারনেই ভ্যালু দুটি অদলবদল করতে হবে।
অদলবদলের পর আমাদের অ্যারে দেখতে হবে এমনঃ
এবার আমরা যদি ৩৩ এবং ৩৫ এর মধ্যে তুলনা করি, তাহলে দকেহব যে এরা আগে থেকেই সর্টেড আছে, কেননা ৩৫ তো ৩৩ থেকে বড়ই।
তারপর আবার আমরা পরের দুটি ভ্যালু এর মধ্যে তুলনা করবো, আর এক্ষেত্রে আমার ভ্যালু হচ্ছে ১০ এবং ৩৫।
আমরা সবাই জানি যে ৩৫ থেকে ১০ অনেক ছোট একোটি সংখ্যা, এর মানে সংখ্যা দুটি আমাদের এই অ্যারেতে সর্টেড নেই।
এখন বাবল সর্টের নিয়ম অনুযায়ী ভ্যালু দুটির অবস্থান অদলবদল করতে হবে, মানে ১০ কে নিয়ে আসতে হবে ৩৫ এর স্থানে। এভাবে আমাদের প্রথম ধাপ শেষ করার পর অ্যারে দেখতে হবে অনেকটা নিচের মতঃ
এবার তোমাকে আবার প্রথম থেকে শুরু করে দ্বিতীয় ধাপ কমপ্লিট করতে হবে, আর তখন আমাদের অ্যারে হবে এই রকমঃ
তুমি খেয়াল করেছ কি না জানি না। আমরা প্রতিবার বাবল সর্ট অ্যাপ্লাই করার পর, যে কোন একটি সংখ্যা সবার শেষে চলে যাচ্ছে। অর্থাৎ শুরুর দিকে ছোট সংখ্যা গুলো আনসর্টেড থাকলেও শেষের দিকে বোড় সংখ্যা গুলো কিন্তু ঠিকই সর্টেড আছে।
এবার আবারো আমরা তৃতীয় বারের জন্য বাবল সর্ট অ্যাপ্লাই করবো, কেননা আমাদের অ্যারে এখনো পুরোপুরি সর্টেড হয়নি।
এভাবে একোটির পর একটি সর্ট করার পর যখন আর অদলবদল করার জায়গা থাকবে না, তখন আমাদের অ্যারে দেখবে হবে নিচের মতঃ
এখানে মনে রাখতে হবে যে, আমরা বাবল সর্ট ততক্ষন চালাতে থাকবো, যতক্ষন পুরপুরি সর্তেড লিস্ট পাবো।
আশাকরি বাবল সর্ত এখন তোমার কাছে অন্যদের মতই অনেক সহজ মনে হচ্ছে। তবে আমার কাছে কিন্তু ঐ সিলেকশন সর্ট অ্যালগরিদমই সহজ লাগে। 🙂
আচ্ছা, এবার তাহলে বাবল সর্ট অ্যালগরিদম দেখে চেষ্টা ক্র পুরোপুরি বুঝেছো কি না?
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
বাবল সর্ট তুমি চাইলে যে কোন ল্যাঙ্গুয়েজ দিয়েই ইমপ্লিমেন্ট করতে পারো, কেননা এটা ইমপ্লিমেন্ট করা খুব সহজ। নিচে যে কোড দিয়েছি, তুমি চাইলে এই কোডে কিছু অপটিমাইজেশন করতে পারো। যেমনঃ এমন হতে পারে যে n বারের আগেই অ্যারেটি সর্টেড হয়ে গেছে, সে ক্ষেত্রে তুমি আগেই লু থেকে বের হয়ে যেতে পারো।
আবার প্রতিবার তোমার সব জোড় সংখ্যা যাচাই করার দরকার নেই, কারণ i সংখ্যকবার চললে তুমি জানবে যে i টি সংখ্যা ঠিক জায়গায় চলে গেছে। তুমি এভাবে কিছু অপটিমাইজেশন করতে পারো, কিন্তু যতই অপটিমাইজেশন করো কেন, এই অ্যালগরিদমের worst কেইস এ Ο(n2) সময় লাগবেই। আচ্ছা তোমরা কি কেউ সেই worst কেইস্টি বের করতে পারবে?
সহজ কোডঃ
for(i=1; i<=n; i++)
{
for (j=1; j num[j])
{
temp=num[j];
num[j] = num[j+1];
num[j+1] = temp;
}
}
সি দিয়ে বাবল সর্ট ইমপ্লিমেন্টশনের সম্পূর্ণ কোডঃ
// C program for implementation of Bubble sort #includevoid swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; } // A function to implement bubble sort void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n-1; i++) // Last i elements are already in place for (j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); } /* Function to print an array */ void printArray(int arr[], int size) { for (int i=0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } // Driver program to test above functions int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, n); printf("Sorted array: \n"); printArray(arr, n); return 0; }
আউটপুরঃ Sorted array: 11 12 22 25 34 64 90
পাইথন দিয়ে বাবল সর্ট ইমপ্লিমেন্টশনের সম্পূর্ণ কোডঃ
# Python program for implementation of Bubble Sort
def bubbleSort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
print ("%d" %arr[i]),
আউটপুটঃ Sorted array: 11 12 22 25 34 64 90
জাভাস্ক্রিপ্ট দিয়ে বাবল সর্ট ইমপ্লিমেন্টশনের সম্পূর্ণ কোডঃ
var arr = [5,6,3,1,2,4];
bubbleSortAlgo(arr);
function bubbleSortAlgo(arr){
for(var i=0;iarr[j+1]){
var tempValue= arr[j];
arr[j]=arr[j+1];
arr[j+1]=tempValue;
flag=true;
}
}
if(flag==false)
break;
}
console.log("Sorted array: ");
console.log(arr);
}
আউটপুটঃ Sorted array: 1,2,3,4,5,6
আশাকরি বাবল সর্ট অ্যালগরিদম কি, কিভাবে কাজ করে, কিভাবে ইমপ্লিমেন্ট করতে হয়, তা তুমি ভালো করেই বুঝেছো। আর যদি না বুঝো তবে পুরো লেখা আরো কএয়কবার পড়ো, বিশেষ করে উদাহরণের অংশটুকু।
তুমি যদি ইনসার্শন সর্টিং ভালো করে বুঝতে চাও, তাহলে আমার ইনসার্শন সর্ট পোস্ট পড়তে পারো।