Selection Sort

Tipe algoritma brute force lainnya dalam pengurutan data adalah selection sort. 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.

Algoritma Selection Sort dilakukan untuk menyempurnakan kekurangan dari bubble sort yang melakukan pertukaran setiap kali perbandingan memenuhi kriterianya.

Gambar: Hasil running

Algoritma dari selection sort adalah sebagai berikut:

1. inisialisasi n adalah ukuran data, pada contoh di atas n = 7 
2. inisialisasi i ← 1 sebagai awal proses.
3. kecil ← i  { asumsi awal, posisi ke-i lah yang paling kecil, garis merah pada gambar di atas }.
4. j ← i + 1  { j adalah posisi data pembanding, garis hitam pada gambar di atas }
5. Jika Data j < Data kecil, maka posisi ke-j lebih kecil, lalu ubah posisi index, kecil  ← j   
6. j ← j + 1
7. Jika j = n { perbandingan sudah sampai index terakhir } maka lanjut ke baris 8, jika tidak ulang ke baris 5.
8. lakukan pertukaran Data-i  dengan Data-terkecil (garis merah dengan garis biru pada gambar di atas).
9. i  ← i + 1 { perubahan tiap tahap, garis merah bergeser pada tiap tahapan } 
10. Ulang ke baris ke-3 selama i < n - 1
11. Selesai .

Gambar: Algoritma Selection Sort dalam bentuk pseudo code

Dari penjelasan di atas dapat disimpulkan bahwa algoritma selection sort mempunyai kompleksitas perbandingan sebanyak n-1 faktorial tetapi kompleksitas pertukarannya = n-1 saja, sedangkan bubble sort mempunyai kompleksitas perbandingan dan pertukaran yang sama yaitu sebanyak n-1. Bila data n=7 seperti contoh running di atas, maka faktorial n-1 = { 1 x 2 x 3 x 4 x 5 x 6 }. 

Kode program: Bahasa C++