My first Magazine pemrograman-kompetitif-dasar | Page 47

3.2 Pengurutan
Karena perlu membuat tabel frekuensi, maka counting sort hanya dapat digunakan ketika
rentang nilai datanya kecil, misalnya ≤ 10 7 . Selain itu, algoritma ini hanya dapat mengurutkan data
diskret. Data seperti bilangan pecahan tidak dapat diurutkan secara tepat. Alternatifnya, untuk
menangani data dengan rentang yang besar atau data yang tidak diskret, kita bisa menggunakan
radix sort yang memiliki konsep yang mirip dengan counting sort .
3.2.5
Rangkuman
Tabel 3.3: Perbandingan beberapa Algoritma Pengurutan.
Algoritma
Kompleksitas Keterangan
Bubble sort
O(N 2 )
-
Selection sort O(N 2 )
Dapat digunakan untuk partial
sort dalam O(KN)
Insertion sort O(N 2 )
Sangat cepat jika data ham-
pir terurut, kasus terbaiknya
O(N)
Counting sort O(N + M)
Cepat hanya untuk data de-
ngan rentang yang kecil
Terdapat algoritma pengurutan yang lebih efisien, misalnya quicksort dan merge sort .
Algoritma pengurutan tersebut menggunakan konsep divide and conquer yang akan dipelajari
pada Bab 5.
II Sekilas Info JJ
Bahasa pemrograman tertentu seperti Java atau C++ memiliki fungsi pengurutan bawaan,
sehingga pada umumnya Anda tidak perlu mengimplementasikan fungsi pengurutan sendiri.
Namun, Anda harus paham konsep pengurutan jika sewaktu-waktu Anda harus memodifikasi
algoritma pengurutan untuk menyelesaikan soal yang diberikan.
37