Thuật toán C/C++

Bubble Sort

Mỗi pass đẩy giá trị lớn nhất chưa sort về cuối.

Bubble Sort là gì?

Mỗi pass đẩy giá trị lớn nhất chưa sort về cuối.

Sắp xếp bằng cách đổi chỗ các cặp kề sai thứ tự.

Điểm quan trọng

Test input rỗng, một phần tử, trùng lặp và đã sắp xếp.
Tách correctness khỏi optimization.
Ưu tiên standard library trong code production.

Mô phỏng Bubble Sort

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++

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]);
    }
}

Output dự kiến

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 << ' ';
    }
}

Output dự kiến

1 2 4 5

So sánh C và C++

Bubble sort mang tính học thuật với O(n²); early exit giúp input đã sorted đạt O(n), production C++ thường dùng std::sort.

Loop, pointer, length và buffer tạm được viết tường minh.

C++

Iterator và standard algorithm tách operation khỏi cách lưu dữ liệu.

Bài tập mở rộng

Chạy cả hai phiên bản rồi thay đổi để quan sát khác biệt về bảo đảm của từng ngôn ngữ.

Trace từng phép so sánh trên giấy.
Test duplicate và extreme value.
Benchmark code tự viết với standard library.