Sorting dan Searching

Sorting dan searching adalah dua operasi yang saling melengkapi. Sorting membiayai O(n log n) sekali di awal, tetapi setelah itu binary search menemukan elemen dalam O(log n)—jauh lebih cepat dari linear search O(n). Pertanyaan kuncinya: kapan biaya sorting awal terbayar? Pada chapter ini kita akan menggabungkan sorting dan searching dalam satu workflow praktis, lalu membandingkan performa tiga pendekatan: linear search, binary search (dengan array sudah terurut), dan sort+binary search (sortir saat dibutuhkan).

Workflow Sorting Lalu Searching #

Pola umum: kita punya data mentah (belum terurut), lalu perlu mencari elemen. Bila pencarian dilakukan satu kali, linear search cukup. Bila pencarian dilakukan berulang pada dataset yang sama, sortir sekali lalu binary search lebih efisien. Berikut contoh konkret pada array struct kontak.

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

typedef struct {
    char nama[32];
    int umur;
} kontak;

/* Comparator berdasarkan nama */
static int cmp_nama(const void *pa, const void *pb) {
    const kontak *a = (const kontak *)pa;
    const kontak *b = (const kontak *)pb;
    return strcmp(a->nama, b->nama);
}

/* Linear search pada array kontak berdasarkan nama */
int cari_linear_kontak(const kontak *a, int n, const char *nama) {
    for (int i = 0; i < n; i++) {
        if (strcmp(a[i].nama, nama) == 0) return i;
    }
    return -1;
}

/* Binary search berdasarkan nama pada array terurut nama */
int cari_binary_kontak(const kontak *a, int n, const char *nama) {
    int kiri = 0, kanan = n - 1;
    while (kiri <= kanan) {
        int mid = kiri + (kanan - kiri) / 2;
        int c = strcmp(a[mid].nama, nama);
        if (c == 0) return mid;
        if (c < 0) kiri = mid + 1;
        else kanan = mid - 1;
    }
    return -1;
}

int main(void) {
    kontak daftar[] = {
        {"Siti", 25},
        {"Budi", 30},
        {"Andi", 22},
        {"Wati", 28},
        {"Rina", 24},
        {"Dewi", 35},
    };
    int n = sizeof(daftar) / sizeof(daftar[0]);

    /* Linear search sebelum sorting */
    printf("Linear search 'Wati': ");
    int idx = cari_linear_kontak(daftar, n, "Wati");
    if (idx >= 0)
        printf("ditemukan di indeks %d (umur %d)\n", idx, daftar[idx].umur);
    else
        printf("tidak ditemukan\n");

    /* Sortir berdasarkan nama */
    qsort(daftar, n, sizeof(kontak), cmp_nama);
    printf("\nSetelah sort by nama:\n");
    for (int i = 0; i < n; i++) {
        printf("  [%d] %s (umur %d)\n", i, daftar[i].nama, daftar[i].umur);
    }

    /* Binary search setelah sorting */
    printf("\nBinary search 'Wati': ");
    idx = cari_binary_kontak(daftar, n, "Wati");
    if (idx >= 0)
        printf("ditemukan di indeks %d (umur %d)\n", idx, daftar[idx].umur);
    else
        printf("tidak ditemukan\n");

    printf("Binary search 'Zara': ");
    idx = cari_binary_kontak(daftar, n, "Zara");
    if (idx >= 0)
        printf("ditemukan di indeks %d\n", idx);
    else
        printf("tidak ditemukan\n");

    return 0;
}

Output yang Dihasilkan:

text
Linear search 'Wati': ditemukan di indeks 3 (umur 28)

Setelah sort by nama:
  [0] Andi (umur 22)
  [1] Budi (umur 30)
  [2] Dewi (umur 35)
  [3] Rina (umur 24)
  [4] Siti (umur 25)
  [5] Wati (umur 28)

Binary search 'Wati': ditemukan di indeks 5 (umur 28)
Binary search 'Zara': tidak ditemukan

Setelah qsort() mengurutkan array berdasarkan nama, indeks berubah. Sebelum sorting, “Wati” ada di indeks 3; setelah sorting, “Wati” pindah ke indeks 5. Inilah karakteristik sorting in-place: data asli dimodifikasi.

Mari kita telaah baris-baris kode di atas:

Baris 4-7 (typedef struct kontak): struct menyimpan nama dan umur. Komparator cmp_nama membandingkan field nama lewat strcmp.
Baris 10-15 (cmp_nama): comparator untuk qsort(). Cast const void * ke const kontak *, lalu pakai strcmp untuk membandingkan nama. strcmp mengembalikan negatif/0/positif sesuai urutan leksikografis.
Baris 18-24 (cari_linear_kontak): linear search pada array kontak sebelum sorting. Bandingkan setiap nama dengan target menggunakan strcmp.
Baris 27-39 (cari_binary_kontak): binary search pada array kontak yang sudah terurut berdasarkan nama. strcmp menentukan arah pencarian: negatif berarti target lebih besar (cari di kanan), positif berarti target lebih kecil (cari di kiri).
Baris 53 (qsort(daftar, n, sizeof(kontak), cmp_nama)): sortir array in-place. Parameter kedua adalah jumlah elemen, ketiga adalah ukuran tiap elemen, keempat adalah comparator.
Baris 59 (cari_binary_kontak(daftar, n, "Wati")): setelah sorting, binary search menemukan “Wati” di indeks 5 dalam O(log n) perbandingan.

Membandingkan Tiga Pendekatan #

Kita akan membandingkan waktu eksekusi tiga pendekatan: (1) linear search tanpa sorting, (2) binary search pada array sudah terurut, dan (3) sort + binary search. Pendekatan ketiga mensimulasikan skenario “saya punya data acak, lalu perlu mencari elemen”.

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

static int cmp_int(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    return (a > b) - (a < b);
}

int linear_search(const int *a, int n, int target) {
    for (int i = 0; i < n; i++)
        if (a[i] == target) return i;
    return -1;
}

int binary_search(const int *a, int n, int target) {
    int kiri = 0, kanan = n - 1;
    while (kiri <= kanan) {
        int mid = kiri + (kanan - kiri) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) kiri = mid + 1;
        else kanan = mid - 1;
    }
    return -1;
}

int main(void) {
    int ukuran[] = {100, 1000, 10000, 100000};
    int k = sizeof(ukuran) / sizeof(ukuran[0]);

    printf("%-8s %-15s %-15s %-15s\n", "n", "linear (1x)", "binary (1x)", "sort+binary");
    for (int i = 0; i < k; i++) {
        int n = ukuran[i];
        int *a = malloc(sizeof(int) * (size_t)n);

        for (int j = 0; j < n; j++) a[j] = j * 2;  /* sudah terurut */

        clock_t s = clock();
        linear_search(a, n, -1);
        double tl = (double)(clock() - s) / CLOCKS_PER_SEC;

        s = clock();
        binary_search(a, n, -1);
        double tb = (double)(clock() - s) / CLOCKS_PER_SEC;

        /* Acak array untuk simulasi sort+binary */
        for (int j = 0; j < n; j++) a[j] = (j * 7) % n;
        s = clock();
        qsort(a, n, sizeof(int), cmp_int);
        binary_search(a, n, -1);
        double ts = (double)(clock() - s) / CLOCKS_PER_SEC;

        printf("%-8d %-15.6f %-15.6f %-15.6f\n", n, tl, tb, ts);
        free(a);
    }
    return 0;
}

Output yang Dihasilkan:

text
n        linear (1x)     binary (1x)     sort+binary    
100      0.000000        0.000000        0.000006       
1000     0.000002        0.000000        0.000027       
10000    0.000020        0.000001        0.000274       
100000   0.000222        0.000001        0.003162       

Pada n = 100.000, binary search pada data terurut hanya butuh 1 mikrodetik, sementara linear search butuh 222 mikrodetik. Namun sort + binary search butuh 3162 mikrodetik—lebih lambat dari linear search untuk satu kali pencarian! Inilah inti keputusan: biaya sorting O(n log n) baru terbayar bila kita melakukan banyak pencarian.

Aturan Praktis: Kapan Sortir dulu #

Tabel berikut memandu keputusan:

Skenario	Pendekatan	Alasan
1 kali pencarian	Linear search	Sortir `O(n log n)` > linear `O(n)` untuk 1 kali
2-10 pencarian	Linear search	Sorting belum terbayar
Banyak pencarian	Sortir + binary search	`O(n log n) + k * O(log n) << k * O(n)`
Data sudah terurut	Binary search	Gratis, tidak perlu sortir lagi
Data besar, tidak terurut, sering dicari	Hash table	`O(1)` lookup rata-rata, mengalahkan binary search