Sorting adalah proses menyusun elemen data sesuai urutan tertentu, biasanya menaik (ascending). Banyak algoritma lain—seperti binary search, deduplikasi, dan penyusunan laporan—bergantung pada data yang sudah terurut. Pada chapter ini kita akan mengimplementasikan enam algoritma klasik di Kotlin: tiga algoritma sederhana dengan kompleksitas O(n²) (bubble, selection, insertion) dan tiga algoritma efisien dengan kompleksitas O(n log n) (merge, quick, heap). Pembaca akan melihat mengapa insertion sort unggul untuk data hampir terurut, dan kapan sorted() bawaan Kotlin menjadi pilihan paling praktis.

Algoritma O(n²): Sederhana tapi Lambat #

Tiga algoritma berikut mudah dipahami dan diimplementasikan, namun kompleksitas waktunya tumbuh kuadratik terhadap ukuran data. Mereka cocok untuk data kecil (kurang dari 100 elemen) atau sebagai dasar pembelajaran.

AlgoritmaCara kerjaBest caseWorst case
Bubble sortTukar pasangan tetangga yang tidak urutO(n) (sudah urut)O(n²)
Selection sortPilih minimum, tukar ke depanO(n²)O(n²)
Insertion sortSisipkan elemen ke posisi tepatO(n) (hampir urut)O(n²)

Algoritma O(n log n): Efisien untuk Data Besar #

AlgoritmaStrategiAverageWorstStable
Merge sortBagi dua, urutkan, gabungO(n log n)O(n log n)Ya
Quick sortPivot partisiO(n log n)O(n²)Tidak
Heap sortBangun max-heap, ekstrak maksO(n log n)O(n log n)Tidak

Implementasi Enam Algoritma Sort #

kotlin 
// Demo Sorting Algorithms: bubble, selection, insertion, merge, quick, heap sort.

// === Bubble sort: O(n^2) ===
fun bubbleSort(arr: IntArray): IntArray {
    val a = arr.copyOf()
    val n = a.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            if (a[j] > a[j + 1]) {
                val t = a[j]; a[j] = a[j + 1]; a[j + 1] = t
            }
        }
    }
    return a
}

// === Selection sort: O(n^2) ===
fun selectionSort(arr: IntArray): IntArray {
    val a = arr.copyOf()
    val n = a.size
    for (i in 0 until n - 1) {
        var minIdx = i
        for (j in i + 1 until n) {
            if (a[j] < a[minIdx]) minIdx = j
        }
        if (minIdx != i) {
            val t = a[i]; a[i] = a[minIdx]; a[minIdx] = t
        }
    }
    return a
}

// === Insertion sort: O(n^2), efisien untuk data hampir sorted ===
fun insertionSort(arr: IntArray): IntArray {
    val a = arr.copyOf()
    for (i in 1 until a.size) {
        val key = a[i]
        var j = i - 1
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j]
            j--
        }
        a[j + 1] = key
    }
    return a
}

// === Merge sort: O(n log n) ===
fun mergeSort(arr: IntArray): IntArray {
    if (arr.size <= 1) return arr.copyOf()
    val mid = arr.size / 2
    val left = mergeSort(arr.sliceArray(0 until mid))
    val right = mergeSort(arr.sliceArray(mid until arr.size))
    return merge(left, right)
}

private fun merge(left: IntArray, right: IntArray): IntArray {
    val result = IntArray(left.size + right.size)
    var i = 0; var j = 0; var k = 0
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            result[k++] = left[i++]
        } else {
            result[k++] = right[j++]
        }
    }
    while (i < left.size) result[k++] = left[i++]
    while (j < right.size) result[k++] = right[j++]
    return result
}

// === Quick sort: avg O(n log n), worst O(n^2) ===
fun quickSort(arr: IntArray): IntArray {
    val a = arr.copyOf()
    quickSortRec(a, 0, a.lastIndex)
    return a
}

private fun quickSortRec(arr: IntArray, low: Int, high: Int) {
    if (low >= high) return
    val pivot = arr[high]
    var i = low - 1
    for (j in low until high) {
        if (arr[j] <= pivot) {
            i++
            val t = arr[i]; arr[i] = arr[j]; arr[j] = t
        }
    }
    val t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t
    val p = i + 1
    quickSortRec(arr, low, p - 1)
    quickSortRec(arr, p + 1, high)
}

// === Heap sort: O(n log n) ===
fun heapSort(arr: IntArray): IntArray {
    val a = arr.copyOf()
    val n = a.size
    // Build max heap
    for (i in n / 2 - 1 downTo 0) heapify(a, n, i)
    // Extract elements one by one
    for (i in n - 1 downTo 1) {
        val t = a[0]; a[0] = a[i]; a[i] = t
        heapify(a, i, 0)
    }
    return a
}

private fun heapify(arr: IntArray, n: Int, i: Int) {
    var largest = i
    val left = 2 * i + 1
    val right = 2 * i + 2
    if (left < n && arr[left] > arr[largest]) largest = left
    if (right < n && arr[right] > arr[largest]) largest = right
    if (largest != i) {
        val t = arr[i]; arr[i] = arr[largest]; arr[largest] = t
        heapify(arr, n, largest)
    }
}

fun main() {
    println("=== Demo Sorting Algorithms ===")

    val data = intArrayOf(64, 34, 25, 12, 22, 11, 90, 5, 77, 30)
    println("Data asli: ${data.toList()}")

    println()
    println("--- Algoritma O(n^2) ---")
    println("Bubble sort:    ${bubbleSort(data).toList()}")
    println("Selection sort: ${selectionSort(data).toList()}")
    println("Insertion sort: ${insertionSort(data).toList()}")

    println()
    println("--- Algoritma O(n log n) ---")
    println("Merge sort: ${mergeSort(data).toList()}")
    println("Quick sort: ${quickSort(data).toList()}")
    println("Heap sort:  ${heapSort(data).toList()}")

    println()
    println("--- Kotlin stdlib sorted() ---")
    println("sorted(): ${data.sorted()}")

    println()
    println("--- String sorting ---")
    val names = listOf("Budi", "andi", "Siti", "dewi", "Rina")
    println("Names: $names")
    println("sorted (case-sensitive): ${names.sorted()}")
    println("sortedIgnoringCase: ${names.sortedWith(String.CASE_INSENSITIVE_ORDER)}")

    println()
    println("--- Sort by key (stable) ---")
    data class Produk(val nama: String, val harga: Int)
    val produk = listOf(
        Produk("Buku", 15000),
        Produk("Pulpen", 5000),
        Produk("Penggaris", 3000),
        Produk("Buku Tulis", 15000)
    )
    println("Sort by harga (asc): ${produk.sortedBy { it.harga }}")
    println("Sort by harga (desc): ${produk.sortedByDescending { it.harga }}")
    println("Sort by nama: ${produk.sortedBy { it.nama }}")
}

Output yang Dihasilkan:

text 
=== Demo Sorting Algorithms ===
Data asli: [64, 34, 25, 12, 22, 11, 90, 5, 77, 30]

--- Algoritma O(n^2) ---
Bubble sort:    [5, 11, 12, 22, 25, 30, 34, 64, 77, 90]
Selection sort: [5, 11, 12, 22, 25, 30, 34, 64, 77, 90]
Insertion sort: [5, 11, 12, 22, 25, 30, 34, 64, 77, 90]

--- Algoritma O(n log n) ---
Merge sort: [5, 11, 12, 22, 25, 30, 34, 64, 77, 90]
Quick sort: [5, 11, 12, 22, 25, 30, 34, 64, 77, 90]
Heap sort:  [5, 11, 12, 22, 25, 30, 34, 64, 77, 90]

--- Kotlin stdlib sorted() ---
sorted(): [5, 11, 12, 22, 25, 30, 34, 64, 77, 90]

--- String sorting ---
Names: [Budi, andi, Siti, dewi, Rina]
sorted (case-sensitive): [Budi, Rina, Siti, andi, dewi]
sortedIgnoringCase: [andi, Budi, dewi, Rina, Siti]

--- Sort by key (stable) ---
Sort by harga (asc): [Produk(nama=Penggaris, harga=3000), Produk(nama=Pulpen, harga=5000), Produk(nama=Buku, harga=15000), Produk(nama=Buku Tulis, harga=15000)]
Sort by harga (desc): [Produk(nama=Buku, harga=15000), Produk(nama=Buku Tulis, harga=15000), Produk(nama=Pulpen, harga=5000), Produk(nama=Penggaris, harga=3000)]
Sort by nama: [Produk(nama=Buku, harga=15000), Produk(nama=Buku Tulis, harga=15000), Produk(nama=Penggaris, harga=3000), Produk(nama=Pulpen, harga=5000)]

Bedah Kode Baris-per-Baris #

Mari kita amati bagian kunci:

  1. bubbleSort (baris 4-15): Loop luar i mengurangi jumlah pasangan yang diperiksa tiap iterasi. Loop dalam j membandingkan a[j] dengan a[j+1] dan menukar bila tidak urut. Setiap iterasi luar “menggelembungkan” elemen terbesar ke akhir array.
  2. selectionSort (baris 18-31): Loop dalam mencari indeks minIdx dari elemen minimum di rentang [i..n). Setelah loop, satu kali pertukaran menempatkan minimum di posisi i. Jumlah pertukaran hanya O(n), tetapi jumlah perbandingan tetap O(n²).
  3. insertionSort (baris 34-46): Untuk setiap elemen ke-i, sisipkan ke posisi tepat di bagian kiri yang sudah terurut. Loop while menggeser elemen yang lebih besar ke kanan hingga menemukan posisi yang sesuai. Sangat cepat untuk data hampir terurut karena loop dalam hanya berjalan sedikit.
  4. mergeSort (baris 49-70): Membagi array menjadi dua bagian rekursif hingga tinggal satu elemen (base case size <= 1). Function merge menggabungkan dua array terurut dengan dua pointer berjalan paralel. Kompleksitas O(n log n) di semua kasus karena pembagian selalu setara.
  5. quickSortRec (baris 79-93): Memilih pivot sebagai elemen terakhir (arr[high]). Loop for (j in low until high) mempartisi elemen menjadi <= pivot di kiri dan > pivot di kanan. Indeks i melacak batas antara dua partisi. Setelah partisi, pivot ditukar ke posisi i+1, lalu rekursi pada dua sisi. Worst case O(n²) terjadi bila pivot selalu ekstrem (misalnya data sudah terurut dan pivot selalu elemen terbesar).
  6. heapSort (baris 96-119): Fase pertama membangun max-heap dengan memanggil heapify dari indeks n/2 - 1 ke 0. Fase kedua menukar root (maksimum) dengan elemen akhir, mengecilkan ukuran heap, lalu memanggil heapify pada root untuk memulihkan sifat heap. heapify membandingkan parent dengan kedua anak, menukar dengan yang terbesar bila perlu, lalu rekursi ke bawah.

Function sorted() Bawaan Kotlin #

Kotlin stdlib menyediakan sorted(), sortedBy { }, dan sortedWith(comparator) yang stabil dan optimal untuk kasus umum. Implementasi internal memakai TimSort—varian merge sort adaptif dengan kompleksitas O(n log n). Untuk produksi, lebih baik gunakan API ini daripada implementasi manual.

Penutup #

Pemilihan algoritma sorting bergantung pada ukuran data, sifat data (sudah hampir urut atau acak), dan kebutuhan stabilitas. Untuk data kecil dan pembelajaran, bubble/selection/insertion cukup; untuk data besar, gunakan merge/quick/heap atau langsung sorted() bawaan Kotlin. Pada chapter berikutnya kita akan membahas recursion dan backtracking sebagai fondasi banyak algoritma lanjutan.

Referensi #

Referensi Lanjutan #