Hiểu bài toán

Bài toán yêu cầu sắp xếp một mảng số nguyên gồm n phần tử theo thứ tự giảm dần (từ lớn đến nhỏ). Dữ liệu đầu vào bao gồm số n và n số nguyên của mảng. Với n ≤ 10^4 và giá trị phần tử ≤ 10^6, các thuật toán sắp xếp có độ phức tạp O(n^2) hoặc O(n log n) đều có thể chấp nhận được.

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

Cách Bubble Sort (Sắp xếp nổi bọt)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ll long long
#define INF 1000
int a[1001];
int n;

ll input(){
    ll x;
    scanf("%lld", &x);
    return x;
}

int main(){
    n = input();
    for (int i = 0; i < n; i++) a[i] = input();

    int temp;
    for (int i = 0; i < n-1; i++)
        for (int j = i+1; j < n; j++)
            if (a[i] < a[j]){
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }

    for (int i = 0; i < n; i++) printf("%d ", a[i]);

    return 0;
}

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

Đây là cách tiếp cận đơn giản nhất. Thuật toán sử dụng hai vòng lặp lồng nhau để so sánh từng cặp phần tử. Nếu phần tử trước nhỏ hơn phần tử sau (theo yêu cầu giảm dần), chúng ta hoán đổi vị trí của chúng. Vòng lặp ngoài chạy từ 0 đến n-2, vòng lặp trong chạy từ i+1 đến n-1. Với mỗi cặp (i, j), nếu A[i] < A[j] thì hoán đổi. Phương pháp này dễ hiểu nhưng không hiệu quả với dữ liệu lớn.

Cách Quick Sort (Thuật toán nhanh)

#include <stdio.h>
int Partition(int a[], int l, int r)
{
    int pivot = a[r];
    int i = l - 1;
    for (int j = l; j < r; j++)
    {
        if (pivot < a[j])
        {
            ++i;
            int tmp = a[j];
            a[j] = a[i];
            a[i] = tmp;
        }
    }
    i++;
    int tmp = a[r];
    a[r] = a[i];
    a[i] = tmp;
    return i;
}
void quicksort(int a[], int l, int r)
{
    if (l < r)
    {
        int m = Partition(a, l, r);
        quicksort(a, l, m - 1);
        quicksort(a, m + 1, r);
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    quicksort(a, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
}

• Time Complexity: O(n log n) (trung bình)
• Space Complexity: O(log n)

Quick Sort là thuật toán chia để trị. Nó chọn một phần tử làm 'pivot' và phân hoạch mảng thành hai phần: các phần tử lớn hơn pivot và nhỏ hơn pivot. Sau đó gọi đệ quy cho hai phần này. Trong code trên, pivot được chọn là phần tử cuối cùng (a[r]). Để sắp xếp giảm dần, chỉ cần thay đổi điều kiện trong hàm Partition từ 'pivot > a[j]' (sắp tăng dần) thành 'pivot < a[j]'. Thuật toán này có độ phức tạp trung bình tốt nhưng có thể xuống cấp O(n^2) trong trường hợp xấu nhất nếu mảng đã được sắp xếp.

Cách Library Function (qsort)

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

// Hàm so sánh dùng cho qsort
// Để sắp xếp giảm dần: trả về hiệu (b - a)
int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}

int main() {
    int n;

    // 1. Nhập số lượng phần tử n
    scanf("%d", &n);

    // Khai báo mảng a với kích thước tối đa theo đề (10^4)
    int a[10005]; 

    // 2. Nhập các phần tử của mảng
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // 3. Sắp xếp mảng giảm dần bằng qsort
    qsort(a, n, sizeof(int), compare);

    // 4. In kết quả ra màn hình
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}

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

Đây là cách hiệu quả và ngắn gọn nhất trong C. Hàm qsort trong thư viện stdlib.h thực hiện thuật toán Quick Sort (hoặc một biến thể hiệu quả tương tự). Để sắp xếp giảm dần, ta cần cung cấp một hàm so sánh custom. Hàm compare(const void a, const void *b) trả về giá trị âm nếu a phải đứng trước b (theo mặc định tăng dần). Để giảm dần, ta trả về giá trị dương nếu *b > *a (tức là *(int)b - (int)a).

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

Bài học kinh nghiệm

• Để sắp xếp giảm dần, logic so sánh giữa các phần tử cần được đảo ngược so với sắp xếp tăng dần (ví dụ: thay vì A[i] > A[j] thì dùng A[i] < A[j]).
• Trong C/C++, hàm qsort là công cụ mạnh mẽ và tối ưu nhất cho các bài toán sắp xếp mảng cỡ vừa (dưới 10^5 phần tử) nhờ độ phức tạp O(n log n) và việc tối ưu hóa ở mức biên dịch.
• Bubble Sort (hoặc Selection Sort) chỉ nên dùng khi n rất nhỏ hoặc để mục đích học thuật, vì độ phức tạp O(n^2) sẽ chậm khi n = 10^4.

Lỗi thường gặp

• Lỗi logic trong hàm so sánh khi dùng qsort: Trả về kết quả không đúng quy ước (dùng nhầm phép trừ a - b thay vì b - a cho giảm dần) sẽ导致sắp xếp sai thứ tự.
• Quên khai báo mảng đủ lớn: Nếu dùng biến static hoặc khai báo mảng không đúng kích thước (ví dụ chỉ khai báo int a[n] trong một số trình biên dịch C cũ) có thể gây lỗi bộ nhớ.
• Sử dụng biến tạm (temp) khi hoán đổi: Khi viết Bubble Sort hay Quick Sort, cần đảm bảo biến temp có kiểu dữ liệu phù hợp (int) và việc hoán đổi giá trị được thực hiện chính xác để không mất dữ liệu.