Thuật toán C/C++

Merge Sort

Merge sort đệ quy sort hai nửa rồi merge thành range có thứ tự.

Merge Sort là gì?

Merge sort đệ quy sort hai nửa rồi merge thành range có thứ tự.

Dùng divide-and-conquer để sort O(n log n) ổn định.

Đ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 Merge 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>
#include <stdlib.h>

void merge_sort(int *values, int *temporary, int left, int right) {
    if (right - left < 2) return;
    int middle = (left + right) / 2;
    merge_sort(values, temporary, left, middle);
    merge_sort(values, temporary, middle, right);

    int first = left;
    int second = middle;
    int output = left;
    while (first < middle && second < right) {
        temporary[output++] = values[first] < values[second]
            ? values[first++] : values[second++];
    }
    while (first < middle) temporary[output++] = values[first++];
    while (second < right) temporary[output++] = values[second++];
    for (int index = left; index < right; ++index) {
        values[index] = temporary[index];
    }
}

int main(void) {
    int values[] = {8, 3, 6, 2, 7};
    int temporary[5];
    merge_sort(values, temporary, 0, 5);
    for (int index = 0; index < 5; ++index) {
        printf("%d ", values[index]);
    }
}

Output dự kiến

2 3 6 7 8

C++

Chạy code →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

void merge_sort(std::vector<int>& values) {
    if (values.size() < 2) return;
    auto middle = values.begin() + values.size() / 2;
    std::vector<int> left(values.begin(), middle);
    std::vector<int> right(middle, values.end());
    merge_sort(left);
    merge_sort(right);
    std::merge(left.begin(), left.end(), right.begin(), right.end(),
               values.begin());
}

int main() {
    std::vector values{8, 3, 6, 2, 7};
    merge_sort(values);
    for (int value : values) {
        std::cout << value << ' ';
    }
}

Output dự kiến

2 3 6 7 8

So sánh C và C++

Cả hai cần O(n) buffer phụ; C quản lý buffer thủ công còn C++ dùng vector và standard algorithm.

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.