Thuật toán sắp xếp nổi bọt (Bubble Sort)

Posted on by mtoplistChuyên mục:Top List

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.

test php

banquyen png

Bài viết này được đăng tại

freetuts.net

, không được copy dưới mọi hình thức.

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:

Thuật toán sắp xếp nổi bọt (Bubble Sort) sẽ tiến hành việc so sánh các cặp phần tử liền kề nhau và tráo đổi vị trí của nó cho đúng thứ tự mà người dùng mong muốn.

Bài viết này được đăng tại [free tuts .net]

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}.

Thuật toán này được áp dụng cho các tập dữ liệu nhỏ, vì nó lặp hết tất cả các phần tử có trong tập. Điều này tốn rất nhiều thời gian, đầy là một thuật toán được xem là chậm nhất trong số các thuật toán sắp xếp.

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<<"\t";
      }
}

int main()
{
    int n;
    do{
        cout << "\nNhậ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: \n";
    printArray(a, n);

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

Kết quả:

thuat toan sap xep bubblesort PNG

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!!!.

mtoplist