Module 12: Thuật toán

Thuật toán cơ bản trong C

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

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;
            }
}

Tìm kiếm nhị phân

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

Độ phức tạp (Big O)

• O(1): Truy cập mảng
• O(n): Vòng lặp đơn
• O(n²): Vòng lặp lồng nhau
• O(log n): Tìm kiếm nhị phân

Ví dụ

int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
// arr = {11, 12, 22, 25, 34, 64, 90}