โปรแกรม C++ อัลกอริทึม Bubble Sort

Bubble Sort

Bubble Sort เป็นอัลกอริทึมการจัดเรียงแบบเปรียบเทียบ (comparison based sorting algorithm) ในอัลกอริทึมนี้ จะเปรียบเทียบองค์ประกอบที่อยู่ติดกันและสลับกันเพื่อทำลำดับที่ถูกต้อง อัลกอริทึมนี้ง่ายกว่าอัลกอริทึมอื่นๆ แต่ก็มีข้อบกพร่องบางอย่าง ไม่เหมาะสำหรับชุดข้อมูลขนาดใหญ่ ใช้เวลามากในการจัดเรียง

ความซับซ้อนของ Bubble Sort

• Time Complexity: O(n) สำหรับกรณีดีที่สุด, O(n²) สำหรับกรณีเฉลี่ยและแย่ที่สุด

• Space Complexity: O(1)

Input - รายการข้อมูลที่ไม่ได้จัดเรียง: 56 98 78 12 30 51
Output - Array after Sorting: 12 30 51 56 78 98

อัลกอริทึม

bubbleSort(array, size)

Input: อาร์เรย์ข้อมูล, และจำนวนรวมในอาร์เรย์

Output: อาร์เรย์ที่จัดเรียงแล้ว

เริ่มต้น
  for i := 0 ถึง size-1
    flag := 0
    for j := 0 ถึง size-i-1
      if array[j] > array[j+1] then
        สลับ array[j] กับ array[j+1]
        flag := 1
    if flag != 1 then break
สิ้นสุด

โค้ดตัวอย่าง

#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 << "Enter the number of elements: ";
    cin >> n;
    int arr[n];
    cout << "Enter elements:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> 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