By: Finn Christoffer K.

Fungsi sortir dapat digunakan untuk mengurutkan daftar dalam urutan naik, turun atau yang ditentukan pengguna. Tujuan utama dari proses sorting adalah untuk mengurutkan data, baik itu dari terendah ataupun tertinggi.  Yang secara tidak langsung akan menjadikan data lebih terstruktur, rapi dan teratur.

Ada banyak algoritma populer untuk mengurutkan data, seperti : insertion sort, selection sort, merge sort, heap sort, quick sort, bubble sort, shell sort, comb sort, counting sort, bucket sort, radix sort. Tapi di artikel ini saya hanya akan menyebutkan salah satu jenis algoritma sort yaitu Selection Sort.

Selection Sort adalah perbaikan dari algoritma bubble sort, dengan mengurangi jumlah perbandingan. Dikatakan selection sort karena algoritma ini mencoba memilih satu per satu elemen data dari posisi awal, untuk mencari data paling kecil dengan mencatat posisi index-nya saja, lalu dilakukan pertukaran hanya sekali pada akhir setiap tahapan.

Selection  sort merupakan  metode  pengurutan dengan mencari nilai data terkecil dimulai dari data diposisi 0 hingga diposisi N-1. Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode selection sortadalah sebagai berikut:

  1. Cari data terkecil dalam interval  j= 0 sampai dengan j= N-1
  2. Jika pada posisi  pos ditemukan data yang terkecil, tukarkan data diposisi  pos dengan data di posisi  i jika k.
  3. Ulangi langkah 1 dan 2 dengan j= j+isampai dengan j= N-1, dan seterusnya sampai  j = N

Jika kita memiliki elemen array :  {5, 1, 12, -5, 16, 2, 12, 14} maka cara pengurutannya

Berikut ini implementasi algoritma selection sort dalam Bahasa pemrograman Python:

Ketika program tersebut dijalankan, berikut ini hasil outputnya:

Analisis Kompleksitas Waktu dan Ruang

Selection Sort memiliki kompleksitas waktu sebesar O(n^2) baik pada kasus terbaik, kasus rata-rata, maupun kasus terburuk. Hal ini disebabkan oleh dua loop bersarang yang masing-masing berjalan sebanyak n kali. Meskipun Selection Sort tidak efisien untuk daftar yang sangat besar, algoritma ini memiliki beberapa kelebihan, seperti kesederhanaan dan kemudahan implementasi.

Kompleksitas ruang dari Selection Sort adalah O(1), karena algoritma ini hanya membutuhkan ruang tambahan yang konstan untuk variabel temporer dalam proses penukaran elemen.

Baca juga: Analisis Performa Algoritma Backpropagation Jaringan Syaraf Tiruan

Kelebihan dan Kekurangan Selection Sort

Kelebihan:

  1. Sederhana dan Mudah Dipahami: Algoritma ini mudah untuk diimplementasikan dan dipahami, sehingga cocok untuk pemula yang baru belajar tentang algoritma pengurutan.
  2. Tidak Bergantung pada Urutan Awal: Selection Sort akan memiliki kompleksitas waktu yang sama tidak peduli bagaimana urutan awal data yang akan diurutkan.
  3. Sedikit Pertukaran: Dibandingkan dengan algoritma lain seperti Bubble Sort, Selection Sort melakukan lebih sedikit pertukaran elemen.

Kekurangan:

  1. Tidak Efisien untuk Daftar Besar: Dengan kompleksitas waktu O(n^2), Selection Sort tidak cocok untuk mengurutkan daftar yang sangat besar.
  2. Tidak Stabil: Selection Sort bukan algoritma pengurutan yang stabil. Jika terdapat elemen-elemen yang memiliki nilai yang sama, urutan relatif mereka mungkin tidak dipertahankan setelah pengurutan.

Perbandingan dengan Algoritma Pengurutan Lain

Untuk memahami posisi Selection Sort dalam konteks algoritma pengurutan lainnya, mari kita bandingkan dengan beberapa algoritma pengurutan yang umum digunakan:

  1. Bubble Sort: Bubble Sort juga memiliki kompleksitas waktu O(n^2) dan sederhana seperti Selection Sort. Namun, Selection Sort biasanya lebih cepat dalam praktik karena melakukan lebih sedikit pertukaran.
  2. Insertion Sort: Insertion Sort juga memiliki kompleksitas waktu O(n^2) pada kasus terburuk, tetapi lebih efisien daripada Selection Sort pada kasus terbaik (O(n)) dan pada data yang hampir terurut.
  3. Merge Sort dan Quick Sort: Kedua algoritma ini memiliki kompleksitas waktu rata-rata O(n log n), yang jauh lebih efisien dibandingkan Selection Sort. Namun, implementasi Merge Sort dan Quick Sort lebih kompleks.

Modifikasi dan Optimasi

Ada beberapa cara untuk memodifikasi dan mengoptimalkan Selection Sort. Salah satu optimasi sederhana adalah dengan menghentikan algoritma jika tidak ada pertukaran yang terjadi dalam satu iterasi, meskipun ini tidak memberikan banyak manfaat karena Selection Sort memang dirancang untuk selalu mencari elemen terkecil pada setiap iterasi.