My first Magazine pemrograman-kompetitif-dasar

3.2 Pengurutan 1 1 3 5 5 6 7 kanan kiri Gambar 3.6: Tahap 6: Temukan lagi indeks tengah yaitu nilai tengah dari kiri dan kanan dan bandingkan nilainya dengan nilai yang dicari. Ternyata nilai pada indeks tengah adalah 3. Dengan demikian pencarian berhasil. 3.1.3 Rangkuman Secara umum, kedua algoritma pencarian dapat dirangkumkan sebagai berikut. Sequential search • Data untuk pencarian tidak perlu terurut. • Kompleksitasnya O(N), dengan N adalah ukuran data. • Baik diimplementasikan jika pencarian hanya dilakukan sesekali. Binary search • Data untuk pencarian harus terurut. • Kompleksitasnya O(log N), dengan N adalah ukuran data. • Baik diimplementasikan jika pencarian perlu dilakukan berkali-kali. Bagaimana jika kita memiliki data yang sangat banyak, tidak terurut, dan butuh pencarian yang eﬁsien? Salah satu solusinya adalah dengan mengurutkan data tersebut, lalu mengaplikasikan binary search untuk setiap pencarian. 3.2 Pengurutan Pengurutan sering digunakan dalam pemrograman untuk membantu membuat data lebih mudah diolah. Terdapat berbagai macam cara untuk melakukan pengurutan, masing-masing dengan keuntungan dan kekurangannya. Contoh Soal 3.2: Bebek Berbaris Sebelum masuk ke dalam kandang, para bebek akan berbaris terlebih dahulu. Seiring dengan berjalannya waktu, bebek-bebek tumbuh tinggi. Pertumbuhan ini berbeda-beda; ada bebek yang lebih tinggi dari bebek lainnya. Terdapat N ekor bebek, bebek ke-i memiliki tinggi sebesar h i . Perbedaan tinggi ini menyebabkan barisan terlihat kurang rapi, sehingga Pak Dengklek ingin bebek-bebek berbaris dari yang paling pendek ke paling tinggi. Bantulah para bebek untuk mengurutkan barisan mereka! Batasan • 1 ≤ N ≤ 1.000 • 1 ≤ h i ≤ 100.000, untuk 1 ≤ i ≤ N 29

My first Magazine pemrograman-kompetitif-dasar | Page 39