Editorial for ptit064: Gộp mảng

Hiểu bài toán

Cho hai mảng A và B, mỗi mảng có n phần tử, đã được sắp xếp không giảm. Nhiệm vụ là tạo ra mảng C chứa tất cả các phần tử của A và B (tổng cộng 2n phần tử) và sắp xếp chúng theo thứ tự không giảm. Vấn đề này về cơ bản là gộp (merge) hai mảng đã được sắp xếp.

Các cách tiếp cận

Cách Sử dụng hàm qsort (Concatenate then Sort)

#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n;
    scanf("%d", &n);
    int c[2 * n], k = 0;
    for(int i = 0; i < n; i++) scanf("%d", &c[k++]);
    for(int j = 0; j < n; j++) scanf("%d", &c[k++]);
    qsort(c, 2 * n, sizeof(int), cmp);
    for(int l = 0; l < 2 * n; l++) printf("%d ", c[l]);
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Cách tiếp cận này đọc tất cả các phần tử của hai mảng vào một mảng lớn hơn (C), sau đó sử dụng hàm qsort để sắp xếp lại mảng C. Đây là cách đơn giản nhất để giải quyết bài toán, nhưng không tận dụng được việc hai mảng ban đầu đã được sắp xếp sẵn.

Cách Thuật toán Trộn hai mảng (Merge Two Sorted Arrays)

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[100000], b[100000];
    int ans[200000];
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) scanf("%d", &b[i]);

    int i = 0, j = 0, cnt = 0;
    while (i < n && j < n) {
        if (a[i] <= b[j]) {
            ans[cnt++] = a[i++];
        } else {
            ans[cnt++] = b[j++];
        }
    }
    while (i < n) ans[cnt++] = a[i++];
    while (j < n) ans[cnt++] = b[j++];

    for (int k = 0; k < cnt; k++) {
        printf("%d ", ans[k]);
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là thuật toán chuẩn để trộn hai mảng đã được sắp xếp. Sử dụng hai biến chỉ thị (pointer) cho từng mảng, ta duyệt qua cả hai mảng và so sánh các phần tử hiện tại. Phần tử nhỏ hơn được thêm vào mảng kết quả và chỉ số của mảng đó được tăng lên. Cách này hiệu quả hơn nhiều so với việc sắp xếp lại toàn bộ mảng.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Việc hai mảng đầu vào đã được sắp xếp là manh mối quan trọng để tối ưu hóa bài toán.
• Thuật toán trộn mảng (Merge Algorithm) là nền tảng cơ bản trong nhiều thuật toán sắp xếp hiệu quả như Merge Sort.

Lỗi thường gặp

• Cần phân bổ đủ bộ nhớ cho mảng kết quả (2*n phần tử).
• Sai sót trong việc xử lý các phần tử còn sót lại sau khi một trong hai mảng đã duyệt hết (hai vòng lặp while cuối cùng).