Sắp xếp mảng là một trong những thao tác cơ bản trong lập trình, giúp tổ chức và xử lý dữ liệu một cách hiệu quả. Trong ngôn ngữ lập trình C, có nhiều thuật toán sắp xếp phổ biến, mỗi thuật toán có ưu và nhược điểm riêng. Trong bài viết này, chúng ta sẽ tìm hiểu về sắp xếp mảng trong C, các thuật toán sắp xếp phổ biến như Bubble Sort, Selection Sort, Insertion Sort, và Quick Sort, cùng các ví dụ cài đặt chi tiết.

Mục Lục

  1. Tại sao cần sắp xếp mảng?
  2. Các thuật toán sắp xếp phổ biến trong C
  3. Cách cài đặt thuật toán sắp xếp trong C
  4. So sánh hiệu suất các thuật toán sắp xếp
  5. Kết luận

1. Tại sao cần sắp xếp mảng?

Sắp xếp mảng giúp dữ liệu được tổ chức một cách hợp lý, dễ dàng tìm kiếm, phân tích và xử lý. Ví dụ, sắp xếp danh sách sinh viên theo điểm số giúp dễ dàng xác định học sinh có thành tích tốt nhất. Ngoài ra, việc sắp xếp còn làm cho các thuật toán tìm kiếm hiệu quả hơn, đặc biệt là tìm kiếm nhị phân (binary search).

2. Các thuật toán sắp xếp phổ biến trong C

a) Bubble Sort (Sắp xếp nổi bọt)

Bubble Sort là thuật toán sắp xếp đơn giản, hoạt động bằng cách so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu chúng sai thứ tự. Quá trình này lặp lại cho đến khi mảng được sắp xếp hoàn toàn.

b) Selection Sort (Sắp xếp chọn)

Selection Sort tìm phần tử nhỏ nhất trong mảng và di chuyển nó về đầu mảng. Tiếp tục với các phần tử còn lại cho đến khi mảng được sắp xếp.

c) Insertion Sort (Sắp xếp chèn)

Insertion Sort hoạt động bằng cách xây dựng một mảng con đã sắp xếp. Mỗi phần tử từ mảng chính sẽ được chèn vào đúng vị trí của mảng con để duy trì thứ tự.

d) Quick Sort (Sắp xếp nhanh)

Quick Sort là thuật toán chia để trị, chọn một phần tử làm pivot và phân tách mảng thành hai phần dựa trên pivot. Sau đó, sắp xếp các phần riêng lẻ để đạt được mảng sắp xếp hoàn chỉnh.

3. Cách cài đặt thuật toán sắp xếp trong C

a) Cài đặt Bubble Sort

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

b) Cài đặt Selection Sort

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

c) Cài đặt Insertion Sort

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

d) Cài đặt Quick Sort

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

4. So sánh hiệu suất các thuật toán sắp xếp

Thuật Toán Độ phức tạp trung bình Độ phức tạp xấu nhất
Bubble Sort O(n²) O(n²)
Selection Sort O(n²) O(n²)
Insertion Sort O(n²) O(n²)
Quick Sort O(n log n) O(n²)

Trong các thuật toán trên, Quick Sort thường có hiệu suất tốt hơn với độ phức tạp trung bình là O(n log n), tuy nhiên vẫn có thể đạt O(n²) trong trường hợp xấu nhất. Bubble Sort và Selection Sort không thích hợp cho các mảng lớn do độ phức tạp cao.

5. Kết luận

Sắp xếp mảng là thao tác quan trọng giúp tổ chức dữ liệu, nâng cao hiệu suất và khả năng xử lý của chương trình. Hiểu rõ về các thuật toán sắp xếp giúp lập trình viên lựa chọn giải pháp phù hợp cho từng tình huống cụ thể. Hy vọng qua bài viết này, bạn đã nắm vững cách cài đặt và sử dụng các thuật toán sắp xếp mảng trong C.