KAL
Menu

Algoritma pengurutan sederhana

Bubble sort, selection sort, dan insertion sort diimplementasikan beserta alasan ketiganya kalah.

Daftar isi

Ketiga pengurutan yang paling sering dijadikan latihan awal, yaitu bubble sort, selection sort, dan insertion sort, memakai ide yang berbeda tetapi berakhir pada kelas kompleksitas yang sama. Topik ini membangun ketiganya secara utuh dalam Python dan Java lengkap dengan penghitung perbandingan dan penukaran, lalu menjalankannya pada tiga jenis array, yaitu array sembarang, array yang sudah terurut, dan array yang terurut terbalik. Dari keluaran itu, perilaku O(n2)O(n^2) yang menjadi kelemahan bersama ketiganya terbaca langsung dari angka, bukan dari teori semata.

Cara kerja ketiganya#

Bubble sort menyapu array dari kiri ke kanan sambil membandingkan dua tetangga, lalu menukarnya bila urutannya terbalik. Akibatnya, nilai terbesar pada setiap putaran pasti terdorong ke ujung kanan seperti gelembung yang naik, sehingga putaran berikutnya cukup menyapu bagian yang belum pasti letaknya. Versi yang dipakai di sini menambahkan bendera tukar, yaitu penanda apakah satu putaran menghasilkan penukaran. Dengan penanda itu, perulangan berhenti lebih awal ketika satu putaran penuh berjalan tanpa penukaran, tanda bahwa array sudah terurut.

Selection sort memilih jalur yang paling hemat penukaran. Setiap putaran mencari nilai terkecil pada bagian yang belum terurut, lalu menukarnya satu kali dengan elemen terdepan bagian itu. Penukaran berlangsung paling banyak n−1n-1 kali, tetapi pencarian nilai terkecil tetap menyapu seluruh sisa array pada setiap putaran, sehingga jumlah perbandingannya tidak pernah turun walaupun datanya sudah terurut.

Insertion sort menumbuhkan wilayah terurut di sisi kiri array. Elemen berikutnya diambil sebagai kunci, semua elemen wilayah terurut yang lebih besar digeser satu posisi ke kanan, lalu kunci disisipkan pada celah yang tersisa. Diagram berikut memperlihatkan proses penggeseran itu ketika kunci bernilai 1 disisipkan pada wilayah terurut yang berisi 3, 7, dan 9.

pergeseran pada insertion sorti = 3, kunci = 137915379513795awal, kunci = 1prefix bergeser ke kanankunci disisipkankuncislot kosongprefix terurutkuncidisisipkansisa
Pergeseran pada insertion sort: wilayah terurut digeser satu posisi untuk membuka slot bagi kunci

Pada baris kedua diagram, slot kosong muncul di depan karena kunci diangkat lebih dahulu sebelum penggeseran dimulai. Baris ketiga menutup prosesnya, kunci menempati slot itu dan wilayah terurut bertambah satu elemen. Inilah mekanisme yang membuat insertion sort terasa seperti menyusun kartu di tangan, yaitu kartu baru disisipkan ke posisi yang tepat pada deretan yang sudah terurut.

Implementasi Python dan keluarannya#

Ketiga algoritma dikemas dalam satu berkas dengan kontrak yang sama, yaitu mengurutkan array di tempat dan mengembalikan jumlah perbandingan beserta aksinya, penukaran untuk bubble dan selection, pergeseran untuk insertion. Penghitung ditempatkan tepat di depan setiap perbandingan dan penukaran sehingga angkanya dapat ditelusuri baris demi baris. Driver memanggil ketiganya pada tiga kasus yang sama agar perbandingannya adil.

python urutan-sederhana.py 
"""Bubble sort, selection sort, dan insertion sort dengan penghitung operasi."""


def bubble_sort(data):
    """Urutkan naik dengan membandingkan tetangga; kembalikan (perbandingan, penukaran)."""
    n = len(data)
    perbandingan = penukaran = 0
    for i in range(n - 1):
        ada_tukar = False
        for j in range(n - 1 - i):
            perbandingan += 1
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
                penukaran += 1
                ada_tukar = True
        if not ada_tukar:
            break
    return perbandingan, penukaran


def selection_sort(data):
    """Urutkan naik dengan memilih nilai terkecil; kembalikan (perbandingan, penukaran)."""
    n = len(data)
    perbandingan = penukaran = 0
    for i in range(n - 1):
        terkecil = i
        for j in range(i + 1, n):
            perbandingan += 1
            if data[j] < data[terkecil]:
                terkecil = j
        if terkecil != i:
            data[i], data[terkecil] = data[terkecil], data[i]
            penukaran += 1
    return perbandingan, penukaran


def insertion_sort(data):
    """Urutkan naik dengan menggeser; kembalikan (perbandingan, pergeseran)."""
    n = len(data)
    perbandingan = pergeseran = 0
    for i in range(1, n):
        kunci = data[i]
        j = i - 1
        while j >= 0:
            perbandingan += 1
            if data[j] > kunci:
                data[j + 1] = data[j]
                pergeseran += 1
                j -= 1
            else:
                break
        data[j + 1] = kunci
    return perbandingan, pergeseran


if __name__ == "__main__":
    dasar = [7, 3, 9, 1, 5, 8, 2, 6]
    kasus = [
        ("sembarang", list(dasar)),
        ("terurut", sorted(dasar)),
        ("terbalik", sorted(dasar, reverse=True)),
    ]
    algoritma = [
        ("bubble", bubble_sort, "penukaran"),
        ("selection", selection_sort, "penukaran"),
        ("insertion", insertion_sort, "pergeseran"),
    ]
    for nama, asal in kasus:
        print(f"array {nama} {asal}")
        for label, fungsi, metrik in algoritma:
            data = list(asal)
            perbandingan, aksi = fungsi(data)
            print(f"  {label:<9}: perbandingan {perbandingan}, {metrik} {aksi}, hasil {data}")
text Keluaran 
array sembarang [7, 3, 9, 1, 5, 8, 2, 6]
  bubble   : perbandingan 27, penukaran 15, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  selection: perbandingan 28, penukaran 7, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  insertion: perbandingan 20, pergeseran 15, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terurut [1, 2, 3, 5, 6, 7, 8, 9]
  bubble   : perbandingan 7, penukaran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  selection: perbandingan 28, penukaran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  insertion: perbandingan 7, pergeseran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terbalik [9, 8, 7, 6, 5, 3, 2, 1]
  bubble   : perbandingan 28, penukaran 28, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  selection: perbandingan 28, penukaran 4, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  insertion: perbandingan 28, pergeseran 28, hasil [1, 2, 3, 5, 6, 7, 8, 9]

Baris pertama keluaran menampilkan kasus yang paling umum, array sembarang. Selection sort mencatat 28 perbandingan, tepat 8×7/28 \times 7 / 2, dan angka yang sama muncul pada ketiga kasus karena sifatnya memang tidak peduli isi array. Bubble sort tercatat 27 perbandingan karena bendera tukar menghentikan putaran terakhir yang tidak lagi menghasilkan penukaran. Insertion sort mencatat 20 perbandingan dan 15 pergeseran, dan angka 15 itu bukan kebetulan, melainkan jumlah pasangan yang urutannya terbalik pada array awal.

Baris tengah dan bawah menunjukkan sisi yang berbeda dari ketiganya. Pada array terurut, bubble dan insertion hanya menghabiskan 7 perbandingan, yaitu n−1n-1, tanpa satu pun penukaran atau pergeseran, sedangkan selection tetap membayar 28 perbandingan penuh. Pada array terbalik, seluruh pasangan saling terbalik sehingga ketiganya mencapai 28 perbandingan, dengan bubble dan insertion mencapai 28 aksi, kasus terburuk yang sebenarnya.

Versi Java#

Versi Java meniru struktur Python dengan tiga metode statis yang mengembalikan pasangan hasil melalui array dua elemen, karena Java tidak memiliki tuple bawaan. Keluarannya identik dengan versi Python, dan memang harus identik, karena jumlah operasi adalah sifat algoritmanya, bukan sifat bahasanya. Perbedaan penulisan hanya muncul pada swap yang di Java menuntut satu variabel sementara.

java UrutanSederhana.java 
import java.util.Arrays;

public class UrutanSederhana {

    // mengurutkan naik dengan membandingkan tetangga, hasil berupa {perbandingan, penukaran}
    static int[] bubbleSort(int[] data) {
        int n = data.length, perbandingan = 0, penukaran = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean adaTukar = false;
            for (int j = 0; j < n - 1 - i; j++) {
                perbandingan++;
                if (data[j] > data[j + 1]) {
                    int sementara = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = sementara;
                    penukaran++;
                    adaTukar = true;
                }
            }
            if (!adaTukar) {
                break;
            }
        }
        return new int[] {perbandingan, penukaran};
    }

    // mengurutkan naik dengan memilih nilai terkecil pada setiap putaran
    static int[] selectionSort(int[] data) {
        int n = data.length, perbandingan = 0, penukaran = 0;
        for (int i = 0; i < n - 1; i++) {
            int terkecil = i;
            for (int j = i + 1; j < n; j++) {
                perbandingan++;
                if (data[j] < data[terkecil]) {
                    terkecil = j;
                }
            }
            if (terkecil != i) {
                int sementara = data[i];
                data[i] = data[terkecil];
                data[terkecil] = sementara;
                penukaran++;
            }
        }
        return new int[] {perbandingan, penukaran};
    }

    // mengurutkan naik dengan menggeser elemen yang lebih besar
    static int[] insertionSort(int[] data) {
        int n = data.length, perbandingan = 0, pergeseran = 0;
        for (int i = 1; i < n; i++) {
            int kunci = data[i];
            int j = i - 1;
            while (j >= 0) {
                perbandingan++;
                if (data[j] > kunci) {
                    data[j + 1] = data[j];
                    pergeseran++;
                    j--;
                } else {
                    break;
                }
            }
            data[j + 1] = kunci;
        }
        return new int[] {perbandingan, pergeseran};
    }

    public static void main(String[] args) {
        int[][] kasus = {
            {7, 3, 9, 1, 5, 8, 2, 6},
            {1, 2, 3, 5, 6, 7, 8, 9},
            {9, 8, 7, 6, 5, 3, 2, 1},
        };
        String[] namaKasus = {"sembarang", "terurut", "terbalik"};
        String[] label = {"bubble", "selection", "insertion"};
        String[] metrik = {"penukaran", "penukaran", "pergeseran"};
        for (int k = 0; k < kasus.length; k++) {
            System.out.println("array " + namaKasus[k] + " " + Arrays.toString(kasus[k]));
            for (int a = 0; a < 3; a++) {
                int[] data = kasus[k].clone();
                int[] hitung;
                if (a == 0) {
                    hitung = bubbleSort(data);
                } else if (a == 1) {
                    hitung = selectionSort(data);
                } else {
                    hitung = insertionSort(data);
                }
                System.out.printf("  %-9s: perbandingan %d, %s %d, hasil %s%n",
                        label[a], hitung[0], metrik[a], hitung[1], Arrays.toString(data));
            }
        }
    }
}
text Keluaran 
array sembarang [7, 3, 9, 1, 5, 8, 2, 6]
  bubble   : perbandingan 27, penukaran 15, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  selection: perbandingan 28, penukaran 7, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  insertion: perbandingan 20, pergeseran 15, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terurut [1, 2, 3, 5, 6, 7, 8, 9]
  bubble   : perbandingan 7, penukaran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  selection: perbandingan 28, penukaran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  insertion: perbandingan 7, pergeseran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terbalik [9, 8, 7, 6, 5, 3, 2, 1]
  bubble   : perbandingan 28, penukaran 28, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  selection: perbandingan 28, penukaran 4, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  insertion: perbandingan 28, pergeseran 28, hasil [1, 2, 3, 5, 6, 7, 8, 9]
bash 
# menjalankan berkas Java tunggal tanpa tahap kompilasi terpisah
java UrutanSederhana.java
text Keluaran 
array sembarang [7, 3, 9, 1, 5, 8, 2, 6]
  bubble   : perbandingan 27, penukaran 15, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  selection: perbandingan 28, penukaran 7, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  insertion: perbandingan 20, pergeseran 15, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terurut [1, 2, 3, 5, 6, 7, 8, 9]
  bubble   : perbandingan 7, penukaran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  selection: perbandingan 28, penukaran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  insertion: perbandingan 7, pergeseran 0, hasil [1, 2, 3, 5, 6, 7, 8, 9]
array terbalik [9, 8, 7, 6, 5, 3, 2, 1]
  bubble   : perbandingan 28, penukaran 28, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  selection: perbandingan 28, penukaran 4, hasil [1, 2, 3, 5, 6, 7, 8, 9]
  insertion: perbandingan 28, pergeseran 28, hasil [1, 2, 3, 5, 6, 7, 8, 9]

Alasan ketiganya kalah#

Jumlah perbandingan pengurutan sederhana pada kasus terburuk mengikuti jumlah pasangan elemen, yaitu n(n−1)2\frac{n(n-1)}{2}. Untuk nn sebesar satu juta, angka itu menjadi sekitar 5×10115 \times 10^{11} perbandingan. Pengurutan berbasis pembagian seperti merge sort hanya membutuhkan sekitar 2×1072 \times 10^7 perbandingan untuk masukan yang sama. Pada mesin yang menyelesaikan satu miliar perbandingan per detik, selisihnya adalah ratusan detik melawan sepersekian detik.

Selisih kelas O(n2)O(n^2) melawan O(nlog⁡n)O(n \log n) itulah yang membuat ketiganya tidak pernah dipakai untuk array besar di produksi. Fungsi sorted() Python dan Arrays.sort Java sama-sama berbasis pengurutan O(nlog⁡n)O(n \log n), sehingga keduanya menjadi pilihan bawaan untuk pekerjaan nyata. Insertion sort tetap hidup di dalam pengurutan modern sebagai komponen, karena deretan pendek dan data yang hampir terurut menyisakan kasus terbaik O(n)O(n) yang tidak dimiliki bubble maupun selection.

Kesalahan umum#

  1. Perulangan dalam bubble sort tidak menyusut. Menuliskan batas n - 1 pada setiap putaran membuat sisa array yang sudah pasti di posisinya ikut disapu ulang. Batas yang benar adalah n - 1 - i, sehingga setiap putaran lebih pendek dari sebelumnya.
  2. Insertion sort ditulis dengan swap alih-alih pergeseran. Menukar kunci dengan setiap elemen yang lebih besar menghasilkan urutan yang benar, tetapi setiap penukaran menulis dua sel, dua kali lipat dibanding satu kali penggeseran. Mekanisme yang dipakai pengurutan modern adalah menggeser lalu menyisipkan, sebagaimana diperlihatkan diagram di awal topik.
  3. Menilai kinerja dari satu array saja. Selection sort terlihat sama buruknya dengan bubble pada data sembarang, tetapi keduanya berperilaku berbeda pada data terurut. Uji selalu tiga kasus, sembarang, terurut, dan terbalik, agar klaim kasus terbaik dan terburuknya berpijak pada data.

Ringkasan#

  • Bubble sort membandingkan tetangga dan mendorong nilai terbesar ke ujung, dengan bendera tukar yang menghentikan dini pada array terurut.
  • Selection sort selalu menghabiskan n(n−1)2\frac{n(n-1)}{2} perbandingan, tetapi menukar paling banyak n−1n-1 kali.
  • Insertion sort menggeser lalu menyisipkan pada wilayah terurut, mencapai O(n)O(n) pada data terurut, dengan jumlah pergeseran sama dengan jumlah inversi.
  • Ketiganya berada di kelas O(n2)O(n^2) pada kasus umum, sehingga kalah dari pengurutan O(nlog⁡n)O(n \log n) ketika masukan membesar.

Referensi#