Hiểu bài toán

Bài toán yêu cầu nhập một ma trận số nguyên có m hàng và n cột, sau đó sắp xếp các phần tử của một cột cụ thể (do người dùng chỉ định) theo thứ tự tăng dần. Các cột khác của ma trận không bị thay đổi. Để dễ hình dung, ta có thể coi ma trận là một bảng gồm m hàng và n cột. Khi sắp xếp cột thứ i, ta chỉ thay đổi vị trí của các phần tử trong cột đó, còn các phần tử trong các hàng tương ứng ở các cột khác sẽ đi theo hàng mới của nó. Ví dụ: nếu giá trị tại hàng 1, cột i được hoán đổi với giá trị tại hàng 2, cột i, thì các giá trị tại hàng 1 và hàng 2 ở các cột còn lại cũng sẽ được hoán đổi theo để giữ nguyên dữ liệu của các hàng đó.

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

Cách Sử dụng thuật toán Bubble Sort trực tiếp trên cột của ma trận

#include <stdio.h>

int main() {
    int m, n, i;
    scanf("%d %d %d", &m, &n, &i);  // nhập m, n, i

    int A[m][n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            scanf("%d", &A[r][c]);
        }
    }

    // sắp xếp cột thứ i (đếm từ 1)
    int col = i - 1;
    for (int x = 0; x < m - 1; x++) {
        for (int y = x + 1; y < m; y++) {
            if (A[x][col] > A[y][col]) {
                // Hoán đổi toàn bộ hàng chứa các phần tử của cột đang xét
                // để đảm bảo dữ liệu hàng được giữ nguyên
                for (int k = 0; k < n; k++) {
                    int temp = A[x][k];
                    A[x][k] = A[y][k];
                    A[y][k] = temp;
                }
            }
        }
    }

    // in ra ma trận sau khi sắp xếp
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            printf("%d ", A[r][c]);
        }
        printf("\n");
    }

    return 0;
}

• Time Complexity: O(m^2 * n)
• Space Complexity: O(1)

Đây là cách tiếp cận đơn giản nhất, bắt chước logic của thuật toán Bubble Sort. Ta duyệt qua các cặp hàng (x, y) và so sánh phần tử tại cột i. Nếu phần tử ở hàng x lớn hơn hàng y, ta hoán đổi vị trí của hai hàng đó (tức là hoán đổi toàn bộ các phần tử trong hai hàng đó). Việc này đảm bảo rằng sau khi sắp xếp, cột i sẽ tăng dần và các dữ liệu hàng còn lại vẫn đi đúng theo hàng của nó.

Ưu điểm: Dễ hiểu, dễ cài đặt.

Nhược điểm: Hiệu quả không cao do mỗi lần hoán đổi phải thực hiện lặp qua n phần tử của hai hàng.

Cách Sử dụng mảng phụ lưu trữ cột và hoán đổi

#include <stdio.h>

void sort(int *a, int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
}

int main() {
    int m, n, k, a[110][110], b[110];
    scanf("%d%d%d", &m, &n, &k);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    // Lưu cột thứ k vào mảng phụ b
    for (int i = 1; i <= m; i++) b[i] = a[i][k];
    // Sắp xếp mảng phụ b
    sort(b, m);
    // Gán lại cột k của ma trận a theo thứ tự của mảng b đã sắp xếp
    for (int i = 1; i <= m; i++) a[i][k] = b[i];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

• Time Complexity: O(m^2)
• Space Complexity: O(m)

Cách tiếp cận này tách biệt việc sắp xếp và cấu trúc dữ liệu.

1. Trích xuất dữ liệu của cột cần sắp xếp vào một mảng phụ.
2. Sắp xếp mảng phụ đó bằng thuật toán Bubble Sort (hoặc bất kỳ thuật toán sắp xếp nào khác).
3. Gán các giá trị đã sắp xếp trở lại vào cột tương ứng của ma trận ban đầu.

Ưu điểm: Logic rõ ràng, tách rời thao tác sắp xếp, không cần phải hoán đổi các hàng lớn.

Nhược điểm: Sử dụng thêm bộ nhớ cho mảng phụ. Vấn đề lớn nhất của cách này là nó chỉ sắp xếp các giá trị trong cột mà không hoán đổi các hàng. Trong bài toán này, yêu cầu là 'sắp xếp cột', thường ngụ ý việc sắp xếp các hàng dựa trên giá trị cột đó. Tuy nhiên, dựa trên các ví dụ và giải pháp tham khảo, cách làm này (chỉ cập nhật cột) lại được chấp nhận vì các bài tập cơ bản về ma trận thường yêu cầu thao tác trực tiếp lên cột đó.

Cách Sử dụng hàm qsort của thư viện chuẩn

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

int col_idx;

// Hàm so sánh để dùng cho qsort
int cmp(const void *a, const void *b) {
    const int *ia = (const int *)a;
    const int *ib = (const int *)b;
    // So sánh giá trị tại cột đang xét
    // Lưu ý: Hướng dẫn này giả định cách truy cập cột,
    // nhưng qsort thường dùng cho mảng 1 chiều.
    // Để đơn giản cho ma trận 2 chiều, ta thường phải cấu trúc lại dữ liệu
    // hoặc dùng giải pháp khác.
    // Dưới đây là ví dụ nếu ta xử lý mảng 1 chiều chứa các giá trị cột:
    return (*(int*)a - *(int*)b);
}

int main() {
    int m, n, i;
    scanf("%d %d %d", &m, &n, &i);
    int A[m][n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            scanf("%d", &A[r][c]);
        }
    }

    // Để sắp xếp hàng dựa trên cột, ta tạo mảng cấu trúc hoặc mảng chỉ số
    // Giải pháp 1: Dùng mảng cấu trúc (Struct)
    typedef struct {
        int row[n];
        int val;
    } Row;
    Row rows[m];
    for(int r=0; r<m; r++) {
        for(int c=0; c<n; c++) rows[r].row[c] = A[r][c];
        rows[r].val = A[r][i-1];
    }

    // Hàm so sánh cho struct
    int compare(const void *a, const void *b) {
        Row *ia = (Row *)a;
        Row *ib = (Row *)b;
        return (ia->val - ib->val);
    }

    qsort(rows, m, sizeof(Row), compare);

    // In kết quả
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            printf("%d ", rows[r].row[c]);
        }
        printf("\n");
    }
    return 0;
}

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

Sử dụng hàm qsort của thư viện <stdlib.h> để sắp xếp.

Vì qsort chỉ hoạt động trên mảng 1 chiều, ta cần một cách tiếp cận tinh tế hơn:

1. Cách 1 (Dùng Struct): Tạo một mảng các cấu trúc (struct), mỗi cấu trúc chứa một hàng của ma trận và giá trị của cột cần sắp xếp. Sắp xếp mảng các cấu trúc này dựa trên giá trị cột.
2. Cách 2 (Dùng mảng chỉ số): Tạo một mảng chỉ số từ 0 đến m-1. Sắp xếp mảng chỉ số này sao cho idx[i] là chỉ số hàng thứ i sau khi sắp xếp. Sau đó in ma trận theo thứ tự các chỉ số này.

Cách này hiệu quả về mặt thời gian执行 (do dùng thuật toán sắp xếp nhanh) và code ngắn gọn nếu đã quen với thư viện chuẩn.

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

Bài học kinh nghiệm

• Bài toán yêu cầu sắp xếp 'cột', nhưng thực chất là sắp xếp các hàng của ma trận dựa trên giá trị của một cột cụ thể. Khi các hàng được hoán đổi vị trí, dữ liệu trong các cột khác cũng đi theo.
• Có thể giải quyết bài toán bằng cách hoán đổi trực tiếp trên ma trận 2 chiều (kiểu Bubble Sort) hoặc bằng cách tách dữ liệu cột ra sắp xếp và cập nhật lại.

Lỗi thường gặp

• Chú ý index của cột trong input (từ 1 đến n) trong khi index trong mảng C/C++ thường từ 0. Cần trừ đi 1 khi sử dụng.
• Nếu chỉ sắp xếp các giá trị trong cột mà không hoán đổi các hàng tương ứng, kết quả đầu ra của các cột khác có thể bị sai lệch so với yêu cầu bài toán (dù một số bài tập cơ bản có thể chấp nhận cách này).