Selection Sort adalah algoritma pengurutan sederhana namun efektif. Bayangkan Anda memiliki setumpuk kartu remi yang berantakan, dan Anda ingin mengurutkannya dari kartu terkecil hingga terbesar. Cara paling intuitif yang mungkin Anda lakukan adalah dengan mencari kartu terkecil, meletakkannya di posisi pertama, kemudian mencari kartu terkecil berikutnya dari sisa kartu yang belum diurutkan, dan menempatkannya di posisi kedua, dan seterusnya. Itulah inti dari Selection Sort. Meskipun bukan algoritma tercepat untuk set data besar, Selection Sort mudah dipahami dan diimplementasikan, menjadikannya landasan penting dalam mempelajari algoritma pengurutan. Pemahaman yang baik tentang Selection Sort memberikan dasar yang kuat untuk memahami algoritma pengurutan yang lebih kompleks.
Memahami Cara Kerja Selection Sort
Selection Sort bekerja dengan iteratif mencari elemen terkecil (atau terbesar, tergantung pada pengurutan ascending atau descending) dari bagian array yang belum diurutkan, dan menukarnya dengan elemen pertama dari bagian array tersebut. Proses ini diulang hingga seluruh array terurut.
Berikut langkah-langkah detailnya:
-
Iterasi Pertama: Cari elemen terkecil dalam seluruh array. Setelah ditemukan, tukar elemen ini dengan elemen pertama dalam array.
-
Iterasi Kedua: Sekarang, abaikan elemen pertama (karena sudah berada di posisi yang benar). Cari elemen terkecil dalam sisa array (dari elemen kedua hingga terakhir). Tukar elemen ini dengan elemen kedua.
-
Iterasi Selanjutnya: Ulangi proses ini untuk setiap elemen dalam array, kecuali elemen terakhir (karena setelah semua elemen sebelumnya terurut, elemen terakhir otomatis berada di posisi yang tepat).
Contoh Ilustrasi
Mari kita ambil contoh array berikut: [64, 25, 12, 22, 11]
-
Iterasi 1:
- Elemen terkecil: 11
- Tukar 64 dengan 11:
[11, 25, 12, 22, 64]
-
Iterasi 2:
- Elemen terkecil (mulai dari indeks 1): 12
- Tukar 25 dengan 12:
[11, 12, 25, 22, 64]
-
Iterasi 3:
- Elemen terkecil (mulai dari indeks 2): 22
- Tukar 25 dengan 22:
[11, 12, 22, 25, 64]
-
Iterasi 4:
- Elemen terkecil (mulai dari indeks 3): 25 (sudah di posisi yang benar)
- Tidak ada pertukaran.
Setelah iterasi ke-4, array telah terurut: [11, 12, 22, 25, 64]
Implementasi Kode dalam Bahasa Indonesia (Python)
Berikut adalah contoh implementasi Selection Sort dalam bahasa Python dengan komentar penjelasan:
def selection_sort(data):
"""
Mengurutkan array 'data' menggunakan algoritma Selection Sort.
Args:
data: List angka yang akan diurutkan.
"""
n = len(data)
# Loop melalui setiap elemen array (kecuali elemen terakhir)
for i in range(n-1):
# Asumsikan elemen saat ini adalah elemen terkecil
min_index = i
# Cari elemen terkecil di sisa array yang belum diurutkan
for j in range(i+1, n):
if data[j] < data[min_index]:
min_index = j
# Tukar elemen terkecil dengan elemen saat ini jika diperlukan
if min_index != i:
data[i], data[min_index] = data[min_index], data[i]
return data
# Contoh penggunaan
angka = [64, 25, 12, 22, 11]
angka_terurut = selection_sort(angka)
print("Array terurut:", angka_terurut) # Output: Array terurut: [11, 12, 22, 25, 64]Analisis Kompleksitas Waktu dan Ruang
-
Kompleksitas Waktu: Selection Sort memiliki kompleksitas waktu O(n^2) dalam semua kasus (best, average, dan worst case). Ini berarti bahwa waktu eksekusi algoritma tumbuh secara kuadratik seiring dengan ukuran input (n). Hal ini disebabkan karena Selection Sort harus menelusuri seluruh array (atau sebagian array) untuk menemukan elemen terkecil di setiap iterasi.
-
Kompleksitas Ruang: Selection Sort adalah algoritma in-place, yang berarti ia tidak memerlukan ruang tambahan yang signifikan selain ruang yang dibutuhkan untuk menyimpan array itu sendiri. Kompleksitas ruang Selection Sort adalah O(1), yang berarti konstan.
Kelebihan dan Kekurangan Selection Sort
Kelebihan:
- Sederhana dan Mudah Dipahami: Konsep Selection Sort sangat intuitif dan mudah diimplementasikan.
- In-place: Tidak memerlukan ruang memori tambahan yang signifikan.
- Performa Baik untuk Array Kecil: Meskipun kompleksitas waktu O(n^2), Selection Sort mungkin berkinerja baik untuk array dengan ukuran yang kecil.
- Jumlah Swap Minimal: Selection Sort melakukan jumlah swap yang minimal dibandingkan dengan algoritma pengurutan lain seperti Bubble Sort. Ini bisa menjadi keuntungan jika operasi swap sangat mahal.
Kekurangan:
- Tidak Efisien untuk Array Besar: Kompleksitas waktu O(n^2) membuat Selection Sort tidak praktis untuk array dengan ukuran yang besar.
- Tidak Stabil: Selection Sort tidak menjamin stabilitas pengurutan. Stabilitas berarti bahwa elemen dengan nilai yang sama akan mempertahankan urutan relatifnya setelah pengurutan.
- Kinerja Konsisten Buruk: Tidak ada perbedaan yang signifikan antara best, average, dan worst case, sehingga kinerjanya relatif tidak dapat diprediksi.
Kapan Menggunakan Selection Sort?
Mengingat kelebihan dan kekurangannya, Selection Sort paling cocok digunakan dalam situasi berikut:
- Ukuran Array Kecil: Ketika array yang akan diurutkan relatif kecil (misalnya, kurang dari 100 elemen).
- Memori Terbatas: Ketika ruang memori sangat terbatas dan tidak memungkinkan penggunaan algoritma pengurutan lain yang memerlukan ruang tambahan.
- Jumlah Swap Penting: Ketika meminimalkan jumlah operasi swap adalah prioritas utama.
Alternatif untuk Selection Sort
Untuk array yang lebih besar, algoritma pengurutan lain seperti Merge Sort (O(n log n)) atau Quick Sort (rata-rata O(n log n)) jauh lebih efisien. Namun, algoritma-algoritma ini lebih kompleks untuk diimplementasikan.
Selection Sort, meskipun sederhana, adalah algoritma fundamental yang penting untuk dipahami dalam dunia ilmu komputer. Memahami prinsip kerjanya, kelebihan, dan kekurangannya membantu Anda membuat keputusan yang lebih baik tentang algoritma pengurutan mana yang paling sesuai untuk situasi tertentu. Ingatlah bahwa pilihan algoritma pengurutan yang tepat sangat bergantung pada ukuran dataset, batasan memori, dan persyaratan kinerja aplikasi Anda. Sekarang, cobalah implementasikan Selection Sort dalam bahasa pemrograman lain dan eksperimen dengan dataset yang berbeda untuk lebih memperdalam pemahaman Anda!
