Quick sort

/* Khuôn chung:

     1. Chọn chốt
     2. Phân hoạch quanh chốt, trả về vị trí cuối cùng p của chốt
     3. Đệ quy sắp a[lo..p) và a[p+1..hi]

   Khác merge sort ở chỗ: merge sort chia dễ trộn khó,
   quick sort chia khó gộp dễ. Sau khi phân hoạch xong thì
   KHÔNG cần bước gộp nào cả.                                */

#include <stddef.h>

static void doi_cho(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* Phân hoạch Lomuto trên khoảng ĐÓNG [lo, hi], chốt là a[hi].
   Trả về vị trí cuối cùng của chốt.

   Bất biến: a[lo..i) toàn phần tử NHỎ HƠN chốt,
             a[i..j)  toàn phần tử LỚN HƠN HOẶC BẰNG chốt. */
static size_t lomuto(int *a, size_t lo, size_t hi)
{
    int    chot = a[hi];
    size_t i    = lo;

    for (size_t j = lo; j < hi; ++j)
        if (a[j] < chot)
            doi_cho(&a[i++], &a[j]);

    doi_cho(&a[i], &a[hi]);      /* đưa chốt về đúng chỗ */

    return i;
}

/* Phân hoạch Hoare: hai con trỏ đi từ hai đầu vào giữa.
   Trả về chỉ số j sao cho a[lo..j] và a[j+1..hi] là hai phần.
   Chú ý: chốt KHÔNG nhất thiết nằm ở vị trí j. */
static size_t hoare(int *a, size_t lo, size_t hi)
{
    int    chot = a[lo + (hi - lo) / 2];      /* chốt là GIÁ TRỊ, không phải vị trí */
    size_t i    = lo;
    size_t j    = hi;

    for (;;) {
        while (a[i] < chot) ++i;
        while (a[j] > chot) --j;

        if (i >= j) return j;

        doi_cho(&a[i], &a[j]);
        ++i;
        --j;
    }
}

void quick_hoare(int *a, size_t lo, size_t hi)
{
    if (lo >= hi) return;

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

    quick_hoare(a, lo, p);          /* CHÚ Ý: p, không phải p-1 */
    quick_hoare(a, p + 1, hi);
}

/* Trung vị của ba: sắp a[lo], a[giua], a[hi] rồi lấy cái giữa.
   Đưa nó về vị trí hi để dùng với Lomuto. */
static void trung_vi_ba(int *a, size_t lo, size_t hi)
{
    size_t giua = lo + (hi - lo) / 2;

    if (a[giua] < a[lo])  doi_cho(&a[giua], &a[lo]);
    if (a[hi]   < a[lo])  doi_cho(&a[hi],   &a[lo]);
    if (a[hi]   < a[giua]) doi_cho(&a[hi],  &a[giua]);

    /* Giờ a[lo] <= a[giua] <= a[hi], tức a[giua] là trung vị */
    doi_cho(&a[giua], &a[hi]);      /* đưa trung vị về cuối làm chốt */
}

#define NGUONG_NHO 24

void quick_sort(int *a, size_t lo, size_t hi)
{
    while (lo < hi) {
        /* 1. Đoạn nhỏ thì dùng insertion sort, xem Bài 27.3 */
        if (hi - lo + 1 <= NGUONG_NHO) {
            insertion_sort(a + lo, hi - lo + 1);

            return;
        }

        trung_vi_ba(a, lo, hi);

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

        /* 2. Đệ quy vào nửa NHỎ HƠN, lặp trên nửa lớn.
              Nhờ vậy độ sâu ngăn xếp không bao giờ vượt log2(n). */
        if (p - lo < hi - p) {
            if (p > lo) quick_sort(a, lo, p - 1);

            lo = p + 1;
        } else {
            quick_sort(a, p + 1, hi);

            if (p == lo) return;

            hi = p - 1;
        }
    }
}

/* Phân hoạch ba đường của Dijkstra, còn gọi là bài toán cờ Hà Lan.
   Chia mảng thành BA phần: nhỏ hơn, bằng, lớn hơn chốt.
   Trả về hai biên qua tham số ra. */
static void ba_duong(int *a, size_t lo, size_t hi,
                     size_t *ra_lt, size_t *ra_gt)
{
    int    chot = a[lo + (hi - lo) / 2];
    size_t lt   = lo;      /* a[lo..lt)  nhỏ hơn chốt */
    size_t i    = lo;      /* a[lt..i)   bằng chốt */
    size_t gt   = hi;      /* a(gt..hi]  lớn hơn chốt */

    while (i <= gt) {
        if      (a[i] < chot) doi_cho(&a[lt++], &a[i++]);
        else if (a[i] > chot) { doi_cho(&a[i], &a[gt]); if (gt == lo) break; --gt; }
        else                  ++i;
    }

    *ra_lt = lt;
    *ra_gt = gt;
}

void quick_ba_duong(int *a, size_t lo, size_t hi)
{
    if (lo >= hi) return;

    size_t lt, gt;

    ba_duong(a, lo, hi, &lt, &gt);

    if (lt > lo)  quick_ba_duong(a, lo, lt - 1);

    quick_ba_duong(a, gt + 1, hi);
}