SELECTION SORT
A. Pengertian
Selection Sort merupakan sebuah algoritma pengurutan (sorting algoritma) yang bekerja
dengan cara berulang kali memilih elemen terkecil (atau terbesar, tergantung pada urutan yang
diinginkan) dari 1 bagian array yang belum diurutkan, kemudian menukar elemen tersebut
dengan elemen pertama dari bagian yang belum diurutkan. Proses ini diulang hingga seluruh
array terurut. Algoritma ini dikenal cukup sederhana dan mudah dipahami, meskipun
performanya tidak terlalu efisien untuk dataset yang besar.
B. Cara Kerja Selection Sort
Secara fundamental, Selection Sort melakukan pengurutan dengan membagi array menjadi
dua bagian: bagian yang sudah terurut (di sebelah kiri) dan bagian yang belum terurut (di
sebelah kanan). Pada setiap iterasi, algoritma akan mencari elemen minimum (atau
maksimum) dalam bagian yang belum terurut dan memindahkannya ke akhir bagian yang
sudah terurut.
1. Mencari Elemen Terkecil:
Pada setiap iterasi, algoritma akan mencari elemen terkecil dalam bagian daftar yang belum
diurutkan
2. Menukar:
Setelah elemen terkecil ditemukan, akan ditukarkan dengan elemen di posisi pertama dari
bagian yang belum diurutkan
3. Mengulangi:
Proses mencari elemen terkecil dan menukarnya diulangi untuk bagian daftar yang tersisa,
hingga seluruh daftar terurut
C. Langkah-langkah Algoritma Selection Sort
Misalkan kita memiliki sebuah array A dengan n elemen. Berikut adalah langkah-langkah
umum dari algoritma Selection Sort untuk mengurutkan array dalam urutan menaik:
1. Iterasi Pertama (i = 0):
➢ Cari elemen terkecil dalam seluruh array A (dari indeks 0 hingga n−1)
➢ Tukar elemen terkecil tersebut dengan elemen pada indeks 0 (A[0])
➢ Sekarang, elemen terkecil berada pada posisi pertama dan bagian array dari indeks 0
hingga 0 dianggap sudah terurut
2. Iterasi Kedua (i = 1):
➢ Cari elemen terkecil dalam bagian array yang belum terurut (dari indeks 1 hingga n−1)
➢ Tukar elemen terkecil tersebut dengan elemen pada indeks 1 (A[1])
➢ Sekarang, dua elemen pertama (A[0] dan A[1]) sudah terurut
3. Iterasi Ketiga (i = 2):
➢ Cari elemen terkecil dalam bagian array yang belum terurut (dari indeks 2 hingga n−1)
➢ Tukar elemen terkecil tersebut dengan elemen pada indeks 2 (A[2])
➢ Sekarang, tiga elemen pertama (A[0], A[1], dan A[2]) sudah terurut
4. Lanjutkan proses ini hingga iterasi ke-n−2:
➢ Pada iterasi ke-i, cari elemen terkecil dalam bagian array dari indeks i hingga n−1
➢ Tukar elemen terkecil tersebut dengan elemen pada indeks i (A[i])
➢ Setelah iterasi ke-n−2, dua elemen terakhir akan otomatis terurut
D. Contoh
Subdaftar Yang Tidak Elemen Terkecil Dalam
Subdaftar Yang Diurutkan Diurutkan Daftar Yang Tidak
Diurutkan
() (12, 25, 64, 11, 22) 11
(11) (25, 64, 12, 22) 12
(11, 12) (64, 25, 22) 22
(11, 12, 22) (25, 64) 25
(11, 12, 22, 25) (64) 64
(11, 12, 22, 25, 64) ()
E. Kelebihan Selection Sort:
➢ Sederhana dan mudah dipahami
➢ Tidak membutuhkan banyak ruang tambahan (O(1))
➢ Bekerja baik untuk daftar yang kecil hingga sedang
F. Kekurangan Selection Sort:
➢ Tidak efisien untuk daftar yang sangat besar (kompleksitas waktu O(n^2))
➢ Tidak stabil, artinya posisi elemen yang sama bisa berubah setelah pengurutan
G. Contoh Code dalam CPP
#include <iostream>
using namespace std;
void selection_sort(int a[], int length);
int main()
{
// A test array and array length
int a[] = {6, 3, 2, 4, 1, 5};
int length = 6;
// Call the function to perform the selection sort algorithm
selection_sort(a, length);
// Print out the array so we can be sure it is sorted correctly
for (int i = 0; i < length; i++)
{
cout << "a[" << i << "] = " << a[i] << endl;
}
return 0;
}
// Sorts array a with the provided length using the selection sort algorithm.
void selection_sort(int a[], int length)
{
// Loop through each index of the array, as we do so the elements < i are
// considered the sorted portion of the array, and the elements >= i are
// considered the unsorted portion of the array. The algorithm repeatedly
// finds the minimum element in the unsorted portion of the array and if
// necessary swaps it with the element at index i, increasing the portion
// of the sorted array with each iteration.
for (int i = 0; i < (length - 1); i++)
{
// find the position of the minimum element in the unsorted portion of
// the array
int min_pos = i;
for (int j = i + 1; j < length; j++)
{
if (a[j] < a[min_pos])
{
min_pos = j;
}
}
// if that element is NOT the element at index i, then swap that element
// with the element at index i
if (min_pos != i)
{
int temp = a[i];
a[i] = a[min_pos];
a[min_pos] = temp;
}
}
}
H. Output
a[0] = 1
a[1] = 2
a[2] = 3
a[3] = 4
a[4] = 5
a[5] = 6
I. Kesimpulan
Selection Sort adalah algoritma pengurutan yang sederhana dan intuitif. Kelebihannya terletak
pada kemudahannya dalam implementasi dan jumlah operasi penukaran (swap) yang relatif kecil
dibandingkan beberapa algoritma pengurutan lainnya. Namun, kompleksitas waktu rata-rata dan
kasus terburuknya adalah O(n2), di mana n adalah jumlah elemen dalam array. Hal ini
menjadikannya kurang efisien untuk dataset yang berukuran besar. Meskipun demikian, Selection
Sort tetap berguna dalam situasi di mana kesederhanaan kode lebih diutamakan daripada efisiensi
untuk dataset yang kecil.