My first Magazine pemrograman-kompetitif-dasar | Page 44

3 Pencarian dan Pengurutan Untuk mengurutkan data, diperlukan N kali penyisipan. Setiap menyisipkan, dilakukan penggiringan yang kompleksitasnya: • Pada kasus terbaik O(1), ketika angka yang dimasukkan merupakan angka terbesar pada data saat ini. • Pada kasus terburuk O(N), yaitu ketika angka yang dimasukkan merupakan angka terkecil pada data saat ini. • Pada kasus rata-rata, kompleksitasnya O(N/2), atau bisa ditulis O(N). Berdasarkan observasi tersebut, insertion sort dapat bekerja sangat cepat ketika datanya sudah hampir terurut. Pada kasus terbaik, insertion sort bekerja dalam O(N), yaitu ketika data sudah terurut. Pada kasus terburuk, kompleksitasnya O(N 2 ). Secara rata-rata, kompleksitasnya adalah O(N 2 ). Strategi insertion pada algoritma ini dapat digunakan untuk menambahkan sebuah elemen pada data yang sudah terurut. Ketimbang mengurutkan kembali seluruh elemen, cukup lakukan strategi insertion yang secara rata-rata bekerja dalam O(N). 3.2.4 Counting Sort Berikut adalah langkah-langkah untuk melakukan counting sort : 1. Siapkan M ember yang mana M merupakan banyaknya kemungkinan nilai elemen yang muncul pada array . 2. Setiap ember dinomori dengan sebuah angka yang merupakan seluruh nilai elemen yang mungkin ada. 3. Untuk setiap elemen yang mau diurutkan, masukkan ke ember yang sesuai dengan nilai elemen tersebut. 4. Setelah seluruh elemen dimasukkan ke ember yang bersesuaian, keluarkan isi ember-ember mulai dari ember 1 sampai M secara berurutan. Sebagai ilustrasi, kita ingin mengurutkan array [1, 3, 2, 2, 1, 5] secara menaik. Jika diketahui nilai elemen yang muncul hanyalah dari 1 sampai 5, maka kita cukup menyiapkan 5 ember. Ember-ember tersebut dinomori 1 sampai dengan 5. Maka, tahapan-tahapan counting sort dari awal hingga selesai dalam mengurutkan array tersebut dapat dilihat pada Gambar 3.12 sampai Gambar 3.21. 1 2 3 4 5 Gambar 3.12: Tahap 1: Siapkan 5 ember kosong. 1 3 2 2 1 5 1 2 3 4 5 Gambar 3.13: Tahap 2: Masukkan elemen pertama ke dalam ember. 34