Sắp xếp không so sánh

/* Với n phần tử có n! hoán vị khác nhau.
   Cây quyết định phải có ít nhất n! lá để phân biệt được hết.
   Cây nhị phân có L lá thì chiều cao ít nhất log2(L).

   Chiều cao cây = số phép so sánh trong trường hợp XẤU NHẤT.

     h >= log2(n!)

   Theo xấp xỉ Stirling:  log2(n!) xấp xỉ n log2(n) - 1.44 n

   Nên mọi thuật toán so sánh cần ÍT NHẤT khoảng n log2(n) phép
   so sánh ở trường hợp xấu nhất. Không có ngoại lệ.            */

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

/* Sắp mảng a có n phần tử, mọi giá trị nằm trong [0, k).
   Trả về 0 nếu ổn, -1 nếu hết bộ nhớ.
   Độ phức tạp O(n + k) thời gian, O(n + k) bộ nhớ. */
int counting_sort(int *a, size_t n, size_t k)
{
    if (n < 2) return 0;

    size_t *dem = calloc(k, sizeof *dem);

    if (dem == NULL) return -1;

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

    if (ra == NULL) { free(dem); return -1; }

    /* Bước 1: đếm số lần xuất hiện */
    for (size_t i = 0; i < n; ++i)
        ++dem[a[i]];

    /* Bước 2: tổng tiền tố. dem[v] thành SỐ PHẦN TỬ nhỏ hơn hoặc bằng v,
       tức vị trí ngay sau ô cuối cùng dành cho giá trị v. */
    for (size_t v = 1; v < k; ++v)
        dem[v] += dem[v - 1];

    /* Bước 3: duyệt NGƯỢC để giữ tính ổn định */
    for (size_t i = n; i-- > 0; )
        ra[--dem[a[i]]] = a[i];

    memcpy(a, ra, n * sizeof *a);

    free(ra);
    free(dem);

    return 0;
}

Mang vao : 4 2 2 8 3 3 1        n = 7, k = 9

Buoc 1, dem so lan xuat hien:
  gia tri :  0  1  2  3  4  5  6  7  8
  dem     :  0  1  2  2  1  0  0  0  1

Buoc 2, tong tien to:
  gia tri :  0  1  2  3  4  5  6  7  8
  dem     :  0  1  3  5  6  6  6  6  7

  Doc: co 3 phan tu <= 2, nen gia tri 2 chiem cac o 1 va 2.

Buoc 3, duyet NGUOC mang vao:
  i=6, a[6]=1 : dem[1]=1 -> 0, ra[0] = 1
  i=5, a[5]=3 : dem[3]=5 -> 4, ra[4] = 3
  i=4, a[4]=3 : dem[3]=4 -> 3, ra[3] = 3
  i=3, a[3]=8 : dem[8]=7 -> 6, ra[6] = 8
  i=2, a[2]=2 : dem[2]=3 -> 2, ra[2] = 2
  i=1, a[1]=2 : dem[2]=2 -> 1, ra[1] = 2
  i=0, a[0]=4 : dem[4]=6 -> 5, ra[5] = 4

Ket qua  : 1 2 2 3 3 4 8

#include <stdio.h>

typedef struct { int khoa; char nhan; } Muc;

/* Counting sort cho struct, sắp theo trường khoa. */
int counting_muc(Muc *a, size_t n, size_t k)
{
    size_t *dem = calloc(k, sizeof *dem);
    Muc    *ra  = malloc(n * sizeof *ra);

    if (dem == NULL || ra == NULL) { free(dem); free(ra); return -1; }

    for (size_t i = 0; i < n; ++i) ++dem[a[i].khoa];
    for (size_t v = 1; v < k; ++v) dem[v] += dem[v - 1];

    for (size_t i = n; i-- > 0; )
        ra[--dem[a[i].khoa]] = a[i];

    memcpy(a, ra, n * sizeof *a);

    free(ra);
    free(dem);

    return 0;
}

int main(void)
{
    Muc a[] = {
        { 2, 'a' }, { 1, 'b' }, { 2, 'c' }, { 1, 'd' }, { 3, 'e' },
    };
    size_t n = sizeof a / sizeof a[0];

    printf("truoc: ");

    for (size_t i = 0; i < n; ++i) printf("%d%c ", a[i].khoa, a[i].nhan);

    counting_muc(a, n, 4);

    printf("\nsau  : ");

    for (size_t i = 0; i < n; ++i) printf("%d%c ", a[i].khoa, a[i].nhan);

    printf("\n");

    return 0;
}

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

/* Counting sort theo một chữ số cơ số 256, dịch phải shift bit. */
static int theo_byte(unsigned *a, unsigned *tam, size_t n, int shift)
{
    size_t dem[256] = { 0 };

    for (size_t i = 0; i < n; ++i)
        ++dem[(a[i] >> shift) & 0xFFu];

    for (size_t v = 1; v < 256; ++v)
        dem[v] += dem[v - 1];

    for (size_t i = n; i-- > 0; )                  /* NGƯỢC, giữ ổn định */
        tam[--dem[(a[i] >> shift) & 0xFFu]] = a[i];

    memcpy(a, tam, n * sizeof *a);

    return 0;
}

/* Radix sort cho unsigned 32 bit: bốn lượt, mỗi lượt một byte. */
int radix_sort(unsigned *a, size_t n)
{
    if (n < 2) return 0;

    unsigned *tam = malloc(n * sizeof *tam);

    if (tam == NULL) return -1;

    for (int shift = 0; shift < 32; shift += 8)
        theo_byte(a, tam, n, shift);

    free(tam);

    return 0;
}

Vet voi cac so 170 45 75 90 802 24 2 66, co so 10:

Luot 1, chu so hang DON VI:
  170 90 802 2 24 45 75 66
  (170 va 90 cung chu so 0, 170 vao truoc nen van truoc: ON DINH)

Luot 2, chu so hang CHUC:
  802 2 24 45 66 170 75 90

Luot 3, chu so hang TRAM:
  2 24 45 66 75 90 170 802

Da sap.

/* Chia khoảng giá trị thành m nhóm, rải phần tử vào nhóm,
   sắp từng nhóm, rồi nối lại.

   Chỉ nhanh khi dữ liệu phân bố ĐỀU trên khoảng giá trị. */
int bucket_sort(double *a, size_t n)
{
    if (n < 2) return 0;

    double nho = a[0], lon = a[0];

    for (size_t i = 1; i < n; ++i) {
        if (a[i] < nho) nho = a[i];
        if (a[i] > lon) lon = a[i];
    }

    if (lon == nho) return 0;      /* mọi phần tử bằng nhau */

    size_t m = n;                  /* số nhóm bằng số phần tử */

    /* Đếm số phần tử mỗi nhóm để cấp phát chính xác */
    size_t *dem = calloc(m + 1, sizeof *dem);

    if (dem == NULL) return -1;

    for (size_t i = 0; i < n; ++i) {
        size_t g = (size_t)((a[i] - nho) / (lon - nho) * (double)(m - 1));

        ++dem[g];
    }

    /* ... rải vào nhóm, gọi insertion sort cho từng nhóm, nối lại ... */

    free(dem);

    return 0;
}