Selection sort

#include <stddef.h>

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

void selection_sort(int *a, size_t n)
{
    for (size_t i = 0; i + 1 < n; ++i) {
        size_t nho = i;

        for (size_t j = i + 1; j < n; ++j)
            if (a[j] < a[nho])
                nho = j;

        if (nho != i)                 /* tránh đổi chỗ vô ích */
            doi_cho(&a[i], &a[nho]);
    }
}

/* Mảng: 4a 2 3 4b 1
   Chữ a và b để phân biệt hai số 4 giống nhau.

   Lượt 0: nhỏ nhất là 1 ở chỉ số 4. Đổi chỗ a[0] với a[4]:
            1 2 3 4b 4a          <- 4a NHẢY XUỐNG SAU 4b

   Lượt 1: nhỏ nhất trong 2 3 4b 4a là 2, đã ở chỗ, không đổi.
   Lượt 2: nhỏ nhất trong 3 4b 4a là 3, không đổi.
   Lượt 3: nhỏ nhất trong 4b 4a là 4b, không đổi.

   Kết quả: 1 2 3 4b 4a
   Thứ tự của 4a và 4b đã bị ĐẢO so với ban đầu.               */

/* Vòng trong LUÔN chạy đủ, bất kể dữ liệu:

     for (size_t j = i + 1; j < n; ++j)
         if (a[j] < a[nho]) nho = j;

   Không có cách nào biết sớm rằng phần còn lại đã sắp,
   vì phải xem hết mới biết cái nào nhỏ nhất.

   Tổng số phép so sánh, với MỌI dữ liệu vào:

     (n-1) + (n-2) + ... + 1  =  n(n-1)/2                      */

/* Chỉ cần k phần tử nhỏ nhất, không cần sắp cả mảng. */
void k_nho_nhat(int *a, size_t n, size_t k)
{
    if (k > n) k = n;

    for (size_t i = 0; i < k; ++i) {      /* dừng sau k lượt */
        size_t nho = i;

        for (size_t j = i + 1; j < n; ++j)
            if (a[j] < a[nho]) nho = j;

        if (nho != i) doi_cho(&a[i], &a[nho]);
    }

    /* a[0..k) giờ là k phần tử nhỏ nhất, đã sắp. */
}

/* Mỗi lượt tìm CẢ nhỏ nhất lẫn lớn nhất, đưa về hai đầu.
   Số lượt giảm còn một nửa, dù tổng số phép so sánh gần như không đổi. */
void selection_hai_dau(int *a, size_t n)
{
    if (n < 2) return;

    size_t trai = 0, phai = n - 1;

    while (trai < phai) {
        size_t nho = trai, lon = trai;

        for (size_t j = trai; j <= phai; ++j) {
            if (a[j] < a[nho]) nho = j;
            if (a[j] > a[lon]) lon = j;
        }

        doi_cho(&a[trai], &a[nho]);

        /* Nếu phần tử lớn nhất vừa bị đẩy khỏi vị trí lon bởi phép đổi trên */
        if (lon == trai) lon = nho;

        doi_cho(&a[phai], &a[lon]);

        ++trai;
        --phai;
    }
}