বাবল সর্ট (Bubble sort) একটি সহজ সর্টিং অ্যালগরিদম যা আমরা ব্যবহার করি যখন কোন array বা লিস্ট সর্ট করতে হয়। এই অ্যালগরিদমটি টাইম কমপ্লেক্সিটিতে অ্যারেকে সর্ট করে দিতে পারে। ধরা যাক আমাদের একটি অ্যারে arr[]={8,5,3,1,4,7,9} দেয়া হয়েছে। আমাদেরকে বাবল সর্টের মাধ্যমে একে সাজিয়ে {1,3,4,5,7,8,9} করতে হবে (ছোট থেকে বড় সাজাতে হবে)। তাহলে চলুন শুরু করা যাক।
Bubble sort Bangla tutorial
সর্টিং (Sorting) যার বাংলা হলো সাজানো। সর্টিং হলো একটি পদ্ধতি যার মাধ্যমে আমরা একটি অ্যারে বা লিস্টকে নির্দিষ্ট শর্ত মোতাবেক সাজাতে পারি। এই শর্ত আমাদের সমস্যা অনুযায়ী বিভিন্ন হতে পারে। যেমন: অ্যারের সমস্ত উপাদান ছোট থেকে বড় (Ascending) বা সমস্ত উপাদান বড় থেকে ছোট (Descending) থাকবে।
বাবল সর্ট (bubble sort) যারা শিখতে এসেছেন অনেকেরই হয়ত বাবল সর্ট-ই প্রথম সর্টিং অ্যালগরিদম। আজকে এই লিখায় আমরা বাবল সর্ট নিয়ে বিস্তারিত জানবো। আমরা অ্যালগরিদমটি ভালো করে বুঝতে অ্যানিমেশনের সহায়তা নিবো। কেন আমরা একে বাবল সর্ট বলছি?
কেন আমরা এর নাম বাবল সর্ট বলছি?
প্রথমেই, আমরা জেনে নিবো এই অ্যালগরিদমকে কেন বাবল সর্ট বলছি। আপনারা সবাই পানির বাবল চিনেন। একাধিক পানির বাবল যখন একসাথে পাত্রের তলা থেকে উপরে উঠতে থাকে তখন দেখা যায় সবথেকে বড় বাবল সবার আগে উপরে উঠে আসে। এর পর তার থেকে ছোট যে থাকে সে। তেমনি বাবল সর্টে সবথেকে বড় ইলিমেন্ট (ছোট থেকে বড় ক্রমে সাজানোর ক্ষেত্রে) সবার আগে অ্যারের শেষে চলে যায়। নিচের ভিজুয়ালাইজেশনটি দেখলেই বুঝবেন।
এবার চলুন শুরু করি বাবল সর্ট অ্যালগরিদম।
বাবল সর্ট অ্যালগরিদম – Bubble sort Bangla tutorial
উপরের আলোচনা থেকে আপনারা অনেকেই বুঝে গেছেন বাবল সর্ট কি। ধরা যাক আমাদেরকে একটি অ্যারে দেয়া আছে। এখানে অ্যারে সাইজ বা । এখন চলুন দেখি বাবল সর্ট অ্যালগরিদম।
- থেকে মোট বার নিচের ধাপগুলো রিপিট করতে হবে।
- থেকে শুরু করে পর্যন্ত নিচের স্টেপ গুলো রিপিট করি।
- যদি হয় (আগের ইলিমেন্ট পরেরটার থেকে বড় হয়) তবে এবং কে swap করি।
- j এর মান এক বৃদ্ধি করি।
- থেকে শুরু করে পর্যন্ত নিচের স্টেপ গুলো রিপিট করি।
পরবর্তী ধাপে যাবার আগে ভিজুয়ালাইজেশনটি দেখে আসতে পারেন। বাংলায় Bubble sort visualization.
এখন চলে আসি ব্যাখাতে। কেন আমরা প্রথম স্টেপ বার রিপিট করবো? আমরা খেয়াল করে দেখি, যখন ভেতরের লুপে এবং এর মধ্যে swap হবে তখন বড় ইলিমেন্ট এক ঘর পিছিয়ে যেয়ে ছোট ইলিমেন্টকে সামনের পজিশন দেবে, কারণ । তারমানে দাঁড়াচ্ছে যতবার ভেতরের স্টেপ রিপিট হবে ততবার একটি করে উপদান অ্যারের পেছনে তার সঠিক জায়গাতে যাবে (নিচের এনিমেশনটি দেখুন)।
এই এনিমেশনে আমরা দেখতে পাচ্ছি প্রথমবার ৮ তার সঠিক জায়গায় গিয়েছে। তারপর ৫ এভাবে।
তারমানে দাড়ায় আমরা টি ইলিমেন্টকে তার সঠিক জায়গায় নিতে চাইলে আমাদেরকে প্রথম লুপ বার রিপিট করতে হবে।
(অ্যারে আগেই সর্ট হয়ে যাবার জন্য এবং ইমেজ সাইজ কমানোর জন্য পরের স্টেপ গুলো দেখানো হয়নি)।
যেহেতু অ্যারেটির প্রতি ধাপে সব থেকে বড় ইলিমেন্ট শেষের দিকে নিজের সঠিক পজিশনে চলে যায় তাই আমরা বলতে পারি যেখানে তম ধাপে থেকে ইনডেক্স পর্যন্ত সাব-অ্যারে সর্ট হয়ে গেছে। অতএব পরবর্তী স্টেপ গুলোতে আমরা এইটুকু স্কিপ করতে পারবো। তাই আমরা বাবল সর্টকে একটু অপ্টিমাইজ করে ভেতরের লুপ বার চালাতে পারবো।
বাবল সর্ট ইমপ্লিমেন্টেশন
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <iostream> using namespace std; int main(){ int n=7; int arr[]={8,5,3,1,4,7,9}; for(int i=0;i<n;i++){// বাইরের স্টেপ ১, n বার রিপিট হবে। for(int j=0;j<n-i-1;j++){ //প্রতি স্টেপে n-i-1 থেকে n-1 পর্যন্ত সর্ট হয়ে যায়। //তাই আমরা এই স্টেপ n-i-1 এর আগে পর্যন্ত প্রসেস করবো। if(arr[j]>arr[j+1]){//যদি আগের ইলিমেন্ট পরেরটা থেকে বড় হয়। swap(arr[j],arr[j+1]);//swap এর মাধ্যমে স্থান পরিবর্তন করে দিলাম। } } } for(auto a:arr) cout<<a<<" "; return 0; } |
উপরের কোডে আমরা প্রথমে একটি অ্যারে নিয়েছি। আপনারা একটি অ্যারের ইনপুট নিয়েও কাজ করতে পারেন। এর পর আমরা একটি লুপ নিয়েছি। এই লুপটি ই অ্যালগরিদমে বর্ণিত প্রথন স্টেপ যেটা বার ঘুরবে। এখানে একেকটি স্টেপকে নির্দেশ করে।
এর পর ভেতরে আমরা আরেকটি লুপ নিয়েছি যেটা মূলত থেকে পর্যন্ত সব থেকে বড় ইলিমেন্টকে তার সঠিক জায়গায় নিয়ে যাবে।
এর ভেতরে আমরা দেখেছি arr[j]>arr[j+1] কিনা। যদি arr[j], arr[j+1] থেকে বড় হয় তবে আমরা arr[j] কে পিছিয়ে arr[j+1] এর জায়গায় এবং arr[j+1] কে arr[j] এর জায়গায় নিয়ে যাবো।
আমরা যদি বড় থেকে ছোট সাজাতাম তবে আমাদের দেখতে হত arr[j]<arr[j+1] কিনা, যদি হত তাহলে আমাদের বড় ইলিমেন্ট বা arr[j+1] কে সামনে arr[j] এর জায়গায় নিয়ে arr[j] কে arr[j+1] এর জায়গায় আনতে হত।
সব শেষে আমরা অ্যারেটিকে প্রিন্ট দিয়েছি।
Bubble sort algorithm complexity
বাবল সর্টের বাইরের লুপটি থেকে মোট বার ঘুরে এবং ভেতরের লুপ বার ঘুরবে প্রতিবার। তাহলে আমরা নিচের মত সিরিজ পাচ্ছি।
সুতরাং বাবল সর্টের টাইম কম্পেলক্সিটি ।
আজকে এই পর্যন্তই। আপনারা আরও পড়তে পারেন সর্টিং: কুইক সর্ট (Quick Sort) অ্যালগরিদম বা সর্টিং: মার্জ সর্ট (Merge Sort) অ্যালগরিদম।
বাবল সর্ট wiki.
লিখাটি কেমন লাগলো রেটিং দিয়ে জানাবেন। #happy_coding.
