Saturday, 15 July 2017

Radix Sort

Bahasan kali ini bukan sesuatu yang berat, yaitu sekedar radix sort.

Orang-orang yang telah menguasai algoritma pengurutan tingkat lanjut pasti tahu tentang jenis pengurutan ini. Algoritmanya sendiri memiliki konsep yang sederhana. Namun di balik konsep sederhana itu, implementasinya mungkin tidak semudah yang dibayangkan. Alasan saya menulis topik ini adalah memperkenalkan implementasinya, yang ternyata menggunakan stable counting sort.

Pengurutan ini cukup unik, untuk mengurutkan N angka yang memiliki paling banyak d digit, kompleksitasnya adalah O(Nd). Untuk nilai d yang kurang dari log N, algoritma ini lebih cepat dari pengurutan O(N log N).

Saturday, 8 July 2017

Binary Search pada Sparse Table

Terdapat suatu teknik optimisasi yang dapat digunakan pada binary search. Biasanya teknik ini akan membuang faktor sebesar O(log N). Jadi kalau tadinya algoritma berjalan dalam O(log2 N), sekarang menjadi O(log N) saja.

Teknik dapat digunakan pada binary search yang dilakukan pada Sparse Table.


Persoalan Motivasi

Misalnya dimiliki N batu pijakan di danau, yang strukturnya seperti lingkaran. Batu-batu dinomori dari 0 sampai dengan N-1. Berhubung bentuknya siklik, batu i bertetangga dengan batu (i-1) dan (i+1). Tentunya batu 0 bertetangga dengan batu N-1 dan 1. Diketahui pula bahwa apabila seseorang berdiri di batu ke-i, maka dia hanya dapat berpindah tempat ke batu (i+t[i]) mod N. Pertanyaannya adalah, apabila seseorang bediri di suatu posisi x, berapa banyak aktivitas berpindah tempat minimal yang perlu ia lakukan supaya ia memutari satu lingkaran?

Misalnya untuk ilustrasi berikut, banyaknya berpindah tempat yang perlu dilakukan adalah 6 kali. Supaya mudah, saya memodelkan setiap posisi (i+t[i]) mod N sebagai anak panah.