Mengurutkan array dan mencari elemen secara efisien adalah tugas yang muncul hampir di setiap program. Daripada menulis sendiri algoritma quicksort dan binary search, C menyediakan dua fungsi generik di <stdlib.h>: qsort untuk mengurutkan dan bsearch untuk pencarian biner. Kedua fungsi menerima array void *, ukuran elemen, dan sebuah comparator function pointer. Pada chapter ini kita akan menguasai pola comparator, mengurutkan array sederhana dan struct, lalu memakai bsearch untuk pencarian O(log n).

qsort dengan Comparator Integer dan String #

Signature qsort adalah void qsort(void *base, size_t n, size_t sz, int (*cmp)(const void *, const void *)). Parameter base adalah array, n adalah jumlah elemen, sz adalah ukuran tiap elemen dalam byte, dan cmp adalah function pointer yang membandingkan dua elemen. Comparator harus mengembalikan nilai negatif, nol, atau positif bergantung pada apakah elemen pertama kurang dari, sama dengan, atau lebih besar dari elemen kedua.

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

/* Comparator integer menaik */
static int cmp_int(const void *a, const void *b) {
    int ia = *(const int *)a;
    int ib = *(const int *)b;
    return (ia > ib) - (ia < ib);
}

/* Comparator string menurun (pakai strcmp) */
static int cmp_str_desc(const void *a, const void *b) {
    const char *sa = *(const char *const *)a;
    const char *sb = *(const char *const *)b;
    return -strcmp(sa, sb);  /* negatifkan untuk urutan menurun */
}

int main(void) {
    int arr[] = {42, 17, 9, 31, 24, 8, 55};
    size_t n = sizeof(arr) / sizeof(arr[0]);

    printf("sebelum sort: ");
    for (size_t i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    qsort(arr, n, sizeof(int), cmp_int);
    printf("setelah sort:  ");
    for (size_t i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    /* Pencarian dengan bsearch */
    int key = 31;
    int *found = (int *)bsearch(&key, arr, n, sizeof(int), cmp_int);
    if (found) {
        printf("ditemukan: %d di indeks %zu\n", *found, (size_t)(found - arr));
    } else {
        printf("tidak ditemukan: %d\n", key);
    }

    int key2 = 100;
    int *found2 = (int *)bsearch(&key2, arr, n, sizeof(int), cmp_int);
    printf("pencarian %d: %s\n", key2, found2 ? "ada" : "tidak ada");

    /* Sortir string menurun */
    const char *buah[] = {"mangga", "apel", "jeruk", "pisang"};
    size_t nb = sizeof(buah) / sizeof(buah[0]);
    qsort(buah, nb, sizeof(const char *), cmp_str_desc);
    printf("buah (desc): ");
    for (size_t i = 0; i < nb; i++) printf("%s ", buah[i]);
    printf("\n");

    return 0;
}

Output yang Dihasilkan:

text 
sebelum sort: 42 17 9 31 24 8 55 
setelah sort:  8 9 17 24 31 42 55 
ditemukan: 31 di indeks 4
pencarian 100: tidak ada
buah (desc): pisang mangga jeruk apel

Mari kita telaah baris-baris kode di atas:

  1. Baris 6-10 (cmp_int): comparator generik. Parameter bertipe const void *, jadi harus di-cast dulu ke const int * sebelum di-dereferensi. Ekspresi (ia > ib) - (ia < ib) adalah idiom yang aman dari overflow—berbeda dengan ia - ib yang bisa meluap bila selisih sangat besar.
  2. Baris 13-17 (cmp_str_desc): comparator string menurun. Karena elemen array adalah const char *, parameter const void * sebenarnya menunjuk ke const char *. Cast ke const char *const * diperlukan untuk mengambil string yang ditunjuk. strcmp mengembalikan -1/0/1; negatifkan hasilnya untuk urutan menurun.
  3. Baris 26 (qsort(arr, n, sizeof(int), cmp_int);): qsort mengurutkan array secara in-place. Tidak ada nilai kembalian—jika gagal (jarang terjadi karena alokasi internal), perilaku tidak terdefinisi.
  4. Baris 30 (int *found = (int *)bsearch(...)): bsearch mengembalikan void * yang menunjuk ke elemen yang cocok, atau NULL bila tidak ada. Indeks elemen dapat dihitung dengan found - arr (pointer arithmetic).
  5. Baris 42 (qsort(buah, nb, sizeof(const char *), cmp_str_desc);): sizeof(const char *) adalah 8 pada sistem 64-bit. qsort memakai ukuran ini untuk melangkah dari elemen ke elemen.

Mengurutkan Struct dengan Multi-Key #

Pada praktik nyata, kita sering mengurutkan array struct berdasarkan beberapa field sekaligus: primary key, lalu secondary key bila primary sama. Comparator harus mengembalikan perbedaan primary key terlebih dahulu, baru membandingkan secondary key bila primary sama.

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

typedef struct {
    const char *nama;
    int skor;
} Siswa;

/* Comparator: skor menurun, lalu nama menaik */
static int cmp_siswa(const void *a, const void *b) {
    const Siswa *sa = (const Siswa *)a;
    const Siswa *sb = (const Siswa *)b;
    if (sa->skor != sb->skor) {
        return (sb->skor > sa->skor) - (sb->skor < sa->skor);
    }
    return strcmp(sa->nama, sb->nama);
}

int main(void) {
    Siswa kelas[] = {
        {"budi", 85},
        {"siti", 92},
        {"agus", 85},
        {"dina", 92},
        {"rina", 78},
    };
    size_t n = sizeof(kelas) / sizeof(kelas[0]);

    qsort(kelas, n, sizeof(Siswa), cmp_siswa);

    printf("peringkat kelas:\n");
    for (size_t i = 0; i < n; i++) {
        printf("%2zu. %-6s %d\n", i + 1, kelas[i].nama, kelas[i].skor);
    }

    /* bsearch siswa dengan skor 85, nama "budi" */
    Siswa key = {"budi", 85};
    Siswa *found = (Siswa *)bsearch(&key, kelas, n, sizeof(Siswa), cmp_siswa);
    if (found) {
        printf("\nditemukan: %s (%d) di indeks %zu\n",
               found->nama, found->skor, (size_t)(found - kelas));
    }

    return 0;
}

Output yang Dihasilkan:

text 
peringkat kelas:
 1. dina   92
 2. siti   92
 3. agus   85
 4. budi   85
 5. rina   78

ditemukan: budi (85) di indeks 3

Comparator cmp_siswa membandingkan skor terlebih dahulu. Bila skor sama, comparator melanjutkan ke strcmp untuk nama. Perhatikan arah perbandingan: skor menurun (sb->skor > sa->skor) berarti siswa dengan skor lebih tinggi muncul lebih dulu, sedangkan nama menaik (strcmp(sa->nama, sb->nama)) berarti urutan alfabetis biasa. bsearch memerlukan key lengkap (skor dan nama) untuk menemukan entri spesifik.