বাবল সর্ট হলো সবচেয়ে সহজ সর্টিং অ্যালগরিদমগুলোতে একটি যা অ্যাডজেসেন্ট এলিমেন্টগুলো তুলনা করে ডেটা সর্ট করে। সকল এলিমেন্ট ফেজ-wise তুলনা হয়। প্রথম ফেজে সবচেয়ে বড় মান শেষে চলে আসে, দ্বিতীয় ফেজে দ্বিতীয় বড় এলিমেন্ট সেকেন্ড লাস্ট পজিশনে চলে আসে এবং এভাবে পুরো লিস্ট সর্ট হয়।
বাবল সর্ট অ্যালগরিদম
int arr[5]= { 5,4,2,1,3 };
int i, j ;
ইনডেক্স i=0 থেকে i<array size পর্যন্ত ট্রাভার্স করুন
ইনডেক্স j=0 থেকে array size - i - 1 পর্যন্ত ট্রাভার্স করুন
যদি arr[i]>arr[j] হয় তবে arr[i] এবং arr[j] সোয়াপ করুন
শেষ
রিকার্সিভ বাবল সর্ট
যদি অ্যারে লেন্থ ১ হয় তবে রিটার্ন করুন
অ্যারেটি একবার ট্রাভার্স করে সবচেয়ে বড় এলিমেন্টটি শেষে ফিক্স করুন
লাস্ট এলিমেন্ট বাদে বাকি অ্যারেটির জন্য স্টেপ ২ রিকার্সিভলি করুন
উদাহরণ
ইনপুট − Arr[] = { 5,7,2,3,1,4 }; length=6
আউটপুট − সর্টেড অ্যারে: 1 2 3 4 5 7
ব্যাখ্যা −
প্রথম পাস 5 7 2 3 1 4 → swap → 5 2 7 3 1 4 5 2 7 3 1 4 → swap → 5 2 3 7 1 4 5 2 3 7 1 4 → swap → 5 2 3 1 7 4 5 2 3 1 7 4 → swap → 5 2 3 1 4 7 দ্বিতীয় পাস 5 2 3 1 4 7 → swap → 2 5 3 1 4 7 2 5 3 1 4 7 → swap → 2 3 5 1 4 7 2 3 5 1 4 7 → swap → 2 3 1 5 4 7 2 3 1 5 4 7 → swap → 2 3 1 4 5 7 তৃতীয় পাস 2 3 1 4 5 7 → swap → 2 1 3 4 5 7 2 1 3 4 5 7 কোনো swap নয় চতুর্থ পাস 2 1 3 4 5 7 → swap → 1 2 3 4 5 7 1 2 3 4 5 7 এর পরের ইটারেশনগুলোতে কোনো swap নয়
ইনপুট − Arr[] = { 1, 2, 3, 3, 2 };
আউটপুট − সর্টেড অ্যারে: 1 2 2 3 3
ব্যাখ্যা −
প্রথম পাস 1 2 3 3 2 → swap → 1 2 3 2 3 1 2 3 2 3 → swap → 1 2 2 3 3 1 2 2 3 3 কোনো swap নয় এরপরের ইটারেশনগুলোতে দ্বিতীয় পাস 1 2 2 3 3 কোনো swap নয় এরপরের ইটারেশনগুলোতে
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি
বাবল সর্টের রিকার্সিভ পদ্ধতিতে, বেস কেস হচ্ছে অ্যারে লেন্থ = ১। অন্যথায় সিঙ্গল ফর লুপ ব্যবহার করে অ্যারে ট্রাভার্স করুন এবং এলিমেন্টগুলো সোয়াপ করুন।
ইনপুট অ্যারে Arr[] এবং এর এলিমেন্ট সংখ্যা হিসেবে length নিন।
Function recurbublSort(int arr[], int len) অ্যারে এবং এর লেন্থ নেয় এবং রিকার্সিভলি বাবল সর্ট ব্যবহার করে অ্যারে সর্ট করে।
একটি temp ভেরিয়েবল নিন।
যদি অ্যারে লেন্থ ১ হয় তবে void রিটার্ন করুন।
অন্যথায় সিঙ্গল ফর লুপ ব্যবহার করে অ্যারে ট্রাভার্স করুন এবং প্রতিটি এলিমেন্টের জন্য arr[i]>arr[i+1] হলে সেগুলো সোয়াপ করুন।
temp=arr[i], arr[i]=arr[i+1] এবং arr[i+1]=temp সেট করুন।
এখন length ১ কমিয়ে দিন কারণ আগের লুপটি সবচেয়ে বড় এলিমেন্টকে শেষ পজিশনে রাখেছে।
recurbublSort(arr,len) রিকার্সিভ কল করুন।
সকল কল শেষে, যখন len ১ হয়ে যাবে রিকার্সন থেকে বের হয়ে আসবে এবং অ্যারেটি সর্টেড হবে।
main-এ সর্টেড অ্যারে প্রিন্ট করুন।
উদাহরণ
#include <stdio.h> void recurbublSort(int arr[], int len){ int temp; if (len == 1){ return; } for (int i=0; i<len-1; i++){ if (arr[i] > arr[i+1]){ temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; } } len=len-1; recurbublSort(arr, len); } int main(){ int Arr[] = {21, 34, 20, 31, 78, 43, 66}; int length = sizeof(Arr)/sizeof(Arr[0]); recurbublSort(Arr, length); printf("Sorted array : "); for(int i=0;i<length;i++){ printf("%d ",Arr[i]); } return 0; }
আউটপুট
উপরোক্ত কোড রান করলে নিম্নলিখিত আউটপুট জেনারেট হবে
Sorted array: 20 21 31 34 43 66 78
