Pengurutan dan pencarian

core:sort dan pencarian biner pada data yang berdampingan.

Daftar isi

Topik ini membahas pengurutan data dan pencarian biner (binary search) pada Odin sebagai dua pola yang saling menopang. Pengurutan dilakukan dengan pustaka core:sort, mulai dari pengurutan slice bertipe dasar, pengurutan menurun, hingga pengurutan struct berdasarkan satu field melalui comparator. Pencarian biner dilakukan dengan pustaka core:slice terhadap slice yang sudah terurut. Pembahasan ditutup dengan alasan mengapa data yang berdampingan dalam satu slice lebih ramah pencarian biner daripada struktur berkunci seperti map dan pohon (tree). Setelah topik ini dibaca, data nilai ujian pada contoh dapat diurutkan dan dicari dengan benar, lengkap dengan biaya waktunya.

Mengurutkan slice dengan sort.sort#

Proc sort.sort dari pustaka core:sort mengurutkan data langsung pada tempatnya, yaitu tanpa menyalin elemen ke penyimpanan lain. Proc ini tidak menerima slice mentah, melainkan sebuah Interface yang memuat tiga proc kecil, yaitu len untuk melaporkan jumlah elemen, less untuk membandingkan dua elemen, dan swap untuk menukar posisi dua elemen. Algoritma pengurutan menjadi tidak bergantung pada bentuk data karena seluruh aksesnya melalui ketiga proc tersebut. Bentuk Interface diperlihatkan pada fragmen berikut, yang disalin dari sumber pustaka tersebut.

odin Bentuk Interface yang diterima sort.sort

// tidak-dijalankan

// salinan deklarasi Interface pada sumber pustaka core:sort
Interface :: struct {
	len:  proc(it: Interface) -> int,
	less: proc(it: Interface, i, j: int) -> bool,
	swap: proc(it: Interface, i, j: int),
	collection: rawptr,
}

Untuk slice biasa, pembungkus sort.slice_interface menyusun Interface tersebut dari satu slice bertipe terurut. Tipe terurut adalah tipe yang mendukung operator <, misalnya bilangan bulat dan string. Argumen yang diterima sort.slice_interface berupa pointer ke slice, sehingga sort.sort(sort.slice_interface(&angka)) mengurutkan slice angka itu sendiri dan bukan salinannya. Algoritma di dalam sort.sort adalah pengurutan cepat (quicksort) dengan batas kedalaman rekursi, beralih ke heapsort apabila batas terlampaui, dan menggunakan pengurutan penyisipan (insertion sort) untuk bagian yang berukuran kecil. Biaya rata-ratanya adalah $O(n \log n)$ , sedangkan urutan relatif elemen yang nilainya setara tidak dijamin.

Pengurutan menurun dan pemeriksaan is_sorted#

Proc sort.reverse_sort mengurutkan data menurun, dari nilai terbesar ke terkecil, dengan cara pemanggilan yang sama seperti sort.sort. Susunan menurun berguna untuk daftar peringkat, misalnya lima nilai ujian tertinggi pada suatu kelas. Proc ini membungkus Interface melalui sort.reverse_interface, yaitu pembungkus yang memanggil less dengan kedua parameter dibalik. Field collection pada pembungkus itu tetap menunjuk ke slice yang sama, sehingga hasil pengurutan tetap tersimpan pada slice asal. Untuk slice, pemanggilannya berupa sort.reverse_sort(sort.slice_interface(&turun)) sebagaimana terlihat pada program di bagian berikutnya.

Proc sort.is_sorted melaporkan apakah elemen sebuah Interface sudah terurut naik. Pemeriksaannya membandingkan pasangan elemen yang bersebelahan dari akhir ke awal melalui less, sehingga satu pasangan yang tidak naik langsung mengembalikan false. Pemeriksaan ini cocok menjadi penegasan ringan setelah data diurutkan, misalnya sort.is_sorted(sort.slice_interface(&angka)) yang mengembalikan true apabila pengurutan berhasil. Perbedaan arah pengurutan dan arah pemeriksaan perlu diingat sebelum pemeriksaan tersebut digunakan untuk memutuskan langkah berikutnya.

Comparator untuk struct nilai ujian#

Struct tidak memiliki operator < bawaan, sehingga sort.slice_interface tidak dapat diterapkan langsung pada data struct. Pustaka core:sort menyediakan proc pengurutan yang menerima fungsi pembanding (comparator), yaitu proc dengan dua parameter elemen yang mengembalikan angka negatif apabila elemen pertama lebih kecil, nol apabila keduanya setara, dan angka positif apabila elemen pertama lebih besar. Salah satunya adalah sort.quick_sort_proc, sedangkan comparator siap pakai seperti sort.compare_ints tersedia untuk tipe dasar.

Contoh pada topik ini menggunakan data nilai ujian mahasiswa, yaitu struct Mahasiswa dengan field nama bertipe string dan field nilai bertipe int. Comparator urut_nilai mengurutkan dua elemen berdasarkan field nilai saja, sehingga susunan data mengikuti nilai ujian, sedangkan field nama mengikuti barisnya masing-masing. Pembandingan ditulis dengan operator < dan > alih-alih selisih a.nilai - b.nilai, karena selisih dua bilangan bulat dapat meluap (overflow) pada nilai yang ekstrem.

odin Comparator pengurutan berdasarkan field nilai

// tidak-dijalankan

// hasil negatif bila a.nilai < b.nilai, nol bila setara, positif bila lebih besar
urut_nilai :: proc(a, b: Mahasiswa) -> int {
	if a.nilai < b.nilai {
		return -1
	} else if a.nilai > b.nilai {
		return 1
	}
	return 0
}

Program berikut memuat seluruh contoh yang dibahas sampai titik ini, ditambah pencarian biner yang dijelaskan pada dua bagian setelahnya.

odin main.odin

package main

import "core:fmt"
import "core:sort"
import "core:slice"

// Mahasiswa menyimpan satu baris data nilai ujian
Mahasiswa :: struct {
	nama:  string,
	nilai: int,
}

// urut_nilai adalah comparator pengurutan berdasarkan field nilai:
// hasil negatif bila a.nilai < b.nilai, nol bila sama, positif bila lebih besar
urut_nilai :: proc(a, b: Mahasiswa) -> int {
	if a.nilai < b.nilai {
		return -1
	} else if a.nilai > b.nilai {
		return 1
	}
	return 0
}

// cari_nilai membandingkan field nilai satu Mahasiswa dengan kunci pencarian
cari_nilai :: proc(m: Mahasiswa, kunci: int) -> slice.Ordering {
	return slice.cmp(m.nilai, kunci)
}

// cetak_daftar mencetak satu Mahasiswa per baris
cetak_daftar :: proc(daftar: []Mahasiswa) {
	for m in daftar {
		fmt.printfln("  %s: %d", m.nama, m.nilai)
	}
}

main :: proc() {
	// pengurutan naik dengan sort.sort dan slice_interface
	angka := []int{72, 85, 90, 68, 77}
	fmt.println("sebelum:", angka)
	sort.sort(sort.slice_interface(&angka))
	fmt.println("sesudah:", angka)
	fmt.printfln("terurut: %t", sort.is_sorted(sort.slice_interface(&angka)))

	// pengurutan menurun dengan reverse_sort
	turun := []int{72, 85, 90, 68, 77}
	sort.reverse_sort(sort.slice_interface(&turun))
	fmt.println("menurun:", turun)

	// pengurutan struct berdasarkan satu field dengan comparator
	daftar := []Mahasiswa{
		{"Dewi", 85}, {"Ali", 68}, {"Citra", 77}, {"Eka", 90}, {"Budi", 72},
	}
	fmt.println("daftar sebelum diurutkan:")
	cetak_daftar(daftar)
	sort.quick_sort_proc(daftar, urut_nilai)
	fmt.println("daftar setelah diurutkan berdasarkan nilai:")
	cetak_daftar(daftar)

	// pencarian biner pada slice int yang sudah terurut naik
	terurut := []int{68, 72, 77, 85, 90}
	indeks, ketemu := slice.binary_search(terurut, 77)
	fmt.printfln("cari 77: indeks = %d, ketemu = %t", indeks, ketemu)
	indeks, ketemu = slice.binary_search(terurut, 80)
	fmt.printfln("cari 80: indeks = %d, ketemu = %t", indeks, ketemu)
	indeks, ketemu = slice.binary_search(terurut, 100)
	fmt.printfln("cari 100: indeks = %d, ketemu = %t", indeks, ketemu)

	// pencarian biner berdasarkan field struct
	indeks, ketemu = slice.binary_search_by(daftar, 85, cari_nilai)
	if ketemu {
		fmt.printfln("nilai 85: ketemu pada indeks %d, nama = %s", indeks, daftar[indeks].nama)
	}
	indeks, ketemu = slice.binary_search_by(daftar, 80, cari_nilai)
	fmt.printfln("nilai 80: ketemu = %t, titik sisip = %d", ketemu, indeks)
}

bash

# sumberkan lingkungan sandbox jalur odin bila belum tersedia
[ -f /home/kal/my-project/tools/env.sh ] && source /home/kal/my-project/tools/env.sh
# jalankan program dari dalam folder topik
odin run main.odin -file

text Keluaran

sebelum: [72, 85, 90, 68, 77]
sesudah: [68, 72, 77, 85, 90]
terurut: true
menurun: [90, 85, 77, 72, 68]
daftar sebelum diurutkan:
  Dewi: 85
  Ali: 68
  Citra: 77
  Eka: 90
  Budi: 72
daftar setelah diurutkan berdasarkan nilai:
  Ali: 68
  Budi: 72
  Citra: 77
  Dewi: 85
  Eka: 90
cari 77: indeks = 2, ketemu = true
cari 80: indeks = 3, ketemu = false
cari 100: indeks = 5, ketemu = false
nilai 85: ketemu pada indeks 3, nama = Dewi
nilai 80: ketemu = false, titik sisip = 3

Keluaran program memperlihatkan setiap langkahnya secara berurutan. Slice lima angka berubah dari urutan awal menjadi [68, 72, 77, 85, 90], pemeriksaan terurut mengembalikan true, dan reverse_sort menghasilkan urutan [90, 85, 77, 72, 68]. Data mahasiswa tersusun menurut nilai ujian dari 68 hingga 90 dengan urutan nama yang tidak menjadi acuan pengurutan.

Pencarian biner pada slice terurut#

Pencarian biner mencari satu nilai pada slice yang sudah terurut naik dengan membagi rentang pencarian menjadi dua pada setiap langkah. Proc slice.binary_search pada pustaka core:slice mengembalikan dua nilai sekaligus, yaitu indeks dan status found. Apabila nilai ditemukan, indeks menunjuk ke elemen yang cocok. Apabila tidak ditemukan, indeks merupakan titik sisip (insertion point), yaitu posisi tempat nilai tersebut dapat disisipkan tanpa merusak urutan naik.

Keluaran program memperlihatkan ketiga kasusnya pada slice []int{68, 72, 77, 85, 90}. Pencarian 77 mengembalikan indeks 2 dengan ketemu = true. Pencarian 80 gagal, tetapi indeks 3 menunjukkan titik sisip yang tepat di antara 77 dan 85. Pencarian 100 mengembalikan indeks 5, yaitu posisi tepat setelah elemen terakhir.

Jumlah pembandingan pencarian biner adalah sekitar $\log_2 n$ , misalnya sekitar 20 pembandingan untuk satu juta elemen, sedangkan pencarian linear (linear search) pada slice tak terurut berbiaya $O(n)$ . Selisih ini menjadi alasan utama data perlu diurutkan terlebih dahulu apabila pencarian dilakukan berkali-kali. Semantik titik sisip menambah kegunaannya, karena daftar terurut dapat diperbarui tanpa mengurutkan ulang seluruh slice.

Mencari struct berdasarkan field nilai#

Proc slice.binary_search_by mencari pada slice struct dengan membandingkan satu field terhadap kunci pencarian. Parameter ketiganya berupa proc dengan tipe elemen dan tipe kunci yang boleh berbeda. Proc tersebut mengembalikan salah satu nilai enum slice.Ordering, yaitu .Less, .Equal, atau .Greater. Nilai .Less berarti elemen lebih kecil daripada kunci, .Equal berarti keduanya cocok, sedangkan .Greater berarti elemen lebih besar. Setiap langkah membandingkan elemen tengah rentang dengan kunci melalui proc tersebut, lalu membuang satu sisi rentang berdasarkan hasilnya, sehingga proses berhenti dalam $\log_2 n$ langkah.

Proc cari_nilai pada program membandingkan field nilai dengan kunci bertipe int menggunakan slice.cmp, yaitu proc pembanding bawaan untuk tipe terurut. Tipe kunci yang berbeda dari tipe elemen memungkinkan pencarian tanpa menyusun struct sementara. Pada data yang sudah diurutkan dengan urut_nilai, pencarian 85 mengembalikan indeks 3 yang menunjuk ke Dewi, sedangkan pencarian 80 gagal dengan titik sisip 3. Prasyaratnya sama dengan slice.binary_search, yaitu slice terurut naik menurut field yang dibandingkan. Konsistensi arah dan field menjadi tanggung jawab pemanggil, sehingga pasangan sort.quick_sort_proc(daftar, urut_nilai) dan slice.binary_search_by(daftar, 85, cari_nilai) pada program tersebut saling menopang.

Mengapa data berdampingan ramah pencarian biner#

Mekanisme pencarian biner bertumpu pada akses acak (random access), yaitu kemampuan membaca elemen ke-i dengan biaya tetap. Pada satu slice yang berdampingan, elemen ke-i berada pada alamat yang dihitung langsung dari alamat dasar, indeks, dan size_of(E), sehingga setiap pembandingan berupa satu pembacaan memori. Pencarian dengan $\log_2 n$ langkah hanya menyentuh $\log_2 n$ elemen, dan elemen yang berdekatan sering berbagi baris cache.

Struktur berkunci menyimpan elemennya secara terpisah. Map pada Odin tidak menjamin urutan, sehingga pencarian biner tidak dapat diterapkan padanya. Pohon seperti container:rbtree memang menyimpan data terurut, tetapi setiap simpul dialokasikan sendiri dan saling dihubungkan dengan pointer, sehingga satu pembandingan berarti satu lompatan memori. Pencarian biner justru sering melakukan lompatan posisi, dan lompatan indeks pada slice berdampingan lebih murah daripada lompatan pointer antarsimpul pohon.

Kombinasi pengurutan dan pencarian biner menghasilkan pola yang lazim pada pemrograman berorientasi data. Data disimpan sebagai satu slice berdampingan, diurutkan sekali dengan biaya $O(n \log n)$ , lalu dicari berkali-kali dengan biaya $O(\log n)$ per pencarian. Apabila pencarian hanya menyentuh kunci, field kuncinya dapat disimpan pada slice terpisah yang sejajar dengan datanya, pola yang sama dengan struct of arrays, sehingga setiap pencarian biner hanya memuat baris cache milik kunci.

Kesalahan umum#

Kesalahan pertama adalah mencari pada slice yang belum terurut. Pada slice []int{72, 68, 90, 77}, pencarian 77 melalui slice.binary_search mengembalikan ketemu = false meskipun 77 ada pada indeks 3, karena rentang pencariannya terbelah dengan asumsi urutan naik. Perbaikannya berupa pengurutan terlebih dahulu, misalnya dengan sort.sort, sebelum pencarian dilakukan.

Kesalahan kedua adalah menggabungkan arah pengurutan dan arah pencarian yang berbeda. Data yang diurutkan menurun dengan sort.reverse_sort lalu dicari dengan slice.binary_search menghasilkan keluaran yang menyesatkan, misalnya pencarian 77 pada slice [90, 85, 77, 72, 68] dilaporkan tidak ditemukan. Proc pencarian pada pustaka core mengasumsikan urutan naik, sehingga arah kedua operasi harus disamakan atau comparator pencariannya sengaja dibalik.

Kesalahan ketiga adalah mengasumsikan sifat stable, yaitu urutan relatif elemen setara tetap dipertahankan. Proc sort.sort dan sort.quick_sort_proc tidak menjamin sifat tersebut, sehingga dua mahasiswa dengan nilai sama dapat tertukar posisi setelah diurutkan. Apabila urutan setara menjadi bagian dari kebutuhan, gunakan slice.stable_sort_by dari pustaka core:slice, yang menerima proc less dengan tipe kembalian bool.

Ringkasan#

sort.sort(sort.slice_interface(&data)) mengurutkan slice secara langsung dengan biaya rata-rata $O(n \log n)$ , sort.reverse_sort mengurutkan menurun, dan sort.is_sorted memeriksa urutan naik.
Struct diurutkan berdasarkan satu field melalui comparator, misalnya sort.quick_sort_proc dengan proc yang membandingkan field nilai.
slice.binary_search dan slice.binary_search_by mencari pada slice terurut naik dan mengembalikan indeks beserta status found, sedangkan indeks pada pencarian gagal berfungsi sebagai titik sisip.
Data berdampingan menjadikan pencarian biner efisien karena setiap pembandingan berupa akses indeks langsung, berbeda dengan struktur berkunci yang mengikuti pointer antar simpul.

Referensi#

Paket core:sort — Referensi paket Odin — Dokumentasi resmi paket pengurutan yang mencakup sort.sort, slice_interface, reverse_sort, is_sorted, dan proc pengurutan dengan comparator.
Paket core:slice — Referensi paket Odin — Dokumentasi resmi paket slice yang mencakup binary_search, binary_search_by, stable_sort_by, dan tipe Ordering.
Overview — Odin Documentation — Panduan resmi bahasa Odin yang mencakup slice, struct, dan proc sebagai dasar contoh pada topik ini.