huật toán sắp xếp nổi bọt (Bubble Sort) - Sắp xếp & tìm kiếm

Trong bài này mình sẽ giới thiệu đến các bạn thuật toán sắp xếp nổi bọt (Bubble Sort). Đây là một thuật toán sắp xếp khá đơn giản và dễ hiểu.

Chúng ta sẽ cùng nhau tìm hiểu về khái niệm sắp xếp nổi bọt (Bubble Sort), thuật toán sắp xếp và cách triển khai. Sau đó mình sẽ có một ví dụ đơn giản áp dụng thuật toán (mình sẽ sử dụng ngôn ngữ C++ để viết).

1. Sắp xếp nổi bọt (Bubble Sort) là gì?

Sắp xếp nổi bọt được hiểu đơn giản như sau:

Ví dụ:

Chúng ta có một tập các số như sau: A = {20; 5; 25; 30; 22; 40}. Giả sử chúng ta muốn sắp xếp theo chiều tăng dần từ trái sang phải, thì thuật toán sẽ hoạt động như sau:

• Thuật toán sẽ bắt đầu với cặp phần tử đầu tiên là {20; 5}. Trong cặp phần tử này 20 > 5 vì vậy thuật toán sẽ hoán đổi vị trí số 20 cho vị trí số 5. Sau khi hoán đổi được cặp phần tử mới là {5; 20}.
• Tiếp đến thuật toán sẽ so sánh cặp phần tử {20;25}. Trong trường hợp này vị trí của hai phần tử đã đúng, vì vậy thuật toán sẽ giữ nguyên vị trí của nó.
• Cứ như vậy thuật toán sẽ so sánh đến hết các cặp phần tử của tập A. Sau khi so sánh đến hết sẽ được kết quả như sau: A = {5; 20; 22; 25; 30; 40}.

2. Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C++

Giả sử:

• Chúng ta có arr là một mảng chứa n phần tử.
• Một hàm Swap() để tráo đổi các phần tử (hàm này mình sẽ viết ở bên dưới).

Giải thích thuật toán

• Trong thuật toán chúng ta cần tạo một biến haveSwap để kiểm tra xem tại lần lặp hiện tại có xảy ra việc trao đổi hai số hay không.
• Sử dụng vòng lặp for để lặp tất cả các phần tử có trong mảng. Nếu phần tử thứ J > J + 1 thì tiến hành gọi hàm Swap() để tráo đổi vị trí. Sau đó gán haveSwap = true và ngược lại.
• Nếu không có Swap nào được thực hiện thì mảng đã được sắp xếp. Khi đó chúng ta sẽ thoát khỏi vòng lặp và không cần lặp thêm nữa.

Thuật toán sắp xếp nổi bọt C++

void bubbleSort(int arr[], int n)
{
    int i, j;
    bool haveSwap = false;
    for (i = 0; i < n-1; i++){
    // i phần tử cuối cùng đã được sắp xếp
        haveSwap = false;
        for (j = 0; j < n-i-1; j++){
            if (arr[j] > arr[j+1]){
                swap(arr[j], arr[j+1]);
                haveSwap = true; // Kiểm tra lần lặp này có swap không
            }
        }
        // Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm
        if(haveSwap == false){
            break;
        }
    }
}

3. Ví dụ sắp xếp nổi bọt áp dụng với mảng

Chúng ta sẽ áp dụng thuật toán trên để làm một bài toán đơn giản. Cụ thể chúng ta sẽ sắp xếp các phần tử có trong một mảng được nhập tử bàn phím.

Gợi ý:

• Việc đầu tiên chúng ta cần tạo hàm Swap() để thực hiện tráo đổi vị trí các phần tử.
• Tiếp theo cần tạo hàm bubbleSort() để thực hiện sắp xếp các phần tử.
• Cuối cùng chỉ cần tạo hàm main và yêu cầu người dùng nhập vào các phần tử cho mảng. Sau đó gọi hàm bubbleSort() để sắp xếp là xong.

Code Mẫu:

#include <iostream>
#include <stdio.h>
using namespace std;
void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}
 
// Hàm sắp xếp bubble sort
void bubbleSort(int arr[], int n)
{
    int i, j;
    bool haveSwap = false;
    for (i = 0; i < n-1; i++){
    // i phần tử cuối cùng đã được sắp xếp
        haveSwap = false;
        for (j = 0; j < n-i-1; j++){
            if (arr[j] > arr[j+1]){
                swap(arr[j], arr[j+1]);
                haveSwap = true; // Kiểm tra lần lặp này có swap không
            }
        }
        // Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm
        if(haveSwap == false){
            break;
        }
    }
}
 
/* Hàm xuất mảng */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++){
        cout << arr[i];
        cout<<"	";
      }
}

int main()
{
    int n;
    do{
        cout << "
Nhập vào số lượng phần tử có trong mảng: ";
        cin >> n;
    }while(n <= 0);
    
    int a[n];
    
    for(int i = 0;i < n;i++){
        cout<<"a["<<i<<"]=";
       cin >> a[i];
    };

    bubbleSort(a, n);

    cout<<"Mảng sau khi được sắp xếp: 
";
    printArray(a, n);

    cout<<"
---------------------------------------
";
    cout<<"Chương trình này được đăng tại Zaidap.com.net";
}

Kết quả:

Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp các phần tử có trong mảng. Cũng như kết thúc hướng dẫn thuật toán sắp xếp nổi bọt (Bubble Sort) trong C++. Chúc các bạn thực hiện thành công!!!.