Algoritma Selection Sort

Selection Sort merupakan salah satu algoritma pengurutan yang sederhana. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending (menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian ditukar.

Selection Sort diakui karena kesederhanaan algoritmanya dan performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi tertentu. Algoritma ini bekerja sebagai berikut:

1. Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list
2. Menukarkan nilai ini dengan elemen pertama list
3. Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua

Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan.



contoh simulasi algoritma selection sort sbb :
jika kita memiliki elemen array sbb :  {5, 1, 12, -5, 16, 2, 12, 14}

Algoritma pengurutan selection sort ini termasuk algoritma sulit dibagi/ mudah digabung (hard split/easy join).  Dari proses pengurutannya, Selection sort ini memiliki dua buah varian yaitu :

1. Maximum Sort

memilih data yang maksimum dari suatu kumpulan data larik, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data maksimum berikutnya.

2. Minimum Sort

memilih data yang minimum dari suatu kumpulan data larik , lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data minimum berikutnya.

Dalam pemecahan masalah algoritma selection sort , kita dapat memilih dua metode alternatif algoritma antara lain pemecahan dengan metode Brute Force dan pemecahan dengan metode devide and conquer.

Metode Pemecahan Brute Force

Kekuatan algoritma brute force terletak pada kemampuannya untuk menemukan semua pemecahan masalah yang mungkin, akan tetapi langkah yang dibutuhkan sangat banyak sehingga tidak baik jika digunakan untuk memecahkan masalah yang memiliki masukan yang cukup besar.