Pengurutan Cepat dan Penerapannya · Pelajaran 10 dari 10
Memilih algoritma yang tepat
7 menit baca · BelajarCode
Tidak ada algoritma yang terbaik untuk semua keadaan. Pilihan bergantung pada ukuran data, apakah datanya sudah urut, dan kebutuhan lain seperti memori atau kestabilan.
| Algoritma | Terbaik | Rata-rata | Terburuk | Memori tambahan | Stabil |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | Tidak | Ya |
| Selection sort | O(n²) | O(n²) | O(n²) | Tidak | Tidak |
| Insertion sort | O(n) | O(n²) | O(n²) | Tidak | Ya |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | Ya, sebanding n | Ya |
| Quick sort | O(n log n) | O(n log n) | O(n²) | Sedikit, untuk rekursi | Tidak |
Eksperimen: menghitung perbandingan
1import random23def hitung_insertion(data):4 data = data.copy()5 banding = 06 for i in range(1, len(data)):7 kunci = data[i]8 j = i - 19 while j >= 0:10 banding += 111 if data[j] <= kunci:12 break13 data[j + 1] = data[j]14 j -= 115 data[j + 1] = kunci16 return banding1718def hitung_merge(data):19 banding = 020 def urut(bagian):21 nonlocal banding22 if len(bagian) <= 1:23 return bagian24 tengah = len(bagian) // 225 kiri, kanan = urut(bagian[:tengah]), urut(bagian[tengah:])26 hasil = []27 i = j = 028 while i < len(kiri) and j < len(kanan):29 banding += 130 if kiri[i] <= kanan[j]:31 hasil.append(kiri[i])32 i += 133 else:34 hasil.append(kanan[j])35 j += 136 return hasil + kiri[i:] + kanan[j:]37 urut(data)38 return banding3940random.seed(5)41acak = random.sample(range(10000), 1000)42hampir_urut = sorted(acak)43hampir_urut[10], hampir_urut[20] = hampir_urut[20], hampir_urut[10]4445print("Data acak : insertion", hitung_insertion(acak), " merge", hitung_merge(acak))46print("Data hampir urut: insertion", hitung_insertion(hampir_urut), " merge", hitung_merge(hampir_urut))Data acak : insertion 255011 merge 8724 Data hampir urut: insertion 1018 merge 4942
Pada data acak, merge sort jauh lebih hemat. Tetapi pada data yang hampir urut, insertion sort justru lebih sedikit perbandingannya. nonlocal dipakai supaya fungsi di dalam fungsi bisa mengubah variabel banding milik fungsi luarnya.
Panduan memilih
- Data kecil (puluhan): algoritma sederhana sudah cukup, pilih yang paling mudah dibaca.
- Data hampir urut: insertion sort.
- Data besar dan butuh hasil stabil: merge sort, atau sort bawaan bahasa pemrograman.
- Data besar dan memori terbatas: quick sort dengan pivot acak.
- Dalam program sungguhan: pakai sort bawaan. Sudah dioptimalkan dan teruji.
- Pencarian berulang kali pada data yang sama: urutkan sekali, lalu pakai pencarian biner.
Cek pemahaman
Sebuah aplikasi menyimpan 10.000 data dan perlu mencari data ratusan kali setiap menit, sementara datanya jarang berubah. Strategi terbaik adalah?
Latihan
Pilih algoritmanya
Tentukan algoritma yang paling cocok dan jelaskan alasannya:
- Mengurutkan 15 nama anggota kelompok.
- Daftar nilai yang sudah urut, lalu ditambah 3 nilai susulan di akhir.
- Mengurutkan 5 juta transaksi berdasarkan waktu, dan transaksi dengan waktu sama harus tetap dalam urutan masuknya.
Pembahasan
- Algoritma sederhana atau sort bawaan. Datanya sangat kecil, jadi perbedaan kecepatan tidak terasa. Pilih yang paling jelas.
- Insertion sort. Data hampir urut, sehingga hanya 3 nilai yang perlu digeser ke tempatnya.
- Merge sort atau sort bawaan yang stabil. Datanya besar sehingga butuh O(n log n) di semua kasus, dan harus stabil supaya urutan masuk transaksi bertanggal sama tidak berubah.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.