Panduan Praktis tentang Algoritma Pengurutan: Contoh dan Penjelasan #
Algoritma pengurutan adalah alat penting dalam ilmu komputer yang memungkinkan kita mengorganisir data dengan efisien. Di artikel ini, kita akan menjelajahi beberapa algoritma pengurutan yang umum dengan contoh, supaya kamu bisa melihat bagaimana cara kerjanya dalam praktik.
1. Bubble Sort #
Cara Kerjanya #
Bubble Sort adalah algoritma yang sangat sederhana. Ia akan terus melangkah melalui daftar, membandingkan elemen yang berdekatan, dan menukarnya jika berada dalam urutan yang salah. Proses ini berlanjut hingga daftar terurut.
Kompleksitas Waktu:
- Kasus Terbaik: \( O(n) \) (sudah terurut)
- Kasus Rata-rata: \( O(n^2) \)
- Kasus Terburuk: \( O(n^2) \)
Contoh #
Bayangkan kamu punya array berikut:
[5, 2, 9, 1, 5, 6]
Proses langkah demi langkah:
- Bandingkan 5 dan 2. Karena 5 > 2, tukar mereka.
[2, 5, 9, 1, 5, 6] - Bandingkan 5 dan 9. Tidak perlu tukar.
- Bandingkan 9 dan 1. Tukar.
[2, 5, 1, 9, 5, 6] - Teruskan hingga akhir array. Ulangi proses ini sampai tidak ada lagi yang perlu ditukar.
Contoh Kode #
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
print(bubble_sort([5, 2, 9, 1, 5, 6])) # Output: [1, 2, 5, 5, 6, 9]
2. Selection Sort #
Cara Kerjanya #
Selection Sort membagi daftar input menjadi bagian yang terurut dan tidak terurut. Ia secara berulang memilih elemen terkecil dari bagian yang tidak terurut dan memindahkannya ke akhir bagian yang terurut.
Kompleksitas Waktu:
- Kasus Terbaik: \( O(n^2) \)
- Kasus Rata-rata: \( O(n^2) \)
- Kasus Terburuk: \( O(n^2) \)
Contoh #
Pertimbangkan array berikut:
[29, 10, 14, 37, 13]
Proses langkah demi langkah:
- Temukan elemen terkecil (10) dan tukar dengan elemen pertama.
[10, 29, 14, 37, 13] - Temukan elemen terkecil berikutnya (13) dan tukar dengan elemen kedua.
[10, 13, 14, 37, 29] - Ulangi sampai seluruh array terurut.
Contoh Kode #
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
print(selection_sort([29, 10, 14, 37, 13])) # Output: [10, 13, 14, 29, 37]
3. Insertion Sort #
Cara Kerjanya #
Insertion Sort membangun array yang terurut satu elemen pada satu waktu. Ia mengambil elemen dari bagian yang tidak terurut dan menempatkannya di posisi yang benar dalam bagian yang terurut.
Kompleksitas Waktu:
- Kasus Terbaik: \( O(n) \) (sudah terurut)
- Kasus Rata-rata: \( O(n^2) \)
- Kasus Terburuk: \( O(n^2) \)
Contoh #
Diberikan array:
[5, 3, 4, 1, 2]
Proses langkah demi langkah:
- Mulai dengan elemen pertama (5) sebagai yang terurut.
- Ambil elemen berikutnya (3) dan masukkan ke dalam bagian yang terurut:
[3, 5, 4, 1, 2] - Ambil 4 dan masukkan:
[3, 4, 5, 1, 2] - Teruskan hingga array sepenuhnya terurut.
Contoh Kode #
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
print(insertion_sort([5, 3, 4, 1, 2])) # Output: [1, 2, 3, 4, 5]
4. Merge Sort #
Cara Kerjanya #
Merge Sort adalah algoritma yang menggunakan pendekatan “bagi dan taklukkan”. Ia membagi array menjadi dua bagian, mengurutkannya secara rekursif, dan kemudian menggabungkan bagian-bagian yang sudah terurut kembali.
Kompleksitas Waktu:
- Kasus Terbaik: \( O(n \log n) \)
- Kasus Rata-rata: \( O(n \log n) \)
- Kasus Terburuk: \( O(n \log n) \)
Contoh #
Mari kita lihat array berikut:
[38, 27, 43, 3, 9, 82, 10]
Langkah demi langkah:
- Bagi array menjadi dua bagian:
[38, 27, 43] dan [3, 9, 82, 10] - Terus bagi hingga hanya tersisa array dengan satu elemen.
- Mulai menggabungkan:
[27, 38, 43] dan [3, 9, 10, 82] - Gabungkan bagian-bagian yang sudah terurut.
Contoh Kode #
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
return arr
print(merge_sort([38, 27, 43, 3, 9, 82, 10])) # Output: [3, 9, 10, 27, 38, 43, 82]
5. Quick Sort #
Cara Kerjanya #
Quick Sort juga menggunakan metode “bagi dan taklukkan”. Ia memilih elemen ‘pivot’ dan membagi elemen lainnya menjadi dua sub-array, tergantung apakah elemen tersebut lebih kecil atau lebih besar dari pivot.
Kompleksitas Waktu:
- Kasus Terbaik: \( O(n \log n) \)
- Kasus Rata-rata: \( O(n \log n) \)
- Kasus Terburuk: \( O(n^2) \) (ini bisa terjadi jika elemen terkecil atau terbesar selalu dipilih sebagai pivot)
Contoh #
Coba lihat array ini:
[10, 80, 30, 90, 40, 50, 70]
Langkah demi langkah:
- Pilih pivot (misalnya, 50).
- Atur ulang array:
[10, 30, 40, 50, 90, 80, 70] - Terapkan logika yang sama secara rekursif pada sub-array.
Contoh Kode #
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([10, 80, 30, 90, 40, 50, 70])) # Output: [10, 30, 40, 50, 70, 80, 90]
6. Heap Sort #
Cara Kerjanya #
Heap Sort memanfaatkan struktur data heap biner untuk mengurutkan elemen. Pertama, ia membangun max heap dari data yang diberikan, lalu secara berulang mengekstrak elemen maksimum dari heap.
Kompleksitas Waktu:
- Kasus Terbaik: \( O(n \log n) \)
- Kasus Rata-rata: \( O(n \log n) \)
- Kasus Terburuk: \( O(n \log n) \)
Contoh #
Mari kita lihat array ini:
[3, 5, 1, 10, 2]
Langkah demi langkah:
- Bangun max heap:
[10, 5, 3, 1, 2] - Hapus elemen terbesar (10) dan bangun kembali heap.
- Terus lakukan hingga array terurut.
Contoh Kode #
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
print(heap_sort([3, 5, 1, 10, 2])) # Output: [1, 2, 3, 5, 10]
Kapan Menggunakan Algoritma Pengurutan yang Mana #
- Bubble Sort, Selection Sort, dan Insertion Sort: Biasanya digunakan untuk dataset kecil karena kesederhanaannya, tetapi tidak efisien untuk dataset yang lebih besar.
- Merge Sort: Lebih disukai untuk dataset besar dan ketika stabilitas dibutuhkan (mempertahankan urutan elemen yang sama).
- Quick Sort: Sering kali yang tercepat dalam praktik untuk kasus rata-rata, tetapi perlu hati-hati untuk menghindari skenario terburuk.
- Heap Sort: Berguna ketika penggunaan memori menjadi perhatian dan ketika Anda memerlukan waktu eksekusi terburuk yang baik.
Kesimpulan #
Algoritma pengurutan adalah dasar untuk memahami manipulasi data dalam ilmu komputer. Dari metode sederhana seperti Bubble Sort hingga teknik yang lebih canggih seperti Quick Sort dan Merge Sort, setiap algoritma memiliki kekuatan dan kasus penggunaan masing-masing. Dengan bereksperimen menggunakan contoh-contoh ini, kamu bisa lebih menghargai bagaimana pengurutan bekerja dan kapan harus menerapkan setiap metode dengan efektif. Selamat coding!