Binary search pada Bab sebelumnya bersyarat data terurut — dan mengurutkan sendiri adalah salah satu operasi paling mahal sekaligus paling sering dilakukan software. Database mengurutkan untuk indeks, e-commerce mengurutkan untuk harga termurah, laporan mengurutkan untuk tanggal terbaru. Keluarga algoritma sorting menawarkan spektrum penuh: bubble sort yang paling mudah dipahami, insertion sort yang diam-diam hebat pada data nyaris terurut, sampai merge sort dan quick sort berbasis divide and conquer yang menopang pustaka standar. Bab ini mengimplementasikan kelimanya dengan penghitung perbandingan dan tukar posisi, lalu membedah apa yang sebenarnya dilakukan Arrays.sort di dalam Java.

Tiga Algoritma Dasar yang Sederhana #

Tiga algoritma kuadratik O(n²) punya cara berpikir yang berbeda. Bubble sort membandingkan dua tetangga dan menukar mereka bila terbalik — elemen terbesar “menggelembung” sampai ujung setiap putaran. Selection sort memilih nilai terkecil dari sisa data dan menukarkannya ke depan — jumlah tukarnya minimal. Insertion sort menyisipkan satu elemen ke posisi tepat pada bagian kiri yang sudah terurut — persis cara kita menyusun kartu di tangan:

java SortingDasar.java 
import java.util.Arrays;

public class SortingDasar {

    static long perbandingan;
    static long tukar;

    public static void main(String[] args) {
        int[] asli = {5, 2, 9, 1, 7, 3, 8, 6};
        System.out.println("Data awal: " + Arrays.toString(asli));
        System.out.println();

        System.out.println("=== Bubble sort ===");
        int[] a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        tukar = 0;
        urutBubble(a);
        laporan(a, "Tukar posisi ");

        System.out.println("=== Selection sort ===");
        a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        tukar = 0;
        urutSelection(a);
        laporan(a, "Tukar posisi ");

        System.out.println("=== Insertion sort ===");
        a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        tukar = 0;
        urutInsertion(a);
        laporan(a, "Geser elemen ");
    }

    // Bubble sort: elemen terbesar menggelembung ke kanan tiap putaran.
    static void urutBubble(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            boolean adaTukar = false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                perbandingan++;
                if (a[j] > a[j + 1]) {
                    tukarPosisi(a, j, j + 1);
                    adaTukar = true;
                }
            }
            if (!adaTukar) {
                break;   // satu putaran tanpa tukar: data sudah terurut
            }
        }
    }

    // Selection sort: cari nilai terkecil, tukar ke posisi depan.
    static void urutSelection(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < a.length; j++) {
                perbandingan++;
                if (a[j] < a[minIdx]) {
                    minIdx = j;
                }
            }
            if (minIdx != i) {
                tukarPosisi(a, i, minIdx);
            }
        }
    }

    // Insertion sort: sisipkan elemen ke posisi tepat di bagian kiri.
    static void urutInsertion(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int kunci = a[i];
            int j = i - 1;
            while (j >= 0) {
                perbandingan++;
                if (a[j] > kunci) {
                    a[j + 1] = a[j];   // geser elemen besar ke kanan
                    tukar++;
                    j--;
                } else {
                    break;
                }
            }
            a[j + 1] = kunci;          // kunci jatuh di lubang yang tersisa
            tukar++;
        }
    }

    static void tukarPosisi(int[] a, int i, int j) {
        tukar++;
        int sementara = a[i];
        a[i] = a[j];
        a[j] = sementara;
    }

    static void laporan(int[] hasil, String metrik) {
        System.out.println("Hasil        : " + Arrays.toString(hasil));
        System.out.println("Perbandingan : " + perbandingan);
        System.out.println(metrik + ": " + tukar);
        System.out.println();
    }
}

Output yang Dihasilkan:

text 
Data awal: [5, 2, 9, 1, 7, 3, 8, 6]

=== Bubble sort ===
Hasil        : [1, 2, 3, 5, 6, 7, 8, 9]
Perbandingan : 22
Tukar posisi : 12

=== Selection sort ===
Hasil        : [1, 2, 3, 5, 6, 7, 8, 9]
Perbandingan : 28
Tukar posisi : 4

=== Insertion sort ===
Hasil        : [1, 2, 3, 5, 6, 7, 8, 9]
Perbandingan : 17
Geser elemen : 19

Angka pada output merangkum karakter ketiganya pada data yang sama. Bubble sort mencatat 12 tukar posisi — persis jumlah inversion (pasangan terbalik) data awal — dan 22 perbandingan karena bendera adaTukar menghentikan putaran terakhir yang sia-sia. Selection sort selalu melakukan 28 perbandingan (7+6+…+1, tetap n(n−1)/2 berapa pun susunan data) tetapi hanya 4 tukar. Insertion sort paling hemat perbandingan (17) karena berhenti begitu menemui elemen yang sudah lebih kecil — inilah alasan method ini menang telak pada data nyaris terurut dan dipakai Arrays.sort untuk potongan kecil.

Merge Sort Membagi lalu Menggabungkan #

Merge sort menukar strategi: bagi array menjadi dua sampai tersisa satu elemen (otomatis terurut), lalu gabungkan dua bagian terurut menjadi satu. Penggabungan dua barisan terurut murah — cukup bandingkan kepala masing-masing dan ambil yang lebih kecil. Quick sort memilih satu pivot, menyusun ulang array agar elemen lebih kecil berada di kiri pivot dan lebih besar di kanan (partisi), lalu mengulanginya di kedua sisi:

java MergeQuickSort.java 
import java.util.Arrays;

public class MergeQuickSort {

    static long perbandingan;
    static long operasi;

    public static void main(String[] args) {
        int[] asli = {5, 2, 9, 1, 7, 3, 8, 6};
        System.out.println("Data awal: " + Arrays.toString(asli));
        System.out.println();

        System.out.println("=== Merge sort (divide and conquer) ===");
        int[] a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        operasi = 0;
        urutMerge(a, 0, a.length - 1);
        System.out.println("Hasil          : " + Arrays.toString(a));
        System.out.println("Perbandingan   : " + perbandingan);
        System.out.println("Penyalinan     : " + operasi);
        System.out.println();

        System.out.println("=== Quick sort (partisi Lomuto) ===");
        a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        operasi = 0;
        urutQuick(a, 0, a.length - 1);
        System.out.println("Hasil          : " + Arrays.toString(a));
        System.out.println("Perbandingan   : " + perbandingan);
        System.out.println("Tukar posisi   : " + operasi);
    }

    // ===== Merge sort =====

    static void urutMerge(int[] a, int kiri, int kanan) {
        if (kiri >= kanan) {
            return;                      // satu elemen: sudah terurut
        }
        int tengah = (kiri + kanan) >>> 1;
        urutMerge(a, kiri, tengah);      // urut separuh kiri
        urutMerge(a, tengah + 1, kanan); // urut separuh kanan
        gabung(a, kiri, tengah, kanan);  // gabungkan dua bagian terurut
    }

    static void gabung(int[] a, int kiri, int tengah, int kanan) {
        int[] campuran = new int[kanan - kiri + 1];
        int i = kiri;
        int j = tengah + 1;
        int k = 0;

        while (i <= tengah && j <= kanan) {
            perbandingan++;
            if (a[i] <= a[j]) {          // <= menjaga stabilitas
                campuran[k++] = a[i++];
            } else {
                campuran[k++] = a[j++];
            }
            operasi++;
        }
        while (i <= tengah) {
            campuran[k++] = a[i++];
            operasi++;
        }
        while (j <= kanan) {
            campuran[k++] = a[j++];
            operasi++;
        }
        for (k = 0; k < campuran.length; k++) {
            a[kiri + k] = campuran[k];   // tulis kembali hasil gabungan
            operasi++;
        }
    }

    // ===== Quick sort (skema partisi Lomuto) =====

    static void urutQuick(int[] a, int rendah, int tinggi) {
        if (rendah >= tinggi) {
            return;
        }
        int posisiPivot = partisi(a, rendah, tinggi);
        urutQuick(a, rendah, posisiPivot - 1);   // kiri pivot: lebih kecil
        urutQuick(a, posisiPivot + 1, tinggi);   // kanan pivot: lebih besar
    }

    static int partisi(int[] a, int rendah, int tinggi) {
        int pivot = a[tinggi];           // Lomuto: elemen terakhir jadi pivot
        int batas = rendah - 1;          // batas wilayah "lebih kecil dari pivot"
        for (int j = rendah; j < tinggi; j++) {
            perbandingan++;
            if (a[j] < pivot) {
                batas++;
                tukarPosisi(a, batas, j);
            }
        }
        tukarPosisi(a, batas + 1, tinggi);   // pivot masuk posisi finalnya
        return batas + 1;
    }

    static void tukarPosisi(int[] a, int i, int j) {
        operasi++;
        int sementara = a[i];
        a[i] = a[j];
        a[j] = sementara;
    }
}

Output yang Dihasilkan:

text 
Data awal: [5, 2, 9, 1, 7, 3, 8, 6]

=== Merge sort (divide and conquer) ===
Hasil          : [1, 2, 3, 5, 6, 7, 8, 9]
Perbandingan   : 17
Penyalinan     : 48

=== Quick sort (partisi Lomuto) ===
Hasil          : [1, 2, 3, 5, 6, 7, 8, 9]
Perbandingan   : 14
Tukar posisi   : 12

Kedua algoritma sama-sama menghasilkan array terurut, tetapi karakter biayanya berbeda: merge sort hanya 17 perbandingan namun 48 penyalinan (harga array bantu), quick sort 14 perbandingan dengan 12 tukar dan tanpa array tambahan. Mari kita bedah bagian-bagian pentingnya:

  1. Baris 38-46 (urutMerge): rekursi membagi rentang jadi dua sampai kiri >= kanan — kasus dasar satu elemen. Pembagian berlangsung log₂ n tingkat, dan setiap tingkat menggabungkan total n elemen, menghasilkan O(n log n) yang kebal susunan data.
  2. Baris 56 (a[i] <= a[j]): tanda sama-dengan bukan detail kecil. Saat nilai sama, elemen dari separuh kiri diambil lebih dulu sehingga urutan relatif dua elemen sama terjaga — sifat stabil yang hilang pada quick sort.
  3. Baris 74-92 (partisi Lomuto): penunjuk batas menandai ujung wilayah “lebih kecil dari pivot”. Setiap kali a[j] < pivot, wilayah itu diperluas dengan menukar elemen ke posisi batas+1. Di akhir loop, pivot ditukar ke batas + 1 — posisi finalnya dalam array terurut, dijamin tidak berpindah lagi.
  4. Kerentanan quick sort: partisi Lomuto dengan pivot elemen terakhir melambat menjadi O(n²) pada data yang sudah terurut, karena setiap partisi hanya membuang satu elemen. Implementasi produksi memitigasinya dengan pivot acak atau median-of-three.

Tabel Kompleksitas dan Stabilitas #

AlgoritmaTerbaikRata-rataTerburukRuang bantuStabil
Bubble sortO(n)O(n²)O(n²)O(1)ya
Selection sortO(n²)O(n²)O(n²)O(1)tidak
Insertion sortO(n)O(n²)O(n²)O(1)ya
Merge sortO(n log n)O(n log n)O(n log n)O(n)ya
Quick sortO(n log n)O(n log n)O(n²)O(log n)tidak

Stabilitas berarti dua elemen bernilai sama mempertahankan urutan relatifnya — krusial saat mengurutkan berdasarkan satu field lalu field lain, misalnya urut kota lalu nama. Merge sort stabil dan berkinerja tetap O(n log n); quick sort rata-rata lebih cepat karena hanya menukar elemen di tempat tanpa penyalinan, tetapi membawa risiko kasus terburuk dan tidak stabil.

Arrays.sort dan Collections.sort di Dalam Java #

Pustaka Java tidak memakai satu algoritma untuk semua. Arrays.sort(int[]) pada primitive memakai dual-pivot quicksort varian Vladimir Yaroslavskiy — dua pivot per partisi, sedikit lebih sedikit perbandingan dan penyalinan dibanding quicksort klasik. Sebaliknya Arrays.sort(Object[]) dan Collections.sort memakai TimSort — merge sort adaptif hybrid yang stabil, gabungan merge sort dan insertion sort, dirancang agar nyaris terurut selesai sangat cepat. Alasan perbedaannya: objek bisa identik nilainya sehingga stabilitas wajib, sementara dua int bernilai sama tidak bisa dibedakan sehingga stabilitas tidak berarti dan quicksort in-place menghemat memori:

java SortPustaka.java 
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SortPustaka {

    public static void main(String[] args) {
        int[] angka = {5, 2, 9, 1, 7, 3, 8, 6};
        Arrays.sort(angka);              // primitive: dual-pivot quicksort
        System.out.println("Arrays.sort(int[])              : "
                + Arrays.toString(angka));

        Integer[] kotak = {5, 2, 9, 1, 7, 3, 8, 6};
        Arrays.sort(kotak, Collections.reverseOrder());   // objek: TimSort
        System.out.println("Arrays.sort(Integer[], turun)   : "
                + Arrays.toString(kotak));

        List<String> nama = new java.util.ArrayList<>(
                Arrays.asList("Budi", "siti", "Dewi", "andi"));
        nama.sort(String.CASE_INSENSITIVE_ORDER);   // TimSort + comparator
        System.out.println("List.sort(abai kapital)         : " + nama);

        List<String> defaultUrut = new java.util.ArrayList<>(
                Arrays.asList("Budi", "siti", "Dewi", "andi"));
        Collections.sort(defaultUrut);              // urutan natural String
        System.out.println("Collections.sort(natural)       : " + defaultUrut);
    }
}

Output yang Dihasilkan:

text 
Arrays.sort(int[])              : [1, 2, 3, 5, 6, 7, 8, 9]
Arrays.sort(Integer[], turun)   : [9, 8, 7, 6, 5, 3, 2, 1]
List.sort(abai kapital)         : [andi, Budi, Dewi, siti]
Collections.sort(natural)       : [Budi, Dewi, andi, siti]

Output memperlihatkan dua hal. Pertama, comparator mengubah urutan tanpa mengubah algoritma: Collections.reverseOrder() membalik urutan Integer, String.CASE_INSENSITIVE_ORDER mengurutkan nama tanpa memedulikan kapital sehingga andi naik ke depan. Kedua, urutan natural String mengikuti kode Unicode: huruf kapital Budi dan Dewi mendahului huruf kecil andi — perilaku yang sering mengejutkan pemula saat menggabungkan casing campuran.

Merge sort dan quick sort yang barusan kita bedah sama-sama memakai teknik yang belum pernah dibahas formal: rekursi. Bab berikutnya masuk ke pola berpikir itu — function yang memanggil dirinya sendiri — beserta pasangannya, backtracking yang menjelajahi ruang solusi dengan mundur terarah.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

MergeQuickSort.java

Unduh berkas
java 
import java.util.Arrays;

public class MergeQuickSort {

    static long perbandingan;
    static long operasi;

    public static void main(String[] args) {
        int[] asli = {5, 2, 9, 1, 7, 3, 8, 6};
        System.out.println("Data awal: " + Arrays.toString(asli));
        System.out.println();

        System.out.println("=== Merge sort (divide and conquer) ===");
        int[] a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        operasi = 0;
        urutMerge(a, 0, a.length - 1);
        System.out.println("Hasil          : " + Arrays.toString(a));
        System.out.println("Perbandingan   : " + perbandingan);
        System.out.println("Penyalinan     : " + operasi);
        System.out.println();

        System.out.println("=== Quick sort (partisi Lomuto) ===");
        a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        operasi = 0;
        urutQuick(a, 0, a.length - 1);
        System.out.println("Hasil          : " + Arrays.toString(a));
        System.out.println("Perbandingan   : " + perbandingan);
        System.out.println("Tukar posisi   : " + operasi);
    }

    // ===== Merge sort =====

    static void urutMerge(int[] a, int kiri, int kanan) {
        if (kiri >= kanan) {
            return;                      // satu elemen: sudah terurut
        }
        int tengah = (kiri + kanan) >>> 1;
        urutMerge(a, kiri, tengah);      // urut separuh kiri
        urutMerge(a, tengah + 1, kanan); // urut separuh kanan
        gabung(a, kiri, tengah, kanan);  // gabungkan dua bagian terurut
    }

    static void gabung(int[] a, int kiri, int tengah, int kanan) {
        int[] campuran = new int[kanan - kiri + 1];
        int i = kiri;
        int j = tengah + 1;
        int k = 0;

        while (i <= tengah && j <= kanan) {
            perbandingan++;
            if (a[i] <= a[j]) {          // <= menjaga stabilitas
                campuran[k++] = a[i++];
            } else {
                campuran[k++] = a[j++];
            }
            operasi++;
        }
        while (i <= tengah) {
            campuran[k++] = a[i++];
            operasi++;
        }
        while (j <= kanan) {
            campuran[k++] = a[j++];
            operasi++;
        }
        for (k = 0; k < campuran.length; k++) {
            a[kiri + k] = campuran[k];   // tulis kembali hasil gabungan
            operasi++;
        }
    }

    // ===== Quick sort (skema partisi Lomuto) =====

    static void urutQuick(int[] a, int rendah, int tinggi) {
        if (rendah >= tinggi) {
            return;
        }
        int posisiPivot = partisi(a, rendah, tinggi);
        urutQuick(a, rendah, posisiPivot - 1);   // kiri pivot: lebih kecil
        urutQuick(a, posisiPivot + 1, tinggi);   // kanan pivot: lebih besar
    }

    static int partisi(int[] a, int rendah, int tinggi) {
        int pivot = a[tinggi];           // Lomuto: elemen terakhir jadi pivot
        int batas = rendah - 1;          // batas wilayah "lebih kecil dari pivot"
        for (int j = rendah; j < tinggi; j++) {
            perbandingan++;
            if (a[j] < pivot) {
                batas++;
                tukarPosisi(a, batas, j);
            }
        }
        tukarPosisi(a, batas + 1, tinggi);   // pivot masuk posisi finalnya
        return batas + 1;
    }

    static void tukarPosisi(int[] a, int i, int j) {
        operasi++;
        int sementara = a[i];
        a[i] = a[j];
        a[j] = sementara;
    }
}

SortingDasar.java

Unduh berkas
java 
import java.util.Arrays;

public class SortingDasar {

    static long perbandingan;
    static long tukar;

    public static void main(String[] args) {
        int[] asli = {5, 2, 9, 1, 7, 3, 8, 6};
        System.out.println("Data awal: " + Arrays.toString(asli));
        System.out.println();

        System.out.println("=== Bubble sort ===");
        int[] a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        tukar = 0;
        urutBubble(a);
        laporan(a, "Tukar posisi ");

        System.out.println("=== Selection sort ===");
        a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        tukar = 0;
        urutSelection(a);
        laporan(a, "Tukar posisi ");

        System.out.println("=== Insertion sort ===");
        a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        tukar = 0;
        urutInsertion(a);
        laporan(a, "Geser elemen ");
    }

    // Bubble sort: elemen terbesar menggelembung ke kanan tiap putaran.
    static void urutBubble(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            boolean adaTukar = false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                perbandingan++;
                if (a[j] > a[j + 1]) {
                    tukarPosisi(a, j, j + 1);
                    adaTukar = true;
                }
            }
            if (!adaTukar) {
                break;   // satu putaran tanpa tukar: data sudah terurut
            }
        }
    }

    // Selection sort: cari nilai terkecil, tukar ke posisi depan.
    static void urutSelection(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < a.length; j++) {
                perbandingan++;
                if (a[j] < a[minIdx]) {
                    minIdx = j;
                }
            }
            if (minIdx != i) {
                tukarPosisi(a, i, minIdx);
            }
        }
    }

    // Insertion sort: sisipkan elemen ke posisi tepat di bagian kiri.
    static void urutInsertion(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int kunci = a[i];
            int j = i - 1;
            while (j >= 0) {
                perbandingan++;
                if (a[j] > kunci) {
                    a[j + 1] = a[j];   // geser elemen besar ke kanan
                    tukar++;
                    j--;
                } else {
                    break;
                }
            }
            a[j + 1] = kunci;          // kunci jatuh di lubang yang tersisa
            tukar++;
        }
    }

    static void tukarPosisi(int[] a, int i, int j) {
        tukar++;
        int sementara = a[i];
        a[i] = a[j];
        a[j] = sementara;
    }

    static void laporan(int[] hasil, String metrik) {
        System.out.println("Hasil        : " + Arrays.toString(hasil));
        System.out.println("Perbandingan : " + perbandingan);
        System.out.println(metrik + ": " + tukar);
        System.out.println();
    }
}

SortPustaka.java

Unduh berkas
java 
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SortPustaka {

    public static void main(String[] args) {
        int[] angka = {5, 2, 9, 1, 7, 3, 8, 6};
        Arrays.sort(angka);              // primitive: dual-pivot quicksort
        System.out.println("Arrays.sort(int[])              : "
                + Arrays.toString(angka));

        Integer[] kotak = {5, 2, 9, 1, 7, 3, 8, 6};
        Arrays.sort(kotak, Collections.reverseOrder());   // objek: TimSort
        System.out.println("Arrays.sort(Integer[], turun)   : "
                + Arrays.toString(kotak));

        List<String> nama = new java.util.ArrayList<>(
                Arrays.asList("Budi", "siti", "Dewi", "andi"));
        nama.sort(String.CASE_INSENSITIVE_ORDER);   // TimSort + comparator
        System.out.println("List.sort(abai kapital)         : " + nama);

        List<String> defaultUrut = new java.util.ArrayList<>(
                Arrays.asList("Budi", "siti", "Dewi", "andi"));
        Collections.sort(defaultUrut);              // urutan natural String
        System.out.println("Collections.sort(natural)       : " + defaultUrut);
    }
}