Algoritma pengurutan (sorting) adalah proses mengatur elemen-elemen dalam suatu struktur data (seperti array atau daftar) dalam urutan tertentu (misalnya, urutan naik atau turun). Pengurutan adalah langkah penting dalam banyak algoritma lain dan aplikasi praktis karena sering mempermudah dan mempercepat pencarian, pengelompokan, dan pengelolaan data.
4.1 Pengurutan Bubble
Pengurutan bubble adalah algoritma pengurutan sederhana yang berulang kali menukar elemen-elemen yang berdekatan jika mereka berada dalam urutan yang salah. Proses ini diulangi sampai seluruh daftar terurut.
Kelebihan dan Kekurangan Pengurutan Bubble
- Kelebihan: Mudah dipahami dan diimplementasikan.
- Kekurangan: Kurang efisien untuk daftar besar karena memiliki kompleksitas waktu O(n²).
Contoh Implementasi Pengurutan Bubble dalam Python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# Contoh penggunaan
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Array terurut:", sorted_arr) # Output: Array terurut: [11, 12, 22, 25, 34, 64, 90]
4.2 Pengurutan Seleksi
Pengurutan seleksi bekerja dengan membagi array menjadi dua bagian: bagian yang sudah terurut dan bagian yang belum terurut. Algoritma ini berulang kali memilih elemen minimum dari bagian yang belum terurut dan menukarnya dengan elemen pertama dari bagian yang belum terurut.
Kelebihan dan Kekurangan Pengurutan Seleksi
- Kelebihan: Mudah dipahami dan diimplementasikan. Efisien dalam penggunaan memori.
- Kekurangan: Kurang efisien untuk daftar besar karena memiliki kompleksitas waktu O(n²).
Contoh Implementasi Pengurutan Seleksi dalam Python
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# Contoh penggunaan
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Array terurut:", sorted_arr) # Output: Array terurut: [11, 12, 22, 25, 64]
4.3 Pengurutan Sisipan
Pengurutan sisipan bekerja dengan membangun array yang terurut satu elemen pada satu waktu. Ini biasanya dilakukan dengan mengambil satu elemen dari array yang belum terurut dan memasukkannya ke posisi yang benar dalam array yang sudah terurut.
Kelebihan dan Kekurangan Pengurutan Sisipan
- Kelebihan: Efisien untuk daftar kecil atau sebagian besar sudah terurut. Sederhana dan mudah diimplementasikan.
- Kekurangan: Kurang efisien untuk daftar besar karena memiliki kompleksitas waktu O(n²).
Contoh Implementasi Pengurutan Sisipan dalam Python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Contoh penggunaan
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Array terurut:", sorted_arr) # Output: Array terurut: [5, 6, 11, 12, 13]
4.4 Penerapan Pengurutan dalam Python
Mari kita lihat beberapa penerapan praktis dari algoritma pengurutan dalam situasi kehidupan nyata.
Penerapan 1: Mengurutkan Daftar Nama
def urutkan_nama(daftar_nama):
return bubble_sort(daftar_nama)
# Contoh penggunaan
daftar_nama = ["Diana", "Charlie", "Alice", "Bob"]
sorted_nama = urutkan_nama(daftar_nama)
print("Daftar nama terurut:", sorted_nama) # Output: Daftar nama terurut: ['Alice', 'Bob', 'Charlie', 'Diana']
Penerapan 2: Mengurutkan Daftar Angka
def urutkan_angka(daftar_angka):
return selection_sort(daftar_angka)
# Contoh penggunaan
daftar_angka = [34, 7, 23, 32, 5, 62]
sorted_angka = urutkan_angka(daftar_angka)
print("Daftar angka terurut:", sorted_angka) # Output: Daftar angka terurut: [5, 7, 23, 32, 34, 62]
Kesimpulan Bab 4
Pada bab ini, kita telah membahas tiga algoritma pengurutan dasar: pengurutan bubble, pengurutan seleksi, dan pengurutan sisipan. Masing-masing algoritma memiliki kelebihan dan kekurangan sendiri, dan mereka digunakan dalam situasi yang berbeda tergantung pada kebutuhan dan ukuran dataset. Memahami algoritma pengurutan ini adalah dasar yang penting untuk mempelajari algoritma pengurutan yang lebih kompleks dan aplikasi praktis dalam pemrograman.
Di bab selanjutnya, kita akan mengeksplorasi struktur data dasar yang sering digunakan bersama dengan algoritma pengurutan dan pencarian untuk memproses data secara efisien.