বাবল সর্ট (Bubble Sort) একটি কমপেরিজন-ভিত্তিক সোর্টিং অ্যালগরিদম। এই অ্যালগরিদমে সন্নিহিত এলিমেন্টগুলো তুলনা করা হয় এবং সঠিক সিকোয়েন্স बनाने সোয়্যাপ করা হয়। এই অ্যালগরিদম অন্য অ্যালগরিদমের চেয়ে সহজ, কিন্তু এর কিছু ড্রব্যাক ও আছে। বড় ডেটা সেটের জন্য এটি উপযোগী নয়। সোর্টিং টাস্ক সমাধান করতে এতে অনেক সময় লাগে।
বাবল সর্ট টেকনিকের জটিলতা
সময় জটিলতা: বেস্ট কেসে O(n), গড় এবং ওasst কেসে O(n²)
স্পেস জটিলতা: O(1)
ইনপুট − একটি আনসর্টেড ডেটা লিস্ট: 56 98 78 12 30 51 আউটপুট − সর্টিংয়ের পর অ্যারে: 12 30 51 56 78 98
অ্যালগরিদম
bubbleSort(array, size)
ইনপুট: একটি ডেটা অ্যারে, এবং অ্যারেতে মোট সংখ্যা
আউটপুট: সর্টেড অ্যারে
শুরু
i := 0 থেকে size-1 পর্যন্ত
flag := 0
j := 0 থেকে size-i-1 পর্যন্ত
যদি array[j] > array[j+1] হয় তবে
array[j] এবং array[j+1] সোয়্যাপ করুন
flag := 1
শেষ
শেষ
যদি flag ≠ 1 হয় তবে
লুপ ব্রেক করুন
শেষ
শেষ
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
void swapping(int &a, int &b) {
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
void bubbleSort(int *array, int size) {
for(int i = 0; i < size; i++) {
int swaps = 0;
for(int j = 0; j < size-i-1; j++) {
if(array[j] > array[j+1]) {
swapping(array[j], array[j+1]);
swaps = 1;
}
}
if(!swaps)
break;
}
}
int main() {
int n;
cout << "এলিমেন্টের সংখ্যা দিন: ";
cin >> n;
int arr[n];
cout << "এলিমেন্টগুলো দিন:" << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "সর্টিংয়ের আগে অ্যারে: ";
display(arr, n);
bubbleSort(arr, n);
cout << "সর্টিংয়ের পর অ্যারে: ";
display(arr, n);
}
আউটপুট
এলিমেন্টের সংখ্যা দিন: 6 এলিমেন্টগুলো দিন: 56 98 78 12 30 51 সর্টিংয়ের আগে অ্যারে: 56 98 78 12 30 51 সর্টিংয়ের পর অ্যারে: 12 30 51 56 78 98
