Panduan Praktis Selection Sort Implementasi di Python

Selection Sort: Konsep Dasar dan Cara Kerjanya

Selection Sort adalah algoritma pengurutan sederhana yang bekerja dengan berulang kali mencari elemen minimum (atau maksimum, tergantung urutan yang diinginkan) dari bagian array yang belum diurutkan, dan menukarnya dengan elemen pertama dari bagian yang belum diurutkan itu. Proses ini diulang untuk sisa bagian array hingga seluruh array terurut. Secara konseptual, algoritma ini mudah dipahami, tetapi efisiensinya tidak sebanding dengan algoritma pengurutan yang lebih canggih seperti Merge Sort atau Quick Sort, terutama untuk dataset berukuran besar. Namun, Selection Sort tetap relevan sebagai fondasi pembelajaran algoritma dan dalam situasi tertentu di mana simplisitas lebih diutamakan daripada kecepatan.

Implementasi Selection Sort dengan Python: Langkah Demi Langkah

Untuk mengimplementasikan Selection Sort dalam Python, kita membutuhkan dua loop bersarang. Loop luar berjalan dari indeks 0 hingga n-2 (di mana n adalah panjang array), sementara loop dalam mencari elemen minimum dari bagian array yang belum diurutkan, dimulai dari indeks i+1 (di mana i adalah indeks loop luar). Berikut adalah kode Python yang menunjukkan implementasi Selection Sort:

def selection_sort(data):
  """
  Mengurutkan list menggunakan algoritma Selection Sort.

  Args:
    data: List yang akan diurutkan.

  Returns:
    List yang sudah diurutkan.
  """
  n = len(data)
  for i in range(n-1):
    # Mencari indeks elemen minimum di sisa array
    min_idx = i
    for j in range(i+1, n):
      if data[j] < data[min_idx]:
        min_idx = j

    # Menukar elemen minimum dengan elemen pertama di sisa array
    data[i], data[min_idx] = data[min_idx], data[i]

  return data

# Contoh Penggunaan
angka = [64, 25, 12, 22, 11]
angka_terurut = selection_sort(angka)
print("Array yang diurutkan:", angka_terurut)  # Output: Array yang diurutkan: [11, 12, 22, 25, 64]

Dalam kode di atas:

1. Fungsi selection_sort(data) menerima sebuah list data sebagai input.
2. Loop luar for i in range(n-1) mengiterasi setiap elemen dalam array, kecuali elemen terakhir (karena setelah n-1 iterasi, elemen terakhir otomatis akan berada di posisi yang benar).
3. Variabel min_idx menyimpan indeks elemen minimum yang ditemukan di sisa array yang belum diurutkan. Awalnya, min_idx diinisialisasi dengan nilai i.
4. Loop dalam for j in range(i+1, n) membandingkan setiap elemen di sisa array dengan elemen di indeks min_idx. Jika ditemukan elemen yang lebih kecil, min_idx diperbarui.
5. Setelah loop dalam selesai, min_idx akan berisi indeks elemen minimum di sisa array.
6. data[i], data[min_idx] = data[min_idx], data[i] melakukan pertukaran (swap) antara elemen di indeks i dengan elemen di indeks min_idx. Dengan demikian, elemen minimum ditempatkan di posisi yang benar.
7. Setelah loop luar selesai, seluruh array akan terurut.

Analisis Kompleksitas Waktu dan Ruang Selection Sort

Selection Sort memiliki kompleksitas waktu O(n^2) dalam semua kasus (terbaik, rata-rata, dan terburuk). Hal ini disebabkan oleh loop bersarang yang selalu membandingkan setiap elemen dengan elemen lainnya, terlepas dari urutan awal array. Kompleksitas ruang Selection Sort adalah O(1), yang berarti algoritma ini membutuhkan ruang tambahan konstan. Ini menjadikannya algoritma in-place, yang artinya pengurutan dilakukan langsung di dalam array input tanpa memerlukan array tambahan yang signifikan.

Kelebihan dan Kekurangan Selection Sort

Kelebihan:

• Sederhana dan mudah diimplementasikan: Konsep Selection Sort mudah dipahami dan kode implementasinya relatif singkat.
• In-place: Algoritma ini tidak memerlukan ruang memori tambahan yang signifikan, menjadikannya efisien dalam penggunaan memori.
• Jumlah pertukaran minimal: Selection Sort melakukan jumlah pertukaran yang relatif sedikit dibandingkan algoritma pengurutan lainnya. Dalam beberapa kasus, ini bisa menjadi keuntungan jika operasi pertukaran mahal.

Kekurangan:

• Tidak efisien untuk dataset besar: Kompleksitas waktu O(n^2) membuatnya tidak cocok untuk mengurutkan dataset berukuran besar.
• Tidak adaptif: Kinerja Selection Sort tidak dipengaruhi oleh urutan awal array. Bahkan jika array sudah hampir terurut, algoritma tetap akan melakukan sejumlah perbandingan yang sama.
• Kurang stabil: Selection Sort bukan algoritma pengurutan yang stabil. Ini berarti bahwa elemen-elemen dengan nilai yang sama mungkin tidak mempertahankan urutan relatifnya setelah pengurutan.

Kapan Sebaiknya Menggunakan Selection Sort?

Meskipun memiliki kompleksitas waktu yang kurang baik, Selection Sort masih bisa berguna dalam beberapa situasi:

• Dataset berukuran kecil: Untuk dataset dengan jumlah elemen yang sedikit (misalnya, kurang dari 100 elemen), perbedaan kinerja antara Selection Sort dan algoritma pengurutan yang lebih canggih mungkin tidak signifikan.
• Keterbatasan memori: Jika memori sangat terbatas, Selection Sort bisa menjadi pilihan yang baik karena merupakan algoritma in-place.
• Jumlah pertukaran minimal: Jika operasi pertukaran elemen mahal, Selection Sort bisa lebih efisien daripada algoritma yang melakukan lebih banyak pertukaran.
• Tujuan pembelajaran: Selection Sort merupakan algoritma pengurutan yang baik untuk dipelajari sebagai pengantar algoritma pengurutan.

Alternatif Selain Selection Sort

Untuk dataset yang lebih besar, disarankan untuk menggunakan algoritma pengurutan yang lebih efisien seperti:

• Merge Sort: Memiliki kompleksitas waktu O(n log n) dan merupakan algoritma yang stabil.
• Quick Sort: Memiliki kompleksitas waktu rata-rata O(n log n), tetapi kompleksitas waktu terburuk O(n^2). Merupakan algoritma yang sangat cepat dalam praktiknya.
• Heap Sort: Memiliki kompleksitas waktu O(n log n) dan merupakan algoritma in-place.

Kesimpulan

Selection Sort adalah algoritma pengurutan yang sederhana dan mudah dipahami, tetapi tidak efisien untuk dataset besar karena kompleksitas waktunya yang O(n^2). Meskipun demikian, algoritma ini masih relevan dalam situasi tertentu di mana simplisitas dan penggunaan memori yang minimal lebih diutamakan daripada kecepatan. Memahami konsep Selection Sort adalah langkah penting dalam mempelajari algoritma pengurutan yang lebih canggih dan kompleks. Apakah Anda akan menggunakan Selection Sort dalam proyek Anda, atau memilih algoritma lain yang lebih efisien, pemahaman yang baik tentang Selection Sort akan membantu Anda membuat keputusan yang lebih tepat.