Sắp xếp mảng theo thuật toán quicksort với hàm qsort() trong C

Quicksort là một thuật toán phân loại hiệu quả, nhanh chóng và thường được sử dụng trong lập trình. Nó hoạt động bằng cách chia mảng thành các phần nhỏ hơn và sau đó sắp xếp các phần đó một cách đệ quy. Trong ngôn ngữ lập trình C, hàm qsort() trong thư viện chuẩn stdlib.h có thể được sử dụng để thực hiện quicksort một cách dễ dàng và hiệu quả.

Cách hoạt động của hàm qsort()

Hàm qsort() yêu cầu bốn tham số để hoạt động:

1. Con trỏ tới mảng cần sắp xếp: Đây là địa chỉ của mảng mà bạn muốn sắp xếp.
2. Số phần tử trong mảng: Số lượng phần tử có trong mảng.
3. Kích thước của mỗi phần tử: Kích thước của mỗi phần tử trong mảng, được xác định bằng hàm sizeof().
4. Con trỏ tới hàm so sánh: Hàm này được sử dụng để so sánh hai phần tử trong mảng, từ đó quyết định cách sắp xếp.

Ví dụ cụ thể

Giả sử bạn có một mảng các số nguyên và muốn sử dụng qsort() để sắp xếp mảng này theo thứ tự tăng dần. Dưới đây là một ví dụ chi tiết về cách thực hiện:

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

// Hàm so sánh cho số nguyên
int compareInt(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int data[] = {9, 4, 6, 3, 7, 2, 8, 5, 1, 0};
    size_t n = sizeof(data) / sizeof(data[0]);

    // Sử dụng hàm qsort để sắp xếp mảng
    qsort(data, n, sizeof(int), compareInt);

    // In kết quả sau khi sắp xếp
    printf("Mảng sau khi sắp xếp: \n");
    for (size_t i = 0; i < n; i++) {
        printf("%d ", data[i]);
    }
    return 0;
}

Phân tích

• Hàm compareInt: Hàm này nhận vào hai tham số là hai con trỏ kiểu void và sau đó thực hiện ép kiểu thành con trỏ số nguyên. Hàm trả về kết quả của phép trừ giữa hai giá trị này, giúp xác định thứ tự của chúng trong mảng.
• Hàm qsort: Dòng qsort(data, n, sizeof(int), compareInt); sử dụng qsort() để sắp xếp mảng data theo thứ tự tăng dần bằng cách sử dụng hàm so sánh compareInt.

Sắp xếp các kiểu dữ liệu khác

Hàm qsort() không chỉ giới hạn trong việc sắp xếp mảng số nguyên mà cũng có thể sắp xếp các kiểu dữ liệu khác như các cấu trúc (structs) hoặc mảng ký tự. Ví dụ, để sắp xếp mảng các chuỗi theo thứ tự từ điển:

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

// Hàm so sánh cho chuỗi
int compareString(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

int main() {
    const char *data[] = {"apple", "orange", "banana", "pear", "grape"};
    size_t n = sizeof(data) / sizeof(data[0]);

    // Sử dụng hàm qsort để sắp xếp mảng
    qsort(data, n, sizeof(char*), compareString);

    // In kết quả sau khi sắp xếp
    printf("Mảng chuỗi sau khi sắp xếp: \n");
    for (size_t i = 0; i < n; i++) {
        printf("%s ", data[i]);
    }
    return 0;
}

Trong ví dụ này, hàm so sánh compareString sử dụng strcmp để so sánh các chuỗi và qsort để sắp xếp chúng theo thứ tự tăng dần.

Kết luận

Việc sử dụng hàm qsort() trong C giúp đơn giản hóa và tăng tốc quá trình sắp xếp mảng, đặc biệt là khi bạn biết cần sắp xếp theo tiêu chí nào. Bằng cách hiểu rõ và áp dụng đúng từng tham số của hàm qsort(), bạn có thể sắp xếp các kiểu dữ liệu khác nhau một cách dễ dàng và hiệu quả.