Selection Sort

Selection sort memilih elemen terkecil yang tersisa lalu menempatkannya pada posisi yang benar. Berbeda dengan bubble sort yang banyak menukar elemen bertetangga, selection sort hanya melakukan paling banyak n-1 pertukaran — sebuah keunggulan saat pertukaran elemen mahal (misalnya pada struct besar atau I/O). Pada Chapter ini kita akan membedah mekanisme selection sort, mengimplementasikannya dalam C++, dan menjelaskan mengapa algoritma ini tidak stabil dalam bentuk klasiknya. Pada akhir chapter kita akan tahu kapan selection sort unggul (jumlah swap minimum) dan kapan harus dihindari (selalu O(n²) terlepas dari distribusi data).

Aturan: Pilih Minimum, Tukar ke Depan #

Pada setiap iterasi i dari 0 hingga n-2:

1. Cari indeks elemen terkecil pada subarray v[i..n-1].
2. Tukar elemen pada indeks tersebut dengan v[i].

Setelah iterasi ke-i selesai, elemen v[0..i] sudah berisi i+1 elemen terkecil dalam urutan benar.

Mekanisme Kerja #

Total dibutuhkan tepat n-1 = 4 iterasi untuk n=5. Setiap iterasi melakukan satu pertukaran (atau tidak sama sekali bila minimum sudah pada posisi benar).

Kode: Selection Sort #

#include <iostream>
#include <vector>
#include <utility>

void selection_sort(std::vector<int>& v, int& swaps) {
    int n = static_cast<int>(v.size());
    swaps = 0;
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (v[j] < v[min_idx]) min_idx = j;
        }
        if (min_idx != i) {
            std::swap(v[i], v[min_idx]);
            ++swaps;
        }
    }
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {29, 10, 14, 37, 13};
    int swaps;
    selection_sort(a, swaps);
    std::cout << "Hasil:   "; print(a);
    std::cout << "  swaps = " << swaps << '\n';

    std::vector<int> b = {4, 2, 4, 1, 3};
    selection_sort(b, swaps);
    std::cout << "Hasil:   "; print(b);
    std::cout << "  swaps = " << swaps << '\n';

    return 0;
}

Output yang Dihasilkan:

Hasil:    10 13 14 29 37
  swaps = 3
Hasil:    1 2 3 4 4
  swaps = 2

Bedah Kode Baris-per-Baris #

1. int min_idx = i;: inisialisasi indeks minimum dengan i (elemen pertama pada subarray yang belum terurut).
2. for (int j = i + 1; j < n; ++j): iterasi linear untuk mencari minimum di v[i+1..n-1].
3. if (v[j] < v[min_idx]) min_idx = j;: pembaruan indeks minimum bila ditemukan elemen lebih kecil. Operator < (strict less) penting untuk stabilitas — sayangnya tidak cukup, seperti akan kita lihat nanti.
4. if (min_idx != i): hindari pertukaran diri sendiri yang sia-sia.
5. swaps = 3: untuk input pertama, terjadi 3 pertukaran — tepat ≤ n-1 = 4. Bandingkan dengan bubble sort yang dapat melakukan hingga n(n-1)/2 pertukaran.

Kompleksitas #

Tidak seperti bubble sort, selection sort tidak memiliki varian adaptif. Best case = worst case = O(n²) karena pencarian minimum selalu memeriksa semua elemen yang tersisa terlepas dari kondisi input.

Mengapa Selection Sort Tidak Stabil #

Pertimbangkan input {4a, 2, 4b, 1, 3} (suffix a, b hanya menandai urutan input, kedua nilai 4 identik):

Iterasi 0: min = 1 (idx 3), swap v[0] <-> v[3]
           hasil: [1, 2, 4b, 4a, 3]   <-- 4b kini mendahului 4a!
Iterasi 1: min = 2 (idx 1), no swap
Iterasi 2: min = 3 (idx 4), swap v[2] <-> v[4]
           hasil: [1, 2, 3, 4a, 4b]
Iterasi 3: min = 4a (idx 3), no swap

Output akhir {1, 2, 3, 4a, 4b} terlihat stabil. Namun perhatikan langkah iterasi 0: pertukaran v[0]=4a dengan v[3]=1 menyebabkan 4b (yang aslinya pada indeks 2) ikut bergeser ke indeks 0 dan kemudian ke indeks 2 saat iterasi 0 menempatkan 4a ke indeks 3. Pada kasus yang lebih kompleks, pertukaran jarak jauh ini sering merusak urutan relatif elemen equal.

Bukti Konkret Ketidakstabilan #

Pertimbangkan input {(Budi,5), (Andi,3), (Citra,5)} (sort by nilai):

Iterasi 0: min nilai = 3 (Andi idx 1), swap v[0] <-> v[1]
           hasil: [Andi(3), Budi(5), Citra(5)]
Iterasi 1: min nilai = 5 (Budi idx 1), no swap
Iterasi 2: min nilai = 5 (Citra idx 2), no swap

Kasus ini terlihat stabil. Sekarang coba {(Budi,5), (Andi,3), (Citra,5), (Dewi,1)}:

Iterasi 0: min nilai = 1 (Dewi idx 3), swap v[0] <-> v[3]
           hasil: [Dewi(1), Andi(3), Citra(5), Budi(5)]
                          ^ Citra kini mendahului Budi!

Pada iterasi 0, swap(v[0], v[3]) memindahkan Citra(5) dari indeks 2 ke depan Budi(5) — urutan relatif Budi, Citra (input asli) menjadi Citra, Budi. Ini melanggar stabilitas.

Stabil Selection Sort (Variasi) #

Bila kita ingin menjaga stabilitas, ganti std::swap(v[i], v[min_idx]) dengan operasi geser:

// Stabil: geser elemen v[i..min_idx-1] ke kanan, tempatkan v[min_idx] di v[i]
int min_val = v[min_idx];
for (int k = min_idx; k > i; --k) v[k] = v[k - 1];
v[i] = min_val;

Mekanisme ini mempertahankan urutan relatif elemen equal karena elemen-elemen di antara i dan min_idx digeser ke kanan, bukan ditukar. Sayangnya, biaya geser adalah O(n) per iterasi, sehingga total operasi geser menjadi O(n²) — sama dengan pembandingan. Konstanta menjadi lebih besar dibanding versi klasik.

Keunggulan Selection Sort #

1. Minimum swaps — paling banyak n-1 pertukaran. Berguna saat biaya pertukaran elemen mahal (misalnya record besar yang tidak muat di cache, atau data pada disk).
2. Sederhana — kode sangat ringkas, mudah diaudit.
3. Deterministik — kompleksitas selalu Θ(n²) terlepas dari data, sehingga runtime dapat diprediksi.
4. In-place — hanya membutuhkan O(1) memori tambahan.

Kapan Selection Sort Layak Dipakai #

• n kecil dan biaya swap tinggi (misalnya elemen besar atau pada secondary storage).
• Kondisi memori sangat terbatas — O(1) auxiliary space.
• Tidak membutuhkan stabilitas.

Ringkasan #

• Selection sort memilih elemen minimum lalu menukarnya ke posisi depan — paling banyak n-1 swap.
• Kompleksitas selalu Θ(n²) pada best/average/worst — tidak adaptif.
• In-place O(1) memori tambahan.
• Tidak stabil dalam bentuk klasik karena pertukaran jarak jauh; dapat distabilkan dengan shift tetapi dengan biaya O(n²) geseran.
• Layak dipakai bila jumlah swap harus minimum dan stabilitas tidak diperlukan.

Pada chapter berikutnya kita akan membahas insertion sort — algoritma O(n²) yang stabil dan adaptif, sehingga menjadi pilihan std::sort untuk sub-array kecil.