Selection Sort Cara Kerja, Contoh, dan Implementasi

Selection Sort: Cara Kerja, Contoh, dan Implementasi

Selection Sort adalah salah satu algoritma pengurutan (sorting algorithm) yang sederhana dan mudah dipahami. Algoritma ini bekerja dengan cara mencari elemen terkecil (atau terbesar, tergantung urutan yang diinginkan) dari data yang belum terurut, kemudian menukarnya dengan elemen pada posisi pertama dari data yang belum terurut tersebut. Proses ini diulang hingga seluruh data terurut. Walaupun sederhana, Selection Sort bukanlah pilihan terbaik untuk dataset berukuran besar karena memiliki kompleksitas waktu yang kurang efisien dibandingkan algoritma pengurutan lainnya.

Cara Kerja Selection Sort: Langkah Demi Langkah

Inti dari Selection Sort adalah iterasi dan pencarian minimum (atau maksimum). Berikut langkah-langkahnya secara detail:

Mulai dari awal array: Algoritma memulai iterasi dari indeks pertama (biasanya indeks 0) array yang akan diurutkan.
Cari elemen minimum: Dalam iterasi saat ini, cari elemen terkecil dalam sisa array yang belum terurut. Misalkan, jika array kita adalah [64, 25, 12, 22, 11], pada iterasi pertama, kita akan mencari elemen terkecil mulai dari indeks 0. Elemen terkecil dalam kasus ini adalah 11, yang berada di indeks 4.
Tukar elemen minimum dengan elemen pertama yang belum terurut: Setelah elemen minimum ditemukan, tukar elemen tersebut dengan elemen pada posisi pertama dari sisa array yang belum terurut. Dalam contoh di atas, 11 (di indeks 4) akan ditukar dengan 64 (di indeks 0), sehingga array menjadi [11, 25, 12, 22, 64].
Ulangi langkah 2 dan 3: Ulangi langkah 2 dan 3 untuk sisa array yang belum terurut. Pada iterasi kedua, kita akan mencari elemen terkecil mulai dari indeks 1 (karena indeks 0 sudah terurut). Elemen terkecil adalah 12 (di indeks 2), yang akan ditukar dengan 25 (di indeks 1), menghasilkan [11, 12, 25, 22, 64].
Berhenti ketika seluruh array terurut: Proses ini diulang hingga seluruh array terurut. Setelah iterasi terakhir, array akan sepenuhnya terurut.

Contoh Implementasi Selection Sort

Berikut contoh implementasi Selection Sort menggunakan beberapa bahasa pemrograman:

Python:

def selection_sort(arr):
  n = len(arr)
  for i in range(n):
    min_idx = i
    for j in range(i+1, n):
      if arr[j] < arr[min_idx]:
        min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
  return arr

# Contoh penggunaan
data = [64, 25, 12, 22, 11]
sorted_data = selection_sort(data)
print("Array terurut:", sorted_data) # Output: Array terurut: [11, 12, 22, 25, 64]

Java:

public class SelectionSort {
  public static void selectionSort(int[] arr) {
    int n = arr.length;
    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;
    }
  }

  public static void main(String[] args) {
    int[] data = {64, 25, 12, 22, 11};
    selectionSort(data);
    System.out.print("Array terurut: ");
    for (int i = 0; i < data.length; i++) {
      System.out.print(data[i] + " ");
    } // Output: Array terurut: 11 12 22 25 64
  }
}

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;
      }
    }
    swap(arr[i], arr[min_idx]);
  }
}

int main() {
  int data[] = {64, 25, 12, 22, 11};
  int n = sizeof(data) / sizeof(data[0]);
  selectionSort(data, n);
  cout << "Array terurut: ";
  for (int i = 0; i < n; i++) {
    cout << data[i] << " ";
  } // Output: Array terurut: 11 12 22 25 64
  cout << endl;
  return 0;
}

Kode di atas menunjukkan implementasi Selection Sort dalam tiga bahasa pemrograman populer. Logika intinya sama: mencari elemen minimum dan menukarnya dengan elemen pada posisi yang sesuai.

Analisis Kompleksitas Waktu

Selection Sort memiliki kompleksitas waktu O(n²) dalam semua kasus (terbaik, rata-rata, dan terburuk). Ini karena algoritma harus melakukan iterasi melalui seluruh array untuk setiap elemen untuk menemukan elemen minimum. Oleh karena itu, Selection Sort kurang efisien untuk dataset berukuran besar.

Kelebihan dan Kekurangan Selection Sort

Kelebihan:

Sederhana dan mudah dipahami: Algoritma ini relatif mudah diimplementasikan dan dipahami, membuatnya cocok untuk pembelajaran dasar algoritma pengurutan.
Performa baik untuk dataset kecil: Untuk dataset yang sangat kecil, perbedaan performa dengan algoritma yang lebih kompleks mungkin tidak signifikan.
Jumlah pertukaran (swap) minimum: Selection Sort melakukan pertukaran elemen lebih sedikit dibandingkan beberapa algoritma pengurutan lainnya, yang bisa menjadi keuntungan dalam kasus di mana operasi pertukaran mahal.

Kekurangan:

Tidak efisien untuk dataset besar: Kompleksitas waktu O(n²) membuat Selection Sort tidak cocok untuk mengurutkan dataset berukuran besar.
Tidak adaptif: Algoritma ini tidak memanfaatkan fakta bahwa sebagian data mungkin sudah terurut. Ia selalu melakukan iterasi melalui seluruh array, bahkan jika data sudah hampir terurut.

Kapan Menggunakan Selection Sort?

Meskipun memiliki kekurangan dalam hal efisiensi, Selection Sort masih relevan dalam situasi tertentu:

Untuk tujuan pendidikan: Selection Sort adalah algoritma yang bagus untuk dipelajari sebagai pengantar algoritma pengurutan.
Untuk dataset kecil: Jika dataset yang akan diurutkan sangat kecil (misalnya, kurang dari 100 elemen), perbedaan performa dengan algoritma yang lebih kompleks mungkin tidak terlalu signifikan.
Ketika jumlah pertukaran harus diminimalkan: Jika operasi pertukaran elemen sangat mahal, Selection Sort mungkin menjadi pilihan yang baik karena melakukan lebih sedikit pertukaran dibandingkan algoritma lain seperti Bubble Sort atau Insertion Sort.

Alternatif untuk Selection Sort

Untuk dataset berukuran besar, ada banyak algoritma pengurutan yang lebih efisien daripada Selection Sort, antara lain:

Merge Sort: Kompleksitas waktu O(n log n), stabil, cocok untuk dataset besar.
Quick Sort: Kompleksitas waktu rata-rata O(n log n), efisien dalam praktiknya, tetapi kompleksitas waktu terburuk O(n²).
Heap Sort: Kompleksitas waktu O(n log n), efisien dan prediktif.

Pilihan algoritma pengurutan terbaik tergantung pada ukuran dataset, karakteristik data (misalnya, apakah data hampir terurut), dan persyaratan performa aplikasi.

Selection Sort merupakan algoritma pengurutan fundamental yang penting untuk dipelajari. Meskipun tidak seefisien algoritma lain untuk dataset besar, kesederhanaannya menjadikannya alat yang berharga untuk memahami konsep dasar pengurutan dan untuk kasus-kasus di mana efisiensi bukan prioritas utama. Memahami kelebihan dan kekurangan Selection Sort akan membantu Anda memilih algoritma pengurutan yang tepat untuk kebutuhan spesifik Anda. Dengan pemahaman yang kuat tentang prinsip-prinsip dasar ini, Anda akan lebih siap untuk menjelajahi algoritma dan struktur data yang lebih kompleks di masa depan.

Selection Sort Cara Kerja, Contoh, dan Implementasi

Comments

Tinggalkan Balasan Batalkan balasan