Thuật toán C/C++

Sắp xếp nổi bọt (bubble sort) trong C, C++

Trong bài học này, bạn sẽ cài đặt thuật toán sắp xếp nổi bọt bằng cách liên tục đổi chỗ các cặp phần tử đứng cạnh nhau bị sai thứ tự.

Giới thiệu

Sắp xếp nổi bọt duyệt qua mảng nhiều lần, mỗi lần so sánh từng cặp phần tử đứng cạnh nhau và đổi chỗ nếu chúng sai thứ tự. Sau mỗi lượt duyệt, giá trị lớn nhất chưa được sắp xếp sẽ dần di chuyển về cuối mảng.

Những điểm quan trọng

  • Kiểm thử với dữ liệu rỗng, chỉ có một phần tử, có giá trị trùng và đã được sắp xếp.
  • Viết cho đúng trước, tối ưu sau.
  • Trong code thực tế, ưu tiên dùng các hàm có sẵn của thư viện chuẩn.

Mô phỏng Sắp xếp nổi bọt (bubble sort) trong C, C++

O(n)

Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.

Code ví dụ bằng C và C++

C
Chạy code →
main.c
#include <stdio.h>

int main(void) {
    int values[] = {5, 1, 4, 2};
    for (int end = 3; end > 0; --end) {
        int changed = 0;
        for (int index = 0; index < end; ++index) {
            if (values[index] > values[index + 1]) {
                int temporary = values[index];
                values[index] = values[index + 1];
                values[index + 1] = temporary;
                changed = 1;
            }
        }
        if (!changed) break;
    }
    for (int index = 0; index < 4; ++index) {
        printf("%d ", values[index]);
    }
}
Kết quả khi chạy
1 2 4 5
C++
Chạy code →
main.cpp
#include <iostream>
#include <vector>

int main() {
    std::vector values{5, 1, 4, 2};
    for (auto end = values.end(); end != values.begin(); --end) {
        bool changed = false;
        for (auto item = values.begin(); item + 1 != end; ++item) {
            if (*item > *(item + 1)) {
                std::iter_swap(item, item + 1);
                changed = true;
            }
        }
        if (!changed) break;
    }
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Kết quả khi chạy
1 2 4 5

So sánh C và C++

Biến changed ghi nhận lượt duyệt có xảy ra đổi chỗ hay không. Nếu không có lần đổi chỗ nào, mảng đã được sắp xếp xong nên vòng lặp dừng sớm, giúp mảng đã sắp xếp sẵn chỉ cần O(n). Trong trường hợp xấu nhất, thuật toán mất O(n²), vì vậy nó chủ yếu dùng để học. Trong thực tế, code C++ thường dùng std::sort.

C

Vòng lặp, con trỏ, độ dài và vùng nhớ tạm đều được viết tường minh.

C++

Iterator và các thuật toán chuẩn tách thao tác xử lý khỏi cách dữ liệu được lưu trữ.

Bài tập mở rộng

Hãy chạy cả hai phiên bản, sau đó thử thay đổi code để quan sát sự khác biệt về mức độ an toàn mà mỗi ngôn ngữ mang lại.

  • Tự mô phỏng từng phép so sánh trên giấy.
  • Thử với giá trị trùng lặp và các giá trị cực lớn, cực nhỏ.
  • Đo thời gian chạy của code tự viết và so sánh với thư viện chuẩn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách