Selection Sort: Kode Program dan Penjelasannya
Algoritma pengurutan (sorting algorithm) memegang peranan krusial dalam dunia pemrograman. Dari mengurutkan data pelanggan dalam basis data, hingga menampilkan hasil pencarian secara terstruktur, algoritma pengurutan hadir di mana-mana. Salah satu algoritma pengurutan yang relatif sederhana dan mudah dipahami adalah Selection Sort. Meskipun performanya tidak secepat algoritma lain yang lebih canggih, Selection Sort menyediakan landasan yang baik untuk memahami konsep dasar pengurutan data. Dalam artikel ini, kita akan membahas secara mendalam tentang Selection Sort, termasuk prinsip kerjanya, kode program dalam beberapa bahasa pemrograman, dan analisis kelebihan serta kekurangannya.
Prinsip Kerja Selection Sort
Selection Sort bekerja dengan berulang kali mencari elemen terkecil (atau terbesar, tergantung urutan yang diinginkan) dari bagian array yang belum diurutkan, dan kemudian menukar elemen tersebut dengan elemen pertama dari bagian array tersebut. Proses ini diulang hingga seluruh array terurut. Secara sederhana, algoritma ini membagi array menjadi dua bagian: bagian yang sudah terurut di awal array dan bagian yang belum terurut di akhir array.
Berikut adalah langkah-langkah detail Selection Sort:
- Pencarian Minimum: Cari elemen terkecil dalam bagian array yang belum terurut.
- Pertukaran: Tukar elemen terkecil yang ditemukan dengan elemen pertama dari bagian array yang belum terurut. Ini menempatkan elemen terkecil pada posisinya yang benar dalam array yang sudah terurut.
- Iterasi: Ulangi langkah 1 dan 2 untuk bagian array yang belum terurut, dimulai dari elemen kedua, hingga seluruh array terurut.
Contoh ilustrasi:
Misalkan kita memiliki array [64, 25, 12, 22, 11].
- Iterasi 1: Elemen terkecil adalah 11. Tukar 64 dengan 11. Array menjadi
[11, 25, 12, 22, 64]. - Iterasi 2: Elemen terkecil dari
[25, 12, 22, 64]adalah 12. Tukar 25 dengan 12. Array menjadi[11, 12, 25, 22, 64]. - Iterasi 3: Elemen terkecil dari
[25, 22, 64]adalah 22. Tukar 25 dengan 22. Array menjadi[11, 12, 22, 25, 64]. - Iterasi 4: Elemen terkecil dari
[25, 64]adalah 25. Tidak ada pertukaran yang diperlukan. Array menjadi[11, 12, 22, 25, 64].
Array sekarang sudah terurut.
Kode Program Selection Sort
Berikut adalah implementasi Selection Sort dalam beberapa bahasa pemrograman populer:
1. Python:
def selection_sort(arr):
n = len(arr)
for i in range(n):
# Cari indeks elemen minimum di bagian array yang belum terurut
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 bagian array yang belum terurut
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# Contoh penggunaan
angka = [64, 25, 12, 22, 11]
angka_terurut = selection_sort(angka)
print(f"Array terurut: {angka_terurut}")Penjelasan Kode Python:
selection_sort(arr): Fungsi yang menerima arrayarrsebagai input.n = len(arr): Mendapatkan panjang array.for i in range(n): Looping utama yang mengiterasi melalui setiap elemen array.min_index = i: Menginisialisasi indeks elemen minimum dengan indeks elemen saat ini.for j in range(i+1, n): Looping dalam yang mencari elemen minimum di bagian array yang belum terurut.if arr[j] < arr[min_index]: Membandingkan elemen saat ini dengan elemen minimum yang ditemukan sebelumnya. Jika elemen saat ini lebih kecil, updatemin_index.arr[i], arr[min_index] = arr[min_index], arr[i]: Melakukan pertukaran elemen menggunakan teknik simultaneous assignment Python.return arr: Mengembalikan array yang sudah terurut.
2. Java:
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Cari indeks elemen minimum di bagian array yang belum terurut
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// Tukar elemen minimum dengan elemen pertama dari bagian array yang belum terurut
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] angka = {64, 25, 12, 22, 11};
selectionSort(angka);
System.out.println("Array terurut:");
for (int i = 0; i < angka.length; i++) {
System.out.print(angka[i] + " ");
}
}
}Penjelasan Kode Java:
selectionSort(int[] arr): Fungsi yang menerima array integerarrsebagai input.n = arr.length: Mendapatkan panjang array.for (int i = 0; i < n - 1; i++): Looping utama yang mengiterasi melalui setiap elemen array (kecuali elemen terakhir).min_idx = i: Menginisialisasi indeks elemen minimum dengan indeks elemen saat ini.for (int j = i + 1; j < n; j++): Looping dalam yang mencari elemen minimum di bagian array yang belum terurut.if (arr[j] < arr[min_idx]): Membandingkan elemen saat ini dengan elemen minimum yang ditemukan sebelumnya. Jika elemen saat ini lebih kecil, updatemin_idx.int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp;: Melakukan pertukaran elemen menggunakan variabel temporary.
3. C++:
#include <iostream>
#include <vector>
using namespace std;
void selectionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
// Cari indeks elemen minimum di bagian array yang belum terurut
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// Tukar elemen minimum dengan elemen pertama dari bagian array yang belum terurut
swap(arr[i], arr[min_idx]);
}
}
int main() {
vector<int> angka = {64, 25, 12, 22, 11};
selectionSort(angka);
cout << "Array terurut: ";
for (int i = 0; i < angka.size(); i++) {
cout << angka[i] << " ";
}
cout << endl;
return 0;
}Penjelasan Kode C++:
selectionSort(vector<int>& arr): Fungsi yang menerima vector integerarrsebagai input (passed by reference untuk memodifikasi array asli).n = arr.size(): Mendapatkan ukuran vector.for (int i = 0; i < n - 1; i++): Looping utama yang mengiterasi melalui setiap elemen array (kecuali elemen terakhir).min_idx = i: Menginisialisasi indeks elemen minimum dengan indeks elemen saat ini.for (int j = i + 1; j < n; j++): Looping dalam yang mencari elemen minimum di bagian array yang belum terurut.if (arr[j] < arr[min_idx]): Membandingkan elemen saat ini dengan elemen minimum yang ditemukan sebelumnya. Jika elemen saat ini lebih kecil, updatemin_idx.swap(arr[i], arr[min_idx]): Melakukan pertukaran elemen menggunakan fungsiswap()dari STL (Standard Template Library).
Kelebihan dan Kekurangan Selection Sort
Kelebihan:
- Sederhana dan Mudah Dipahami: Algoritma ini relatif mudah dipahami dan diimplementasikan, menjadikannya pilihan yang baik untuk mempelajari konsep dasar pengurutan.
- Minim Pertukaran: Selection Sort melakukan jumlah pertukaran yang relatif sedikit dibandingkan dengan algoritma lain seperti Bubble Sort. Ini bisa menjadi keuntungan jika operasi pertukaran memakan waktu yang signifikan.
- Bekerja dengan Baik untuk Ukuran Data Kecil: Untuk array dengan ukuran kecil, Selection Sort mungkin memiliki performa yang sebanding dengan algoritma lain yang lebih kompleks.
Kekurangan:
- Kompleksitas Waktu O(n^2): Selection Sort memiliki kompleksitas waktu kuadratik O(n^2) dalam semua kasus (terbaik, rata-rata, dan terburuk). Ini berarti performanya menurun secara signifikan seiring dengan bertambahnya ukuran data. Untuk array yang besar, algoritma ini menjadi sangat lambat.
- Tidak Efisien untuk Data Besar: Karena kompleksitas waktunya, Selection Sort tidak cocok untuk mengurutkan data dalam skala besar. Algoritma pengurutan lain seperti Merge Sort atau Quick Sort lebih efisien dalam kasus tersebut.
- Tidak Adaptif: Selection Sort tidak memanfaatkan fakta jika array sudah sebagian terurut. Ia akan tetap melakukan semua perbandingan dan pertukaran, bahkan jika array sudah hampir terurut sempurna.
Kapan Menggunakan Selection Sort?
Selection Sort sebaiknya digunakan dalam situasi berikut:
- Ukuran Data Kecil: Ketika Anda memiliki array dengan jumlah elemen yang sedikit.
- Sederhana Penting: Ketika prioritas utama adalah kemudahan implementasi dan pemahaman daripada performa optimal.
- Operasi Pertukaran Mahal: Ketika operasi pertukaran elemen sangat memakan waktu.
Sebaliknya, hindari penggunaan Selection Sort jika Anda berurusan dengan data berukuran besar atau membutuhkan performa pengurutan yang cepat. Pertimbangkan alternatif seperti Merge Sort, Quick Sort, atau algoritma pengurutan lainnya yang lebih efisien.
Selection Sort, meskipun sederhana, tetap menjadi alat yang berguna untuk memahami dasar-dasar pengurutan. Memahami cara kerjanya dan batasannya akan membantu Anda memilih algoritma pengurutan yang paling tepat untuk kebutuhan spesifik Anda. Ingatlah untuk selalu mempertimbangkan ukuran data dan prioritas performa ketika memilih algoritma pengurutan.
