Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 30.426 phút đọc

qsort và bsearch

Sau bài này bạn sẽ làm được

  • Viết hàm so sánh đúng cho số nguyên, số thực, chuỗi và struct
  • Nêu vì sao qsort không ổn định và cách làm nó ổn định
  • Dùng bsearch và biết điều kiện bắt buộc của nó
  • Sắp xếp mảng chỉ số theo khóa nằm ngoài

Hai hàm này là ví dụ hoàn chỉnh nhất về lập trình tổng quát trong thư viện chuẩn: một cài đặt duy nhất, chạy với mọi kiểu, nhờ ba con số và một con trỏ hàm. Chúng cũng là chỗ có nhiều cách viết sai nhất.

#qsort

#include <stdlib.h>

void qsort(void *co_so, size_t n, size_t co,
           int (*ss)(const void *, const void *));
Tham sốLà gìLỗi hay gặp
co_soĐịa chỉ phần tử đầuTruyền &mang thay vì mang
nSố PHẦN TỬ, không phải số byteTruyền sizeof mang
coKích thước MỘT phần tửTruyền sizeof cả mảng
ssHàm so sánh hai con trỏ tới phần tửXem mục dưới
int a[100];

qsort(a, 100, sizeof a[0], ss_int);              /* dung */
qsort(a, sizeof a / sizeof a[0], sizeof a[0], ss_int);   /* dung, va an toan hon */

qsort(a, sizeof a, sizeof a[0], ss_int);         /* SAI: n la 400 */
qsort(a, 100, sizeof a, ss_int);                 /* SAI: co la 400 */
qsort(&a, 100, sizeof a[0], ss_int);             /* chay dung, nhung &a
                                                    co kieu int (*)[100],
                                                    nen y dinh khong ro */

#Bốn cách viết sai hàm so sánh

Sai một: dùng phép trừ

return *(const int *)a - *(const int *)b;    /* TRAN */

return (x > y) - (x < y);                    /* dung */

Bài 29.2 đã đo: với hai giá trị gần biên của int, phép trừ cho ra số dương khi đáng lẽ phải âm, và mảng bị sắp sai thứ tự.

Sai hai: quên một tầng con trỏ với mảng con trỏ

const char *ten[] = { "Chuong", "An", "Binh" };

/* SAI */
int ss(const void *a, const void *b) { return strcmp(a, b); }

/* DUNG */
int ss(const void *a, const void *b) {
    const char *const *x = a, *const *y = b;

    return strcmp(*x, *y);
}

Sai ba: hàm so sánh không nhất quán

/* Ham so sanh PHAI la mot thu tu toan phan chat:

     1. Doi xung nguoc: neu ss(a,b) < 0 thi ss(b,a) > 0
     2. Bac cau:        neu ss(a,b) < 0 va ss(b,c) < 0 thi ss(a,c) < 0
     3. Nhat quan:      goi hai lan voi cung doi so cho cung ket qua

   Vi pham bat ky dieu nao la HANH VI KHONG XAC DINH,
   khong phai "ket qua sai". qsort co the sap khong het,
   doc ngoai mang, hoac lap vo tan. */

/* Vi pham dieu 3: */
int ss_ngau_nhien(const void *a, const void *b) {
    (void)a; (void)b;

    return rand() % 3 - 1;        /* moi lan mot khac */
}

/* Vi pham dieu 2, tinh vi hon: */
int ss_gan_dung(const void *a, const void *b) {
    double x = *(const double *)a, y = *(const double *)b;

    if (fabs(x - y) < 0.001) return 0;      /* "gan bang thi bang" */

    return (x > y) - (x < y);
}

/* Voi x=0, y=0.0009, z=0.0018:
     ss(x,y) == 0, ss(y,z) == 0, nhung ss(x,z) != 0
   Khong bac cau. */

Sai bốn: NaN trong dữ liệu số thực

Bài 29.2 đã chạy thử: một NaN trong mảng làm quan hệ so sánh mất tính bắc cầu, và mảng ra không hề được sắp xếp. Lọc NaN trước khi sắp.

#qsort không ổn định

Sắp xếp ổn định
Sắp xếp giữ nguyên thứ tự tương đối của những phần tử mà hàm so sánh coi là bằng nhau. Chuẩn C không yêu cầu qsort ổn định.
on-dinh.c
typedef struct { char ten[8]; int diem; int goc; } SV;

/* Chi so sanh diem: ba nguoi 8 diem la "bang nhau" */
static int ss_diem(const void *a, const void *b) {
    const SV *x = a, *y = b;

    return (x->diem < y->diem) - (x->diem > y->diem);   /* giam dan */
}

/* Them khoa phu la THU TU GOC: khong con hai phan tu nao bang nhau */
static int ss_on_dinh(const void *a, const void *b) {
    const SV *x = a, *y = b;

    if (x->diem != y->diem)
        return (x->diem < y->diem) - (x->diem > y->diem);

    return (x->goc > y->goc) - (x->goc < y->goc);
}

SV ds[] = {
    { "An",    8, 0 }, { "Binh", 9, 1 }, { "Cuong", 8, 2 },
    { "Dung",  9, 3 }, { "En",   8, 4 },
};
terminal
gcc -std=c11 -Wall -Wextra -o on-dinh on-dinh.c && ./on-dinh
goc         : An Binh Cuong Dung En
khong on dinh: Binh Dung Cuong En An
on dinh     : Binh Dung An Cuong En

#bsearch

void *bsearch(const void *khoa, const void *co_so, size_t n, size_t co,
              int (*ss)(const void *, const void *));

/* Tra ve con tro toi phan tu tim duoc, hoac NULL. */
int a[] = { 1, 3, 5, 7, 9, 11 };
int khoa = 7;

int *p = bsearch(&khoa, a, 6, sizeof a[0], ss_int);

if (p) printf("thay tai chi so %td\n", p - a);
else   printf("khong thay\n");
terminal
./bsearch-demo
tim 7  -> thay, chi so 3
tim 8  -> khong thay

#Sắp xếp mảng chỉ số

Đôi khi bạn không được phép di chuyển dữ liệu gốc: nó quá lớn để chép, hoặc có con trỏ khác đang trỏ vào nó, hoặc bạn cần nhiều thứ tự cùng lúc. Cách giải là sắp xếp một mảng chỉ số.

/* Ta co mang du lieu lon, va muon ba thu tu khac nhau
   ma khong chep du lieu ba lan. */

SinhVien ds[10000];

size_t theo_ten[10000], theo_diem[10000], theo_lop[10000];

for (size_t i = 0; i < 10000; ++i)
    theo_ten[i] = theo_diem[i] = theo_lop[i] = i;

/* Van de: ham so sanh nhan hai con tro toi size_t,
   no khong biet mang ds o dau. qsort chuan khong co ngu canh. */
Cách chuẩn: ghép cặp
typedef struct {
    const SinhVien *sv;
    size_t          goc;
} Cap;

static int ss_cap_theo_diem(const void *a, const void *b) {
    const Cap *x = a, *y = b;

    if (x->sv->diem != y->sv->diem)
        return (x->sv->diem < y->sv->diem) - (x->sv->diem > y->sv->diem);

    return (x->goc > y->goc) - (x->goc < y->goc);    /* on dinh */
}

Cap *cap = malloc(n * sizeof *cap);

if (!cap) return -1;

for (size_t i = 0; i < n; ++i) { cap[i].sv = &ds[i]; cap[i].goc = i; }

qsort(cap, n, sizeof *cap, ss_cap_theo_diem);

for (size_t i = 0; i < n; ++i)
    printf("%s %d\n", cap[i].sv->ten, cap[i].sv->diem);

free(cap);

/* Chuan C 100 phan tram, khong bien toan cuc, va on dinh.
   Ton them n * 16 byte. */

Bảng tổng kết bốn cách

CáchChuẩn CBộ nhớ thêmDùng khi
Sắp thẳng mảng dữ liệuCóKhôngPhần tử nhỏ, không ai giữ con trỏ vào nó
Thêm trường chỉ số gốcCóVài byte mỗi phần tửChỉ cần ổn định
Ghép cặp con trỏ và chỉ sốCó16 byte mỗi phần tửCần nhiều thứ tự, hoặc dữ liệu không di chuyển được
Sắp mảng con trỏCó8 byte mỗi phần tửPhần tử lớn
qsort_rKhôngKhôngChỉ chạy trên một nền tảng

Tự làm thử

  1. Viết hàm so sánh cho int, double, mảng chuỗi và struct nhiều tiêu chí.
  2. Chạy chương trình sắp xếp năm sinh viên có điểm trùng và xác nhận thứ tự nhóm bằng điểm bị đảo lộn.
  3. Thêm khóa phụ là chỉ số gốc và xác nhận thứ tự được giữ nguyên.
  4. Chạy bsearch trên mảng chưa sắp và đếm xem tìm đúng bao nhiêu trong sáu giá trị.
  5. Viết hàm so sánh vi phạm tính bắc cầu bằng ngưỡng xấp xỉ, sắp một mảng nghìn phần tử, và kiểm tra kết quả có sắp xếp không.
  6. Sắp một mảng chỉ số theo khóa nằm ngoài bằng cách ghép cặp.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

  • Tham số n là số phần tử và co là kích thước một phần tử. Luôn viết sizeof a / sizeof a[0].
  • Bốn cách viết sai hàm so sánh: phép trừ, quên tầng con trỏ, không nhất quán, và NaN.
  • Hàm so sánh không nhất quán là hành vi không xác định, không phải kết quả sai. qsort có thể đọc ngoài mảng.
  • qsort không ổn định. Cách khả chuyển duy nhất là thêm một khóa phụ duy nhất.
  • bsearch trên mảng chưa sắp không báo lỗi, nó chỉ trả về NULL cho một nửa số khóa thật sự có trong mảng.