So sánh và cách chọn

#include <math.h>
#include <stddef.h>

#define NGUONG_NHO 24

static void intro(int *a, size_t lo, size_t hi, int gioi_han)
{
    while (hi > lo) {
        /* Lưới 1: đoạn nhỏ dùng insertion sort */
        if (hi - lo + 1 <= NGUONG_NHO) {
            insertion_sort(a + lo, hi - lo + 1);

            return;
        }

        /* Lưới 2: quá sâu thì đổi sang heap sort */
        if (gioi_han == 0) {
            heap_sort(a + lo, hi - lo + 1);

            return;
        }

        --gioi_han;

        trung_vi_ba(a, lo, hi);

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

        if (p - lo < hi - p) {
            if (p > lo) intro(a, lo, p - 1, gioi_han);

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

            if (p == lo) return;

            hi = p - 1;
        }
    }
}

void introsort(int *a, size_t n)
{
    if (n < 2) return;

    intro(a, 0, n - 1, 2 * (int)log2((double)n));
}

/* Ba ý tưởng chính của timsort:

   1. TÌM RUN. Quét mảng tìm những đoạn đã sắp sẵn, xuôi hoặc ngược.
      Đoạn ngược thì đảo lại tại chỗ. Dữ liệu thật thường có nhiều
      đoạn như vậy, ví dụ nhật ký gộp từ nhiều nguồn.

   2. MỞ RỘNG RUN NGẮN. Đoạn ngắn hơn ngưỡng thì dùng insertion sort
      mở rộng nó tới độ dài tối thiểu, thường 32 hoặc 64.

   3. TRỘN THÔNG MINH. Giữ một ngăn xếp các đoạn và trộn chúng theo
      quy tắc bảo đảm các đoạn được trộn có kích thước gần nhau.
      Nhờ vậy tổng chi phí trộn vẫn là O(n log n).                */

#include <stdlib.h>

/* Hàm so sánh: âm nếu a trước b, 0 nếu tương đương, dương nếu a sau b. */
static int so_sanh_int(const void *pa, const void *pb)
{
    int a = *(const int *)pa;
    int b = *(const int *)pb;

    return (a > b) - (a < b);      /* KHÔNG viết a - b, xem Bài 26.2 */
}

qsort(a, n, sizeof *a, so_sanh_int);

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

typedef void (*HamSap)(int *, size_t);

typedef enum { DL_NGAU_NHIEN, DL_DA_SAP, DL_SAP_NGUOC, DL_NHIEU_TRUNG,
               DL_SO_LUONG } LoaiDL;

static const char *TEN_DL[DL_SO_LUONG] = {
    "ngau nhien", "da sap", "sap nguoc", "nhieu trung"
};

static void sinh(int *a, size_t n, LoaiDL loai, unsigned hat)
{
    srand(hat);

    for (size_t i = 0; i < n; ++i)
        switch (loai) {
            case DL_NGAU_NHIEN:  a[i] = rand();            break;
            case DL_DA_SAP:      a[i] = (int)i;            break;
            case DL_SAP_NGUOC:   a[i] = (int)(n - i);      break;
            case DL_NHIEU_TRUNG: a[i] = rand() % 100;      break;
            default:             a[i] = 0;                 break;
        }
}

static int so_sanh_double(const void *pa, const void *pb)
{
    double a = *(const double *)pa, b = *(const double *)pb;

    return (a > b) - (a < b);
}

/* Chạy lan lần, mỗi lần dựng lại dữ liệu, trả về TRUNG VỊ. */
static double do_mot(HamSap f, const int *goc, size_t n, int lan)
{
    int    *ban = malloc(n * sizeof *ban);
    double *kq  = malloc((size_t)lan * sizeof *kq);

    if (ban == NULL || kq == NULL) { free(ban); free(kq); return -1.0; }

    for (int k = 0; k < lan; ++k) {
        memcpy(ban, goc, n * sizeof *ban);      /* dựng lại, KHÔNG đo */

        clock_t t0 = clock();

        f(ban, n);

        kq[k] = (double)(clock() - t0) / CLOCKS_PER_SEC;
    }

    /* Kiểm tra kết quả đúng, và cũng để trình biên dịch không bỏ lời gọi */
    for (size_t i = 1; i < n; ++i)
        if (ban[i - 1] > ban[i]) {
            fprintf(stderr, "SAI: khong sap dung\n");
            free(ban); free(kq);

            return -1.0;
        }

    qsort(kq, (size_t)lan, sizeof *kq, so_sanh_double);

    double trung_vi = kq[lan / 2];

    free(ban);
    free(kq);

    return trung_vi;
}

int main(int argc, char **argv)
{
    size_t n   = (argc > 1) ? strtoul(argv[1], NULL, 10) : 100000;
    int    lan = (argc > 2) ? atoi(argv[2]) : 7;

    struct { const char *ten; HamSap f; } bang[] = {
        { "insertion", insertion_sort },
        { "shell",     shell_sort     },
        { "merge",     merge_sort_v   },
        { "intro",     introsort      },
        { "heap",      heap_sort      },
    };

    int *goc = malloc(n * sizeof *goc);

    if (goc == NULL) return 1;

    printf("n = %zu, %d lan moi phep do, lay trung vi\n\n", n, lan);
    printf("%-12s", "");

    for (int d = 0; d < DL_SO_LUONG; ++d) printf("%14s", TEN_DL[d]);

    printf("\n");

    for (size_t t = 0; t < sizeof bang / sizeof bang[0]; ++t) {
        printf("%-12s", bang[t].ten);

        for (int d = 0; d < DL_SO_LUONG; ++d) {
            sinh(goc, n, (LoaiDL)d, 2024);

            double s = do_mot(bang[t].f, goc, n, lan);

            if (s < 0.0) printf("%14s", "loi");
            else         printf("%14.4f", s * 1000.0);
        }

        printf("\n");
    }

    free(goc);

    return 0;
}