Insertion sort

#include <stddef.h>

void insertion_sort(int *a, size_t n)
{
    for (size_t i = 1; i < n; ++i) {
        int    khoa = a[i];      /* phần tử cần chèn */
        size_t j    = i;

        /* Dịch mọi phần tử LỚN HƠN khoa sang phải một ô */
        while (j > 0 && a[j - 1] > khoa) {
            a[j] = a[j - 1];
            --j;
        }

        a[j] = khoa;             /* đặt khoa vào chỗ vừa mở ra */
    }
}

/* Số phép dịch bằng đúng số cặp NGHỊCH THẾ của mảng vào.

   Mảng đã sắp     : 0 cặp     -> n - 1 phép so sánh, 0 phép dịch, O(n)
   Gần sắp, k cặp  : k cặp     -> O(n + k)
   Ngẫu nhiên      : ~n^2/4    -> O(n^2)
   Sắp ngược       : n(n-1)/2  -> O(n^2), xấu nhất

   Với mảng 1 triệu phần tử đã sắp, chỉ đổi 100 phần tử ngẫu nhiên,
   số cặp nghịch thế vẫn rất nhỏ so với n, nên insertion sort
   gần như chạy tuyến tính.                                          */

/* Giữ một mảng luôn sắp khi dữ liệu tới dần.
   Mỗi phần tử mới chỉ tốn O(số phần tử lớn hơn nó). */
int them_giu_sap(int *a, size_t *n, size_t suc_chua, int x)
{
    if (*n >= suc_chua) return -1;

    size_t j = *n;

    while (j > 0 && a[j - 1] > x) { a[j] = a[j - 1]; --j; }

    a[j] = x;
    ++*n;

    return 0;
}

/* Nếu dữ liệu tới gần như đã sắp thì mỗi lần thêm gần như O(1).
   Nếu tới ngẫu nhiên thì mỗi lần O(n), và tổng là O(n^2).
   Lúc đó nên dùng heap ở Bài 23.4 hoặc cây ở Bài 24.7. */

#include <string.h>

/* Chỉ số đầu tiên trong a[0..n) mà a[i] > x.
   Chú ý dấu lớn hơn nghiêm ngặt: nó giữ tính ổn định. */
static size_t cho_chen(const int *a, size_t n, int x)
{
    size_t lo = 0, hi = n;

    while (lo < hi) {
        size_t giua = lo + (hi - lo) / 2;

        if (a[giua] <= x) lo = giua + 1;      /* bằng thì chèn SAU */
        else              hi = giua;
    }

    return lo;
}

void insertion_nhi_phan(int *a, size_t n)
{
    for (size_t i = 1; i < n; ++i) {
        int    khoa = a[i];
        size_t j    = cho_chen(a, i, khoa);

        if (j < i) {
            memmove(&a[j + 1], &a[j], (i - j) * sizeof *a);
            a[j] = khoa;
        }
    }
}

#define NGUONG 24

void quick_sort(int *a, size_t lo, size_t hi)
{
    while (lo < hi) {
        if (hi - lo + 1 <= NGUONG) {
            insertion_sort(a + lo, hi - lo + 1);      /* đoạn nhỏ */

            return;
        }

        size_t p = phan_hoach(a, lo, hi);

        /* Đệ quy vào nửa nhỏ hơn, lặp trên nửa lớn, xem Bài 27.5 */
        if (p - lo < hi - p) {
            quick_sort(a, lo, p ? p - 1 : 0);
            lo = p + 1;
        } else {
            quick_sort(a, p + 1, hi);
            hi = p ? p - 1 : 0;
        }
    }
}

void shell_sort(int *a, size_t n)
{
    /* Dãy bước nhảy của Knuth: 1, 4, 13, 40, 121, 364, ...
       tức h = 3h + 1. Đơn giản và hiệu quả tốt. */
    size_t h = 1;

    while (h < n / 3) h = 3 * h + 1;

    while (h >= 1) {
        /* Insertion sort với bước nhảy h thay vì 1 */
        for (size_t i = h; i < n; ++i) {
            int    khoa = a[i];
            size_t j    = i;

            while (j >= h && a[j - h] > khoa) {
                a[j] = a[j - h];
                j   -= h;
            }

            a[j] = khoa;
        }

        h /= 3;
    }
}