Selection sort adalah algoritma sorting intuitif: kita membagi array menjadi bagian terurut (kiri) dan tidak terurut (kanan). Pada setiap iterasi, kita cari elemen terkecil di bagian tidak terurut, lalu tukar dengan elemen pertama bagian tidak terurut. Walaupun kompleksitasnya sama dengan bubble sort (O(n^2)), selection sort melakukan jauh lebih sedikit pertukaran—paling banyak n-1 swap, terlepas dari distribusi data. Pada chapter ini kita akan mengimplementasikan selection sort dan menghitung jumlah perbandingan serta pertukaran untuk memahami keunggulannya.

Cara Kerja Selection Sort #

Algoritma menjaga indeks i yang menandai batas antara bagian terurut (sebelum i) dan bagian tidak terurut (i hingga n-1). Pada setiap iterasi:

  1. Cari indeks min_idx dari elemen terkecil pada rentang i..n-1.
  2. Tukar a[i] dengan a[min_idx].
  3. Naikkan i sebanyak satu.

Loop luar berjalan n-1 kali. Loop dalam yang mencari minimum berjalan (n-1) + (n-2) + ... + 1 = n(n-1)/2 kali—selalu sama, terlepas dari data. Total perbandingan: n(n-1)/2 = O(n^2). Total pertukaran: paling banyak n-1 swap. Inilah perbedaan utama dengan bubble sort yang bisa melakukan O(n^2) swap pada worst case.

Implementasi Dasar #

c 
#include <stdio.h>

/* Selection sort: cari minimum, tukar ke depan */
void selection_sort(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            int t = a[i]; a[i] = a[min_idx]; a[min_idx] = t;
        }
    }
}

static void cetak(const int *a, int n) {
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

int main(void) {
    int a[] = {64, 25, 12, 22, 11, 9, 78, 3};
    int n = sizeof(a) / sizeof(a[0]);

    printf("Sebelum: ");
    cetak(a, n);

    selection_sort(a, n);

    printf("Setelah: ");
    cetak(a, n);

    return 0;
}

Output yang Dihasilkan:

text 
Sebelum: 64 25 12 22 11 9 78 3 
Setelah: 3 9 11 12 22 25 64 78

Array terurut menaik. Selection sort tidak stabil pada implementasi standar karena swap a[i] dengan a[min_idx] dapat mengubah urutan relatif elemen yang sama nilainya.

Mari kita telaah baris-baris kode di atas:

  1. Baris 5 (for (int i = 0; i < n - 1; i++)): loop luar berjalan n-1 kali. Setelah n-1 iterasi, elemen terakhir pasti sudah di posisi yang benar karena semua elemen sebelumnya sudah lebih kecil.
  2. Baris 6 (int min_idx = i;): inisialisasi min_idx ke indeks awal bagian tidak terurut. Asumsi: elemen pertama adalah minimum sampai dibuktikan lain.
  3. Baris 7-9 (for (int j = i + 1; ...) if (a[j] < a[min_idx])): cari elemen terkecil di rentang i+1..n-1. Bila ketemu yang lebih kecil, update min_idx.
  4. Baris 11-13 (if (min_idx != i) { swap }): tukar a[i] dengan a[min_idx] hanya bila minimum tidak berada di posisi i. Cek ini menghemat satu swap sia-sia saat elemen pertama sudah minimum.
  5. Baris 21 (cetak(a, n);): cetak array sebelum dan sesudah sorting untuk verifikasi.

Menghitung Perbandingan dan Pertukaran #

Kita akan membandingkan jumlah perbandingan dan pertukaran pada tiga skenario data untuk memahami karakteristik selection sort.

c 
#include <stdio.h>

/* Selection sort dengan penghitung perbandingan dan pertukaran */
void selection_count(int *a, int n, long long *jumlah_banding,
                     long long *jumlah_tukar) {
    *jumlah_banding = 0;
    *jumlah_tukar = 0;
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            (*jumlah_banding)++;
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            int t = a[i]; a[i] = a[min_idx]; a[min_idx] = t;
            (*jumlah_tukar)++;
        }
    }
}

int main(void) {
    int a1[] = {64, 25, 12, 22, 11};
    int a2[] = {1, 2, 3, 4, 5};
    int a3[] = {5, 4, 3, 2, 1};
    int n = 5;

    long long banding, tukar;

    selection_count(a1, n, &banding, &tukar);
    printf("Acak    : banding=%lld, tukar=%lld\n", banding, tukar);

    selection_count(a2, n, &banding, &tukar);
    printf("Terurut : banding=%lld, tukar=%lld\n", banding, tukar);

    selection_count(a3, n, &banding, &tukar);
    printf("Terbalik: banding=%lld, tukar=%lld\n", banding, tukar);

    return 0;
}

Output yang Dihasilkan:

text 
Acak    : banding=10, tukar=3
Terurut : banding=10, tukar=0
Terbalik: banding=10, tukar=2

Pengamatan penting:

  • Perbandingan selalu 10: pada n=5, rumus n(n-1)/2 = 5*4/2 = 10. Jumlah perbandingan tidak bergantung pada konten data—selalu sama.
  • Pertukaran bervariasi: data terurut tidak melakukan swap apapun; data terbalik hanya butuh 2 swap. Maksimum n-1 = 4 swap.

Inilah keunggulan selection sort dibanding bubble sort: bila biaya swap mahal (misal pada struct besar), selection sort jauh lebih hemat.

Kapan Selection Sort Cocok Dipakai #

Selection sort cocok pada situasi berikut:

  • Biaya swap tinggi: jumlah swap maksimal n-1, jauh lebih sedikit dari bubble sort.
  • Memori sangat terbatas: algoritma in-place dengan O(1) ruang tambahan.
  • Prediktabilitas penting: jumlah perbandingan selalu sama, sehingga waktu eksekusi mudah diprediksi.

Sebaliknya, selection sort tidak cocok bila:

  • Data besar (n > 100): kompleksitas O(n^2) lambat dibanding O(n log n) dari merge sort.
  • Stability diperlukan: implementasi standar tidak stabil.
  • Data hampir terurut: tidak ada optimisasi early exit seperti bubble sort.