Bubble sort

#include <stddef.h>

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

/* Bản ngây thơ: luôn chạy đủ n-1 lượt. */
void bubble_ngay_tho(int *a, size_t n)
{
    for (size_t i = 0; i + 1 < n; ++i)
        for (size_t j = 0; j + 1 < n - i; ++j)
            if (a[j] > a[j + 1])
                doi_cho(&a[j], &a[j + 1]);
}

/* Bản có cờ: dừng ngay khi một lượt không đổi chỗ lần nào,
   vì lúc đó mảng đã sắp xong. */
void bubble_sort(int *a, size_t n)
{
    for (size_t i = 0; i + 1 < n; ++i) {
        int da_doi = 0;

        for (size_t j = 0; j + 1 < n - i; ++j)
            if (a[j] > a[j + 1]) {
                doi_cho(&a[j], &a[j + 1]);
                da_doi = 1;
            }

        if (!da_doi) break;      /* đã sắp xong, không cần lượt nào nữa */
    }
}

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

typedef struct { char ten[16]; int diem; } SV;

/* So sánh chỉ theo điểm, không theo tên. */
static int theo_diem(const SV *a, const SV *b)
{
    return (a->diem > b->diem) - (a->diem < b->diem);
}

static void bubble_sv(SV *a, size_t n)
{
    for (size_t i = 0; i + 1 < n; ++i) {
        int da_doi = 0;

        for (size_t j = 0; j + 1 < n - i; ++j)
            if (theo_diem(&a[j], &a[j + 1]) > 0) {   /* CHỈ đổi khi LỚN HƠN */
                SV t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                da_doi = 1;
            }

        if (!da_doi) break;
    }
}

int main(void)
{
    SV a[] = {
        { "An",    8 }, { "Binh",  7 }, { "Cuong", 8 },
        { "Dung",  7 }, { "Em",    9 },
    };
    size_t n = sizeof a / sizeof a[0];

    printf("truoc: ");

    for (size_t i = 0; i < n; ++i) printf("%s(%d) ", a[i].ten, a[i].diem);

    bubble_sv(a, n);

    printf("\nsau  : ");

    for (size_t i = 0; i < n; ++i) printf("%s(%d) ", a[i].ten, a[i].diem);

    printf("\n");

    return 0;
}

/* Muốn sắp danh sách theo LỚP tăng dần, trong mỗi lớp theo ĐIỂM giảm dần.

   Cách 1: viết một hàm so sánh gộp cả hai tiêu chí.
   Cách 2: dùng thuật toán ỔN ĐỊNH và sắp hai lần, tiêu chí PHỤ trước.  */

/* Cách 2, chỉ đúng khi thuật toán ổn định */
sap_on_dinh(a, n, theo_diem_giam);      /* tiêu chí phụ, sắp TRƯỚC */
sap_on_dinh(a, n, theo_lop_tang);       /* tiêu chí chính, sắp SAU */

/* Sau lần sắp thứ hai, các phần tử cùng lớp giữ nguyên thứ tự
   mà lần sắp thứ nhất đã tạo ra, tức thứ tự theo điểm giảm dần. */

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

static long so_sanh, hoan_doi;

static void bubble_dem(int *a, size_t n)
{
    for (size_t i = 0; i + 1 < n; ++i) {
        int da_doi = 0;

        for (size_t j = 0; j + 1 < n - i; ++j) {
            ++so_sanh;

            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                ++hoan_doi;
                da_doi = 1;
            }
        }

        if (!da_doi) break;
    }
}

static void dien(int *a, size_t n, int kieu)
{
    for (size_t i = 0; i < n; ++i)
        switch (kieu) {
            case 0: a[i] = rand();              break;   /* ngẫu nhiên */
            case 1: a[i] = (int)i;              break;   /* đã sắp */
            case 2: a[i] = (int)(n - i);        break;   /* sắp ngược */
            default: a[i] = rand() % 10;        break;   /* nhiều trùng */
        }
}

int main(void)
{
    const size_t n = 1000;
    int         *a = malloc(n * sizeof *a);

    if (a == NULL) return 1;

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

    printf("n = %zu, ly thuyet xau nhat: %zu so sanh\n\n", n, n * (n - 1) / 2);
    printf("%-14s %12s %12s\n", "du lieu", "so sanh", "hoan doi");

    for (int k = 0; k < 4; ++k) {
        srand(2024);
        dien(a, n, k);

        so_sanh = hoan_doi = 0;
        bubble_dem(a, n);

        printf("%-14s %12ld %12ld\n", ten[k], so_sanh, hoan_doi);
    }

    free(a);

    return 0;
}

/* Đi qua đi lại hai chiều. Sửa được vấn đề "rùa":
   phần tử NHỎ nằm gần cuối mảng chỉ tiến được MỘT vị trí mỗi lượt,
   nên bubble sort thường tốn rất nhiều lượt vì chúng. */
void cocktail_sort(int *a, size_t n)
{
    if (n < 2) return;

    size_t trai = 0, phai = n - 1;

    while (trai < phai) {
        size_t doi_cuoi = trai;

        for (size_t j = trai; j < phai; ++j)          /* đi sang phải */
            if (a[j] > a[j + 1]) {
                doi_cho(&a[j], &a[j + 1]);
                doi_cuoi = j;
            }

        phai = doi_cuoi;

        if (trai >= phai) break;

        doi_cuoi = phai;

        for (size_t j = phai; j > trai; --j)          /* đi sang trái */
            if (a[j - 1] > a[j]) {
                doi_cho(&a[j - 1], &a[j]);
                doi_cuoi = j;
            }

        trai = doi_cuoi;
    }
}