Selection Sort: Menjelajahi Algoritma Pengurutan Sederhana Namun Powerful
Selection Sort, algoritma pengurutan yang mungkin kurang populer dibandingkan Quick Sort atau Merge Sort, tetap menjadi fondasi penting dalam pemahaman algoritma pengurutan. Ia menawarkan keunggulan dalam kesederhanaan dan kemudahan implementasi, membuatnya ideal untuk pembelajaran dasar dan situasi tertentu di mana efisiensi bukanlah prioritas utama. Artikel ini akan membongkar Selection Sort secara mendalam, mulai dari teori dasarnya, cara kerjanya, kelebihan dan kekurangannya, hingga contoh implementasi nyata dalam kode.
Memahami Konsep Dasar Selection Sort
Selection Sort adalah algoritma pengurutan in-place, yang berarti ia mengurutkan elemen-elemen secara langsung di dalam array asli tanpa memerlukan ruang memori tambahan yang signifikan. Cara kerjanya cukup intuitif: algoritma ini secara berulang mencari elemen terkecil (atau terbesar, tergantung pada urutan yang diinginkan) dari bagian array yang belum diurutkan, dan menukarnya dengan elemen pertama dari bagian tersebut. Proses ini diulang untuk sisa array yang belum diurutkan, sehingga secara bertahap membangun bagian array yang sudah terurut di awal.
Bayangkan Anda memiliki tumpukan kartu yang belum diurutkan. Selection Sort akan bekerja seperti ini:
- Cari Minimum: Cari kartu dengan nilai terkecil di seluruh tumpukan.
- Tukar: Tukar kartu terkecil ini dengan kartu yang berada di posisi paling atas tumpukan.
- Ulangi: Sekarang, anggap kartu paling atas sudah terurut. Ulangi langkah 1 dan 2 untuk sisa tumpukan kartu (mulai dari kartu kedua).
- Selesai: Terus ulangi hingga seluruh tumpukan kartu terurut.
Cara Kerja Selection Sort: Tahapan Demi Tahapan
Untuk lebih memahami cara kerja Selection Sort, mari kita ilustrasikan dengan contoh array: [64, 25, 12, 22, 11].
-
Iterasi Pertama:
- Cari elemen terkecil di seluruh array. Dalam hal ini, elemen terkecil adalah 11 (berada di indeks 4).
- Tukar 11 dengan elemen pertama (64). Array menjadi:
[11, 25, 12, 22, 64]. Sekarang, elemen pertama (11) sudah terurut.
-
Iterasi Kedua:
- Cari elemen terkecil di antara elemen yang belum diurutkan (mulai dari indeks 1 hingga indeks 4). Elemen terkecil adalah 12 (berada di indeks 2).
- Tukar 12 dengan elemen kedua (25). Array menjadi:
[11, 12, 25, 22, 64]. Sekarang, elemen pertama dan kedua sudah terurut.
-
Iterasi Ketiga:
- Cari elemen terkecil di antara elemen yang belum diurutkan (mulai dari indeks 2 hingga indeks 4). Elemen terkecil adalah 22 (berada di indeks 3).
- Tukar 22 dengan elemen ketiga (25). Array menjadi:
[11, 12, 22, 25, 64]. Sekarang, elemen pertama, kedua, dan ketiga sudah terurut.
-
Iterasi Keempat:
- Cari elemen terkecil di antara elemen yang belum diurutkan (mulai dari indeks 3 hingga indeks 4). Elemen terkecil adalah 25 (berada di indeks 3).
- Karena elemen terkecil sudah berada di posisi yang benar, tidak perlu dilakukan penukaran. Array tetap:
[11, 12, 22, 25, 64]. Sekarang, elemen pertama, kedua, ketiga, dan keempat sudah terurut.
-
Selesai: Seluruh array sudah terurut.
Implementasi Selection Sort dalam Kode (Python)
Berikut adalah contoh implementasi Selection Sort dalam bahasa pemrograman Python:
def selection_sort(arr):
"""Mengurutkan array menggunakan algoritma Selection Sort."""
n = len(arr)
for i in range(n-1):
# Cari indeks elemen minimum di sisa array yang belum diurutkan
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
# Tukar elemen minimum dengan elemen pertama dari sisa array
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# Contoh penggunaan
data = [64, 25, 12, 22, 11]
data_terurut = selection_sort(data)
print("Array terurut:", data_terurut) # Output: Array terurut: [11, 12, 22, 25, 64]Kode di atas mengilustrasikan dengan jelas langkah-langkah yang telah dijelaskan sebelumnya. Loop luar (for i in range(n-1)) melakukan iterasi melalui setiap posisi dalam array, kecuali yang terakhir (karena elemen terakhir akan otomatis terurut setelah elemen-elemen sebelumnya terurut). Loop dalam (for j in range(i+1, n)) mencari indeks elemen minimum dalam sisa array yang belum diurutkan. Setelah elemen minimum ditemukan, ia ditukar dengan elemen di posisi i.
Kelebihan dan Kekurangan Selection Sort
Seperti semua algoritma, Selection Sort memiliki kelebihan dan kekurangan yang perlu dipertimbangkan:
Kelebihan:
- Sederhana dan Mudah Diimplementasikan: Konsepnya mudah dipahami dan implementasinya cukup sederhana, menjadikannya ideal untuk belajar algoritma dasar.
- Minim Pertukaran: Selection Sort melakukan jumlah pertukaran yang relatif sedikit dibandingkan algoritma pengurutan lainnya. Ini bisa menjadi keuntungan jika operasi pertukaran mahal (misalnya, ketika menulis ke memori flash).
- In-Place: Tidak memerlukan memori tambahan yang signifikan untuk melakukan pengurutan.
Kekurangan:
- Inefisien untuk Data Besar: Kompleksitas waktu Selection Sort adalah O(n^2), membuatnya kurang efisien untuk array dengan ukuran besar. Waktu eksekusinya meningkat secara kuadratik dengan ukuran input.
- Tidak Adaptif: Selection Sort melakukan jumlah perbandingan yang sama, terlepas dari apakah data sudah hampir terurut atau tidak. Ini berarti tidak ada keuntungan yang diperoleh dari input yang sudah sebagian terurut.
Kapan Selection Sort Cocok Digunakan?
Meskipun kurang efisien untuk data besar, Selection Sort dapat berguna dalam situasi berikut:
- Ukuran Data Kecil: Untuk array dengan ukuran yang sangat kecil (misalnya, kurang dari 100 elemen), perbedaan kinerja antara Selection Sort dan algoritma yang lebih kompleks mungkin tidak signifikan.
- Operasi Pertukaran Mahal: Jika operasi pertukaran elemen sangat mahal (misalnya, karena keterbatasan hardware), Selection Sort bisa menjadi pilihan yang lebih baik daripada algoritma yang melakukan banyak pertukaran.
- Kejelasan dan Kesederhanaan: Ketika kode yang mudah dipahami dan dipelihara lebih penting daripada kinerja optimal, Selection Sort dapat menjadi pilihan yang tepat. Misalnya, dalam aplikasi pendidikan atau prototipe cepat.
Implementasi Nyata: Contoh Kasus Sederhana
Meskipun Selection Sort jarang digunakan dalam aplikasi produksi skala besar, berikut adalah contoh kasus sederhana di mana ia mungkin relevan:
- Mengurutkan Daftar Skor Tinggi dalam Game Sederhana: Dalam game sederhana dengan daftar skor tinggi yang relatif kecil, Selection Sort dapat digunakan untuk mengurutkan skor-skor tersebut.
- Memilih Beberapa Elemen Terkecil dari Kumpulan Data Kecil: Selection Sort dapat dimodifikasi untuk menemukan k elemen terkecil dalam array tanpa harus mengurutkan seluruh array. Ini bisa berguna dalam aplikasi di mana hanya sebagian kecil data yang diperlukan.
- Sorting di Embedded System dengan Memori Terbatas: Pada sistem embedded dengan keterbatasan memori, algoritma in-place seperti Selection Sort mungkin menjadi pilihan yang lebih baik daripada algoritma yang membutuhkan memori tambahan.
Selection Sort, dengan kesederhanaannya, menyediakan landasan yang kuat untuk memahami algoritma pengurutan yang lebih kompleks. Pemahaman yang mendalam tentang kelebihan dan kekurangannya memungkinkan kita untuk membuat keputusan yang tepat dalam memilih algoritma yang paling sesuai untuk kebutuhan spesifik kita.
