Algoritma Selection Sort adalah salah satu metode pengurutan sederhana dan klasik yang sering diajarkan dalam mata kuliah pengantar ilmu komputer. Meskipun tidak secepat algoritma pengurutan yang lebih kompleks seperti Quick Sort atau Merge Sort, Selection Sort memiliki konsep yang mudah dipahami dan diimplementasikan.
Artikel ini kita akan membahas secara mendalam tentang algoritma Selection Sort, cara kerjanya, kelebihan dan kekurangannya, serta contoh implementasinya dalam bahasa pemrograman.
Apa Algoritma Selection Sort?
Algoritma Selection Sort adalah algoritma pengurutan yang sederhana namun efisien, digunakan untuk mengurutkan elemen dalam sebuah array atau daftar. Algoritma ini bekerja dengan cara membagi array menjadi dua bagian: bagian yang terurut dan bagian yang tidak terurut. Algoritma kemudian secara bertahap memilih elemen terkecil (atau terbesar, tergantung kebutuhan) dari bagian yang tidak terurut dan menukarnya dengan elemen pertama dari bagian yang tidak terurut, hingga seluruh array terurut.
Sejarah Pengembangan
Algoritma Selection Sort pertama kali diperkenalkan pada tahun 1956 oleh ahli komputer J.W. Tukey. Meskipun bukan yang paling efisien untuk dataset besar, algoritma ini dikenal karena kesederhanaannya dan mudah dipahami, sehingga sering digunakan sebagai contoh pengantar dalam pengajaran algoritma dan struktur data.
Prinsip Kerja Selection Sort
Selection sort bekerja dengan prinsip dasar sebagai berikut:
- Cari Elemen Terkecil: Algoritma ini pertama-tama mencari elemen terkecil dalam daftar yang belum terurut.
- Tukar Elemen: Setelah menemukan elemen terkecil, algoritma menukarnya dengan elemen di posisi pertama dari daftar yang belum terurut.
- Perulangan: Langkah ini diulang untuk elemen kedua, ketiga, dan seterusnya, hingga seluruh daftar terurut.
Implementasi Algoritma Selection Sort
1. Pseudocode
Berikut adalah pseudocode dari algoritma Selection Sort:
SELECTION-SORT(A)
1. for i = 1 to length[A] - 1
2. smallest = i
3. for j = i + 1 to length[A]
4. if A[j] < A[smallest]
5. smallest = j
6. swap A[i] with A[smallest]2. Implementasi dalam Python
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr3. Implementasi dalam C++
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}Analisis Kompleksitas Waktu dan Ruang
Selection Sort memiliki kompleksitas waktu O(n^2) baik dalam kasus terbaik, rata-rata, maupun terburuk. Hal ini disebabkan oleh dua loop bersarang yang diperlukan untuk menyelesaikan pengurutan. Sedangkan untuk kompleksitas ruang, Selection Sort menggunakan ruang O(1), karena hanya memerlukan sejumlah kecil tambahan memori untuk variabel sementara.
Contoh Selection Sort
Mari kita lihat contoh bagaimana algoritma Selection Sort bekerja dengan daftar berikut: [64, 25, 12, 22, 11]
- Iterasi Pertama:
- Cari elemen terkecil di daftar [64, 25, 12, 22, 11]. Elemen terkecil adalah 11.
- Tukar 11 dengan elemen pertama (64), hasilnya: [11, 25, 12, 22, 64]
- Iterasi Kedua:
- Cari elemen terkecil di daftar yang belum diurutkan [25, 12, 22, 64]. Elemen terkecil adalah 12.
- Tukar 12 dengan elemen pertama dari bagian yang belum diurutkan (25), hasilnya: [11, 12, 25, 22, 64]
- Iterasi Ketiga:
- Cari elemen terkecil di daftar yang belum diurutkan [25, 22, 64]. Elemen terkecil adalah 22.
- Tukar 22 dengan elemen pertama dari bagian yang belum diurutkan (25), hasilnya: [11, 12, 22, 25, 64]
- Iterasi Keempat:
- Cari elemen terkecil di daftar yang belum diurutkan [25, 64]. Elemen terkecil adalah 25.
- Tidak perlu tukar karena 25 sudah berada di tempat yang benar.
- Iterasi Kelima:
- Elemen terakhir secara otomatis sudah diurutkan, hasil akhirnya: [11, 12, 22, 25, 64]
Contoh Penggunaan di Dunia Nyata
Selection Sort sering digunakan dalam situasi di mana jumlah data relatif kecil atau ketika kecepatan bukanlah faktor kritis. Contohnya termasuk pengurutan daftar peserta dalam acara kecil, pengurutan nama dalam buku telepon offline, atau pengurutan data statis yang tidak sering berubah.
Perbandingan dengan Algoritma Pengurutan Lainnya
1. Bubble Sort
Bubble Sort adalah algoritma pengurutan sederhana lainnya yang bekerja dengan cara membandingkan dan menukar elemen-elemen yang berdekatan. Meskipun lebih mudah diimplementasikan, Bubble Sort cenderung lebih lambat dibandingkan Selection Sort dalam banyak kasus.
2. Insertion Sort
Insertion Sort bekerja dengan cara membangun array terurut satu elemen pada satu waktu. Meskipun lebih efisien daripada Selection Sort dalam banyak kasus, terutama untuk dataset kecil atau sebagian terurut, kompleksitas waktu tetap O(n^2).
3. Merge Sort
Merge Sort adalah algoritma pengurutan yang lebih efisien dengan kompleksitas waktu O(n log n). Algoritma ini bekerja dengan cara membagi array menjadi sub-array lebih kecil, mengurutkan setiap sub-array, dan kemudian menggabungkannya kembali.
4. Quick Sort
Quick Sort juga memiliki kompleksitas waktu rata-rata O(n log n) dan bekerja dengan cara memilih elemen pivot dan membagi array menjadi dua bagian berdasarkan pivot tersebut. Quick Sort seringkali lebih cepat daripada Merge Sort dalam praktik.
Keuntungan dan Kelemahan
Keuntungan:
- Sederhana dan Mudah Dipahami: Algoritma selection sort sangat mudah dipahami dan diimplementasikan. Ini membuatnya cocok untuk digunakan dalam konteks pendidikan dan sebagai dasar untuk memahami algoritma pengurutan yang lebih kompleks.
- Tidak Membutuhkan Memori Tambahan: Algoritma ini bekerja di tempat, artinya tidak memerlukan memori tambahan selain daftar yang akan diurutkan. Ini menjadikannya algoritma dengan kompleksitas ruang O(1).
Kelemahan:
- Tidak Efisien untuk Daftar Besar: Dengan kompleksitas waktu O(n^2), selection sort menjadi tidak efisien untuk daftar yang besar. Algoritma ini akan memerlukan waktu yang cukup lama untuk mengurutkan daftar dengan banyak elemen.
- Tidak Stabil: Selection sort bukanlah algoritma yang stabil, yang berarti elemen dengan nilai yang sama bisa saja tidak mempertahankan urutan relatif mereka setelah pengurutan.
Aplikasi dalam Dunia Nyata
Meskipun selection sort tidak sering digunakan dalam aplikasi dunia nyata yang memerlukan pengurutan cepat, algoritma ini tetap memiliki beberapa kegunaan:
- Pengurutan Data yang Kecil: Untuk daftar dengan jumlah elemen yang relatif kecil, selection sort bisa menjadi pilihan yang baik karena kesederhanaan dan kemudahan implementasinya.
- Pengajaran dan Pembelajaran: Algoritma ini sering digunakan dalam konteks pendidikan untuk mengajarkan konsep dasar pengurutan dan algoritma.
- Kasus Khusus: Dalam beberapa kasus khusus di mana memori sangat terbatas dan pengurutan tidak perlu dilakukan dengan cepat, selection sort bisa menjadi solusi yang memadai.
Tips dan Trik dalam Menggunakan Selection Sort
1. Optimalisasi Kinerja
Meskipun Selection Sort tidak dapat dioptimalkan secara signifikan dari segi kompleksitas waktu, penggunaan batasan tertentu atau kombinasi dengan algoritma lain dalam kasus khusus dapat membantu meningkatkan kinerjanya.
2. Penggunaan dalam Kasus-Kasus Tertentu
Selection Sort ideal digunakan untuk dataset kecil, atau dalam situasi di mana algoritma yang lebih kompleks tidak diperlukan atau tidak tersedia.
Kesimpulan
Pada pembahasan kita di atas dapat disimpulkan bahwa Algoritma selection sort adalah salah satu algoritma pengurutan yang paling sederhana dan mudah dipahami. Dengan prinsip kerja yang jelas dan implementasi yang langsung, selection sort merupakan pilihan yang baik untuk daftar dengan jumlah elemen yang kecil atau dalam konteks pendidikan.
Meskipun tidak efisien untuk daftar yang besar karena kompleksitas waktunya yang O(n^2), selection sort tetap memiliki tempat dalam berbagai aplikasi khusus di mana kesederhanaan dan penggunaan memori yang minimal menjadi prioritas.
Artikel ini merupakan bagian seri artikel Programming dari KantinIT.com dan jika ada ide topik yang mau kami bahas silahkan komen di bawah ya..
