cpp-bubble-sort

readme.md

Thuật toán Sắp xếp Nổi Bọt (Bubble Sort) trong C++

Giới thiệu (10 phút)

Thuật toán sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán sắp xếp đơn giản nhất trong khoa học máy tính. Tên gọi "nổi bọt" xuất phát từ cách thức hoạt động của thuật toán - các phần tử lớn hơn "nổi" dần lên phía cuối mảng, giống như bong bóng khí nổi lên bề mặt chất lỏng.

Nguyên lý cơ bản

Thuật toán sắp xếp nổi bọt hoạt động bằng cách:

1. So sánh từng cặp phần tử liền kề trong mảng
2. Nếu chúng không theo thứ tự (ví dụ: phần tử trước lớn hơn phần tử sau khi sắp xếp tăng dần), thì đổi chỗ chúng
3. Tiếp tục quá trình này cho đến khi không cần đổi chỗ nữa - tức là mảng đã được sắp xếp

Ưu và nhược điểm

Ưu điểm:

• Dễ hiểu và triển khai
• Không cần bộ nhớ phụ (sắp xếp tại chỗ)
• Ổn định (các phần tử có giá trị bằng nhau giữ nguyên thứ tự tương đối)

Nhược điểm:

• Hiệu suất kém (độ phức tạp O(n²) trong trường hợp trung bình và tệ nhất)
• Không phù hợp với tập dữ liệu lớn

Cài đặt cơ bản (15 phút)

Cài đặt thuật toán sắp xếp nổi bọt trong C++

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        // Duyệt qua mảng
        for (int j = 0; j < n-i-1; j++) {
            // So sánh các phần tử liền kề
            if (arr[j] > arr[j+1]) {
                // Hoán đổi nếu phần tử hiện tại lớn hơn phần tử kế tiếp
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

// Hàm để in mảng
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout << "Mảng ban đầu: \n";
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    cout << "Mảng sau khi sắp xếp: \n";
    printArray(arr, n);
    
    return 0;
}

Phân tích mã

1. Vòng lặp ngoài for (int i = 0; i < n-1; i++):

   • Vòng lặp này chạy n-1 lần vì sau mỗi lần lặp, phần tử lớn nhất sẽ "nổi" lên vị trí cuối cùng chưa được sắp xếp
   • Sau mỗi lần lặp, số phần tử cần xét giảm đi 1

2. Vòng lặp trong for (int j = 0; j < n-i-1; j++):

   • Vòng lặp này so sánh các cặp phần tử liền kề
   • Chỉ cần duyệt đến phần tử thứ n-i-1 vì i phần tử cuối cùng đã được sắp xếp

3. Điều kiện if (arr[j] > arr[j+1]):

   • So sánh hai phần tử liền kề
   • Nếu phần tử trước lớn hơn phần tử sau, đổi chỗ chúng (để sắp xếp tăng dần)

Minh họa thuật toán (15 phút)

Hãy theo dõi quá trình sắp xếp mảng [5, 1, 4, 2, 8] bằng thuật toán Bubble Sort:

Lần lặp đầu tiên (i = 0):

• So sánh arr[0] = 5 > arr[1] = 1? => Đổi chỗ: [1, 5, 4, 2, 8]
• So sánh arr[1] = 5 > arr[2] = 4? => Đổi chỗ: [1, 4, 5, 2, 8]
• So sánh arr[2] = 5 > arr[3] = 2? => Đổi chỗ: [1, 4, 2, 5, 8]
• So sánh arr[3] = 5 > arr[4] = 8? => Không đổi chỗ: [1, 4, 2, 5, 8]

Lần lặp thứ hai (i = 1):

• So sánh arr[0] = 1 > arr[1] = 4? => Không đổi chỗ: [1, 4, 2, 5, 8]
• So sánh arr[1] = 4 > arr[2] = 2? => Đổi chỗ: [1, 2, 4, 5, 8]
• So sánh arr[2] = 4 > arr[3] = 5? => Không đổi chỗ: [1, 2, 4, 5, 8]

Lần lặp thứ ba (i = 2):

• So sánh arr[0] = 1 > arr[1] = 2? => Không đổi chỗ: [1, 2, 4, 5, 8]
• So sánh arr[1] = 2 > arr[2] = 4? => Không đổi chỗ: [1, 2, 4, 5, 8]

Lần lặp thứ tư (i = 3):

• So sánh arr[0] = 1 > arr[1] = 2? => Không đổi chỗ: [1, 2, 4, 5, 8]

Kết quả cuối cùng: [1, 2, 4, 5, 8]

Phân tích độ phức tạp (10 phút)

Độ phức tạp thời gian

• Trường hợp tốt nhất: O(n) - khi mảng đã được sắp xếp (nếu sử dụng cải tiến cờ hiệu)
• Trường hợp trung bình: O(n²)
• Trường hợp xấu nhất: O(n²) - khi mảng được sắp xếp ngược

Độ phức tạp không gian

• O(1) - thuật toán sắp xếp tại chỗ, chỉ cần lưu một số biến tạm thời

Cải tiến thuật toán Bubble Sort (15 phút)

Cải tiến 1: Sử dụng cờ hiệu (flag)

void improvedBubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n-1; i++) {
        swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Sử dụng hàm swap có sẵn trong C++
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        // Nếu không có swap nào trong lượt này, mảng đã được sắp xếp
        if (!swapped)
            break;
    }
}

Cải tiến này giúp tối ưu trường hợp mảng đã được sắp xếp một phần hoặc hoàn toàn. Nếu không có hoán đổi nào xảy ra trong một lần lặp, có nghĩa là mảng đã được sắp xếp và thuật toán có thể dừng sớm.

Cải tiến 2: Bubble Sort hai chiều (Cocktail Sort)

void cocktailSort(int arr[], int n) {
    bool swapped = true;
    int start = 0;
    int end = n - 1;
    
    while (swapped) {
        // Đặt lại cờ hiệu trong mỗi lần lặp
        swapped = false;
        
        // Di chuyển từ trái sang phải
        for (int i = start; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }
        
        // Nếu không có swap, mảng đã được sắp xếp
        if (!swapped)
            break;
            
        // Giảm phạm vi phía phải
        end--;
        
        // Đặt lại cờ hiệu
        swapped = false;
        
        // Di chuyển từ phải sang trái
        for (int i = end - 1; i >= start; i--) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }
        
        // Tăng phạm vi phía trái
        start++;
    }
}

Cocktail Sort là biến thể của Bubble Sort, hoạt động bằng cách di chuyển theo hai hướng. Thuật toán này giúp giảm hiện tượng "rùa" (các phần tử nhỏ ở cuối mảng di chuyển chậm về đầu mảng).

Ứng dụng thực tế (10 phút)

Mặc dù Bubble Sort không hiệu quả cho dữ liệu lớn, nhưng nó vẫn có một số ứng dụng:

1. Tình huống giáo dục: Dễ hiểu, dễ triển khai, thích hợp để giới thiệu khái niệm sắp xếp
2. Tập dữ liệu nhỏ: Với các tập dữ liệu rất nhỏ (< 10 phần tử), Bubble Sort có thể có hiệu suất hợp lý
3. Phát hiện đã sắp xếp: Phiên bản cải tiến có thể nhanh chóng xác định mảng đã được sắp xếp
4. Bộ nhớ hạn chế: Không yêu cầu bộ nhớ phụ, phù hợp với hệ thống có bộ nhớ hạn chế
5. Kiểm tra sắp xếp: Có thể được sử dụng để kiểm tra một mảng đã gần như được sắp xếp hay chưa

So sánh với các thuật toán sắp xếp khác (10 phút)

Thuật toán	Độ phức tạp thời gian TB	Độ phức tạp không gian	Ổn định	Đặc điểm
Bubble Sort	O(n²)	O(1)	Có	Đơn giản, không hiệu quả với dữ liệu lớn
Selection Sort	O(n²)	O(1)	Không	Số lần hoán đổi ít hơn Bubble Sort
Insertion Sort	O(n²)	O(1)	Có	Hiệu quả với dữ liệu gần như sắp xếp
Merge Sort	O(n log n)	O(n)	Có	Hiệu quả, nhưng cần bộ nhớ phụ
Quick Sort	O(n log n)	O(log n)	Không	Nhanh trong thực tế, nhưng tệ nhất O(n²)

Danh sách bài tập thực hành (5 phút)

1. Cài đặt thuật toán sắp xếp nổi bọt cơ bản để sắp xếp mảng số nguyên theo thứ tự tăng dần
2. Sửa đổi thuật toán để sắp xếp mảng theo thứ tự giảm dần
3. Cài đặt phiên bản cải tiến với cờ hiệu và so sánh hiệu suất với phiên bản cơ bản
4. Viết chương trình đếm số lần so sánh và hoán đổi trong quá trình sắp xếp
5. Sắp xếp mảng các chuỗi theo thứ tự bảng chữ cái
6. Tạo cấu trúc Sinh viên và sắp xếp theo điểm số
7. Cài đặt thuật toán sắp xếp nổi bọt cho một phạm vi cụ thể trong mảng
8. Viết chương trình hiển thị từng bước của quá trình sắp xếp
9. Sửa đổi thuật toán để sắp xếp số chẵn trước, số lẻ sau trong mảng
10. Cài đặt thuật toán sắp xếp Cocktail Sort và so sánh với Bubble Sort cơ bản

Tổng kết (10 phút)

Điểm chính

• Thuật toán sắp xếp nổi bọt là thuật toán sắp xếp đơn giản, hoạt động bằng cách liên tục hoán đổi các phần tử liền kề
• Độ phức tạp thời gian là O(n²) trong trường hợp trung bình và xấu nhất
• Có thể cải thiện hiệu suất bằng cờ hiệu hoặc sắp xếp hai chiều
• Thích hợp cho mục đích giáo dục, tập dữ liệu nhỏ, và khi không gian bộ nhớ hạn chế

Lưu ý quan trọng

• Không nên sử dụng Bubble Sort cho tập dữ liệu lớn
• Trong thực tế, các thuật toán như Quick Sort, Merge Sort, hoặc các thuật toán chuẩn trong thư viện thường được sử dụng
• Hiểu thuật toán Bubble Sort giúp nắm vững các khái niệm cơ bản về sắp xếp

Câu hỏi thảo luận và suy nghĩ (5 phút)

1. Trong trường hợp nào Bubble Sort có thể chạy nhanh hơn?
2. Liệu có thể cải thiện thêm Bubble Sort để đạt được độ phức tạp tốt hơn O(n²)?
3. Tại sao Bubble Sort là thuật toán ổn định?
4. So sánh ưu và nhược điểm của Bubble Sort với Insertion Sort?
5. Trong thực tế, khi nào bạn sẽ chọn sử dụng Bubble Sort thay vì các thuật toán sắp xếp khác?

---

Bài học này cung cấp một cái nhìn toàn diện về thuật toán sắp xếp nổi bọt từ nguyên lý cơ bản đến các cải tiến và ứng dụng thực tế. Học viên sẽ có 1 tiếng 30 phút để hiểu sâu về thuật toán và chuẩn bị cho việc thực hành các bài tập.