Pengurutan dan Pencarian

Bubble, insertion, merge, dan quick sort serta pencarian linier dan biner.

Daftar isi

Pengurutan menyusun ulang data menjadi urutan naik, sedangkan pencarian menemukan posisi sebuah nilai pada kumpulan data. Keduanya sering bekerja berpasangan karena pencarian biner hanya sah pada data yang sudah terurut. Topik ini mengimplementasikan empat algoritma pengurutan pada data yang sama, yaitu bubble sort, insertion sort, merge sort, dan quick sort. Penutupnya adalah pencarian linier dan pencarian biner yang dibandingkan dari banyaknya perbandingan. Semua program memakai data tetap sehingga keluarannya dapat dihitung ulang.

Bubble sort dan insertion sort#

Bubble sort bergerak melewati array berulang kali dan mempertukarkan dua nilai bertetangga setiap kali urutannya terbalik, sehingga nilai terbesar perlahan naik ke ujung belakang seperti gelembung. Setiap putaran penuh menempatkan satu nilai pada posisi akhirnya, sehingga putaran berikutnya cukup memeriksa sisa yang belum terurut. Insertion sort bekerja seperti menyusun kartu di tangan, yaitu mengambil satu nilai kunci lalu menggeser nilai yang lebih besar satu posisi ke kanan sampai tempat kunci ditemukan.

c pengurutan.c

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

#define JUMLAH 8

int data_awal[JUMLAH] = {29, 10, 14, 37, 13, 5, 22, 8};

void tampilkan(const char *label, const int *a, int n)
{
    printf("%-12s:", label);
    for (int i = 0; i < n; i++) {
        printf(" %d", a[i]);
    }
    printf("\n");
}

void tukar(int *a, int *b)
{
    int sementara = *a;
    *a = *b;
    *b = sementara;
}

void bubble_sort(int *a, int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                tukar(&a[j], &a[j + 1]);
            }
        }
    }
}

void insertion_sort(int *a, int n)
{
    for (int i = 1; i < n; i++) {
        int kunci = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > kunci) {
            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = kunci;
    }
}

void merge(int *a, int *bantu, int kiri, int tengah, int kanan)
{
    int i = kiri;
    int j = tengah + 1;
    int k = kiri;

    while (i <= tengah && j <= kanan) {
        if (a[i] <= a[j]) {
            bantu[k] = a[i];
            i = i + 1;
        } else {
            bantu[k] = a[j];
            j = j + 1;
        }
        k = k + 1;
    }
    while (i <= tengah) {
        bantu[k] = a[i];
        i = i + 1;
        k = k + 1;
    }
    while (j <= kanan) {
        bantu[k] = a[j];
        j = j + 1;
        k = k + 1;
    }
    for (int x = kiri; x <= kanan; x++) {
        a[x] = bantu[x];
    }
}

void merge_sort(int *a, int *bantu, int kiri, int kanan)
{
    if (kiri >= kanan) {
        return;
    }
    int tengah = kiri + (kanan - kiri) / 2;
    merge_sort(a, bantu, kiri, tengah);
    merge_sort(a, bantu, tengah + 1, kanan);
    merge(a, bantu, kiri, tengah, kanan);
}

int partisi(int *a, int rendah, int tinggi)
{
    int poros = a[tinggi];
    int i = rendah - 1;
    for (int j = rendah; j < tinggi; j++) {
        if (a[j] < poros) {
            i = i + 1;
            tukar(&a[i], &a[j]);
        }
    }
    tukar(&a[i + 1], &a[tinggi]);
    return i + 1;
}

void quick_sort(int *a, int rendah, int tinggi)
{
    if (rendah >= tinggi) {
        return;
    }
    int p = partisi(a, rendah, tinggi);
    quick_sort(a, rendah, p - 1);
    quick_sort(a, p + 1, tinggi);
}

int main(void)
{
    int a[JUMLAH];
    int bantu[JUMLAH];

    memcpy(a, data_awal, sizeof a);
    tampilkan("Data awal", a, JUMLAH);

    memcpy(a, data_awal, sizeof a);
    bubble_sort(a, JUMLAH);
    tampilkan("Bubble", a, JUMLAH);

    memcpy(a, data_awal, sizeof a);
    insertion_sort(a, JUMLAH);
    tampilkan("Insertion", a, JUMLAH);

    memcpy(a, data_awal, sizeof a);
    merge_sort(a, bantu, 0, JUMLAH - 1);
    tampilkan("Merge", a, JUMLAH);

    memcpy(a, data_awal, sizeof a);
    quick_sort(a, 0, JUMLAH - 1);
    tampilkan("Quick", a, JUMLAH);

    return 0;
}

text Keluaran

Data awal   : 29 10 14 37 13 5 22 8
Bubble      : 5 8 10 13 14 22 29 37
Insertion   : 5 8 10 13 14 22 29 37
Merge       : 5 8 10 13 14 22 29 37
Quick       : 5 8 10 13 14 22 29 37

Empat algoritma menghasilkan urutan akhir yang sama persis, sehingga pembedanya justru terletak pada cara bekerja dan banyaknya operasi. Insertion sort menyimpan kunci pada variabel terpisah sebelum menggeser, sehingga penggeseran tidak menimpa nilai yang sedang dibawa. Bubble sort memakai fungsi tukar yang menerima dua pointer karena pertukaran pada C hanya dapat dilakukan melalui alamat, sebagaimana pola pass by reference. Pada data yang hampir terurut, insertion sort jauh lebih hemat karena perulangan dalamnya langsung berhenti, sedangkan bubble sort tetap melewati seluruh putarannya.

Merge sort dan quick sort#

Merge sort dan quick sort sama-sama memakai strategi divide and conquer, yaitu memecah masalah besar menjadi masalah kecil yang serupa, tetapi keduanya memecahnya pada titik yang berbeda. Merge sort membagi array menjadi dua bagian sama besar secara membabi buta, lalu mengurutkan masing-masing secara rekursif. Fungsi merge menyatukan dua bagian terurut dengan membandingkan ujung depan keduanya. Quick sort justru melakukan sebagian besar pekerjaannya pada tahap pemecahan. Fungsi partisi menempatkan nilai poros pada posisi akhirnya dan memastikan semua nilai yang lebih kecil berada di kirinya.

Tabel berikut merangkum keempat algoritma dari sisi pertumbuhan waktu dan kebutuhan memorinya. Notasi $O(\cdot)$ menyatakan kelas pertumbuhan banyaknya operasi terhadap banyaknya data. Pembacaan praktisnya, $O(n^2)$ berarti operasi naik sekitar seratus kali lipat setiap kali banyaknya data naik sepuluh kali lipat.

Algoritma	Kasus terburuk	Kasus rata-rata	Memori tambahan
Bubble sort	$O(n^2)$	$O(n^2)$	$O(1)$
Insertion sort	$O(n^2)$	$O(n^2)$	$O(1)$
Merge sort	$O(n \log n)$	$O(n \log n)$	$O(n)$
Quick sort	$O(n^2)$	$O(n \log n)$	$O(\log n)$

Merge sort menjamin $O(n \log n)$ pada semua masukan karena pembagiannya selalu di tengah, dengan konsekuensi buffer tambahan sebesar datanya yang terlihat pada array bantu. Quick sort hemat memori dan cepat pada praktiknya. Namun, poros yang buruk, misalnya nilai terkecil pada data yang sudah terurut, membuat partisinya timpang dan waktunya merosot menjadi $O(n^2)$ . Pilihan poros yang lebih baik, seperti elemen tengah atau acak, menekan risiko tersebut pada kebanyakan masukan.

Pencarian linier dan pencarian biner#

Pencarian linier memeriksa elemen satu per satu dari awal, sehingga banyaknya perbandingan sebanding dengan posisi nilai yang dicari. Pencarian biner menuntut data yang terurut, membandingkan target dengan elemen tengah, lalu melanjutkan hanya pada separuh array yang mungkin memuat target. Rentang pencarian melipat dua setiap langkah, sehingga jumlah perbandingannya tumbuh sekitar $\log_2 n$ , bukan sebanding dengan $n$ . Kedua fungsi menerima parameter int *perbandingan yang diisi selama pencarian berlangsung, sehingga angka pada keluaran berasal dari penghitung di dalam algoritmanya sendiri dan bukan hasil perkiraan.

c pencarian-biner.c

#include <stdio.h>

#define JUMLAH 16

int terurut[JUMLAH] = {2, 5, 9, 13, 17, 21, 26, 30, 35, 39, 44, 48, 53, 61, 68, 74};

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

int cari_biner(const int *a, int n, int target, int *perbandingan)
{
    int rendah = 0;
    int tinggi = n - 1;
    *perbandingan = 0;

    while (rendah <= tinggi) {
        int tengah = rendah + (tinggi - rendah) / 2;
        *perbandingan = *perbandingan + 1;
        if (a[tengah] == target) {
            return tengah;
        }
        if (a[tengah] < target) {
            rendah = tengah + 1;
        } else {
            tinggi = tengah - 1;
        }
    }
    return -1;
}

void uji(int target)
{
    int perbandingan = 0;
    int indeks;

    indeks = cari_linier(terurut, JUMLAH, target, &perbandingan);
    printf("Linier cari %d: indeks %d, %d perbandingan\n", target, indeks, perbandingan);

    indeks = cari_biner(terurut, JUMLAH, target, &perbandingan);
    printf("Biner  cari %d: indeks %d, %d perbandingan\n", target, indeks, perbandingan);
}

int main(void)
{
    uji(61);
    uji(63);
    return 0;
}

text Keluaran

Linier cari 61: indeks 13, 14 perbandingan
Biner  cari 61: indeks 13, 3 perbandingan
Linier cari 63: indeks -1, 16 perbandingan
Biner  cari 63: indeks -1, 4 perbandingan

Nilai 61 berada pada indeks 13, sehingga pencarian linier menyusuri 14 elemen sebelum menemukannya, sedangkan pencarian biner cukup memeriksa tiga elemen tengah. Untuk nilai 63 yang tidak ada, linier tetap memeriksa seluruh 16 elemen, sedangkan biner berhenti setelah rentangnya habis dalam empat langkah. Indeks tengah dihitung dengan rendah + (tinggi - rendah) / 2 alih-alih (rendah + tinggi) / 2 karena bentuk pertama tidak berisiko melimpah ketika kedua indeksnya sangat besar. Pustaka standar C juga menyediakan bsearch untuk pencarian biner dan qsort untuk pengurutan, dan keduanya memakai pointer fungsi sebagai pembandingnya.

Kesalahan umum#

Lima kesalahan berikut muncul saat implementasi maupun saat perbandingannya, dan semuanya berkaitan dengan asumsi yang tidak diperiksa terhadap datanya.

Batas putaran bubble sort yang lebar. Perulangan dalam yang berjalan sampai j < n membaca a[j + 1] di luar array pada putaran pertama. Gunakan batas j < n - 1 - i agar pasangan yang dibandingkan selalu berada di dalam array.
Merge tanpa buffer. Menyatukan dua bagian langsung pada array sumber menimpa nilai yang belum dipindahkan. Salin hasil sementara ke bantu lebih dahulu, lalu tulis kembali setelah rentangnya selesai.
Pencarian biner pada data tak terurut. Algoritma berjalan tanpa pesan error, tetapi hasilnya bisa salah atau tidak ditemukan padahal nilainya ada. Urutkan data terlebih dahulu atau gunakan pencarian linier.
Poros quick sort yang selalu di ujung. Data yang sudah terurut atau hampir terurut membuat partisi timpang dan kedalaman rekursi mengejutkan. Pilih poros dari tengah atau dari beberapa kandidat acak.
Membandingkan algoritma pada data yang berbeda. Banyaknya perbandingan insertion sort sangat bergantung pada seberapa terurut datanya, sehingga dua algoritma yang diuji pada data berbeda tidak dapat disandingkan. Salin data awal yang sama persis sebelum setiap pengurutan, sebagaimana dilakukan program di atas.

Ringkasan#

Bubble sort dan insertion sort mudah ditulis dan cocok untuk data kecil, dengan insertion sort lebih unggul pada data yang hampir terurut.
Merge sort menjamin $O(n \log n)$ dengan buffer tambahan, sedangkan quick sort hemat memori dan cepat pada rata-rata tetapi merosot menjadi $O(n^2)$ ketika porosnya buruk.
Pencarian biner melipatgandakan rentang pencarian setiap langkah sehingga jauh lebih sedikit membandingkan, dengan syarat datanya sudah terurut.

Referensi#

bsearch(3) — Linux man-pages project — Pencarian biner dari pustaka standar C beserta kontrak pembandingnya.
qsort(3) — Linux man-pages project — Pengurutan pustaka standar C yang memakai pointer fungsi sebagai pembanding.
Sorting — VisuAlgo — Visualisasi langkah demi langkah bubble, insertion, merge, dan quick sort.