বাবল সর্ট (Bubble Sort)

বাবল সর্ট একটি কমপ্যারিজন-বেসড সর্টিং অ্যালগরিদম। এই অ্যালগরিদমে অপরিচিত এলিমেন্টগুলো তুলনা করা হয় এবং সঠিক সিকোয়েন্স बनाने জন্য সোয়াপ করা হয়। এই অ্যালগরিদম অন্যান্য অ্যালগরিদমের চেয়ে সহজ, কিন্তু এর কিছু ড্রব্যাকও রয়েছে। এই অ্যালগরিদম বড় ডেটা সেটের জন্য উপযুক্ত নয়। সর্টিং টাস্ক সমাধান করতে এটি অনেক সময় নেয়।

বাবল সর্ট টেকনিকের কমপ্লেক্সিটি

• টাইম কমপ্লেক্সিটি: বেস্ট কেসে O(n), এভারেজ ও ওয়ার্স্ট কেসে O(n²)
• স্পেস কমপ্লেক্সিটি: O(1)

ইনপুট এবং আউটপুট

Input: A list of unsorted data: 56 98 78 12 30 51
Output: Array after Sorting: 12 30 51 56 78 98

অ্যালগরিদম

bubbleSort(array, size)

ইনপুট - একটি ডেটা অ্যারে, এবং অ্যারেতে মোট সংখ্যা

আউটপুট - সোর্টেড অ্যারে

Begin
    for i := 0 to size-1 do
        flag := 0;
        for j:= 0 to size - i - 1 do
            if array[j] > array[j+1] then
                swap array[j] with array[j+1]
                flag := 1
            done
        if flag ≠ 1 then
            break the loop.
        done
End

উদাহরণ

#include 
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
    int temp;
    temp = a;
    a = b;
    b = temp;
}
void display(int *array, int size) {
    for(int i = 0; i array[j+1]) { //when the current item is bigger than next
                swapping(array[j], array[j+1]);
                swaps = 1; //set swap flag
            }
        }
        if(!swaps)
            break; // No swap in this pass, so array is sorted
    }
}
int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n]; //create an array with given number of elements
    cout << "Enter elements:" << endl;
    for(int i = 0; i> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    bubbleSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

আউটপুট

Enter the number of elements: 6
Enter elements:
56 98 78 12 30 51
Array before Sorting: 56 98 78 12 30 51
Array after Sorting: 12 30 51 56 78 98