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