Searching and Sorting

Penjelasan Komprehensif Algoritma Sorting dan Searching

Algoritma sorting dan searching merupakan fondasi penting dalam pemrograman, terutama untuk wawancara software engineer. Penjelasan ini telah diperkaya dengan detail mekanisme kerja, perhitungan Big O berdasarkan analisis matematis, serta contoh kode dalam Go. Big O dihitung berdasarkan jumlah operasi dasar seperti perbandingan dan swap, dengan mempertimbangkan kasus terbaik (best case), rata-rata (average case), dan terburuk (worst case). Saya menggunakan sumber terpercaya untuk verifikasi, seperti GeeksforGeeks dan Khan Academy, untuk memastikan akurasi. Secara umum, sorting mengurutkan data untuk efisiensi, sementara searching mencari elemen dengan cepat, dan pemahaman Big O membantu memilih algoritma yang tepat berdasarkan ukuran data.

Poin Kunci Utama:

  • Sorting Algorithms: Efisiensi bervariasi; O(n²) seperti Bubble Sort cocok untuk data kecil, sementara O(n log n) seperti Merge Sort lebih baik untuk data besar, meskipun ada trade-off seperti stabilitas dan ruang memori. Penelitian menunjukkan bahwa untuk data acak, Quick Sort sering kali lebih cepat secara praktis meskipun worst case O(n²).

  • Searching Algorithms: Linear Search sederhana tapi lambat (O(n)), sedangkan Binary Search cepat (O(log n)) tapi memerlukan data terurut terlebih dahulu. Dalam praktik, Binary Search mengurangi waktu pencarian secara signifikan untuk dataset besar.

  • Perhitungan Big O: Dihitung dari recurrence relation atau loop nested; misalnya, loop ganda menghasilkan O(n²), sementara divide-and-conquer seperti Merge Sort menghasilkan O(n log n) melalui logaritma tingkat rekursi. Selalu pertimbangkan asumsi seperti data acak untuk average case.

  • Rekomendasi: Untuk interview, latihlah implementasi dan jelaskan trade-off; gunakan Go untuk keefisienan, tapi konsep sama di bahasa lain.

Ringkasan Kompleksitas Sorting Berikut tabel perbandingan untuk memudahkan pemahaman, berdasarkan analisis standar:

Algoritma
Waktu Terbaik
Waktu Rata-rata
Waktu Terburuk
Ruang
Stabil?
In-Place?

Bubble Sort

O(n)

O(n²)

O(n²)

O(1)

Ya

Ya

Selection Sort

O(n²)

O(n²)

O(n²)

O(1)

Tidak

Ya

Insertion Sort

O(n)

O(n²)

O(n²)

O(1)

Ya

Ya

Merge Sort

O(n log n)

O(n log n)

O(n log n)

O(n)

Ya

Tidak

Quick Sort

O(n log n)

O(n log n)

O(n²)

O(log n)

Tidak

Ya

Heap Sort

O(n log n)

O(n log n)

O(n log n)

O(1)

Tidak

Ya

Counting Sort

O(n + k)

O(n + k)

O(n + k)

O(k)

Ya

Tidak

Ringkasan Kompleksitas Searching Tabel ini menyoroti perbedaan utama:

Algoritma
Waktu Terbaik
Waktu Rata-rata
Waktu Terburuk
Ruang
Syarat

Linear Search

O(1)

O(n)

O(n)

O(1)

Tidak ada

Binary Search

O(1)

O(log n)

O(log n)

O(1)

Array terurut

Implementasi dalam Go Semua kode di bawah ini dapat diuji langsung; gunakan package main untuk contoh sederhana.

Algoritma sorting dan searching adalah elemen krusial dalam ilmu komputer, sering diuji dalam wawancara karena mencerminkan kemampuan analisis efisiensi. Penjelasan ini mencakup intuisi, mekanisme kerja langkah demi langkah, perhitungan Big O secara matematis (termasuk derivation dari recurrence relation atau loop count), kode implementasi dalam Go, serta contoh penggunaan. Analisis Big O didasarkan pada jumlah operasi dasar seperti perbandingan (comparison) dan assignment (swap atau copy), dengan mempertimbangkan kasus terbaik (data sudah urut), rata-rata (data acak), dan terburuk (data terbalik atau tidak seimbang). Saya juga menyertakan trade-off seperti stabilitas (apakah urutan elemen sama dipertahankan) dan in-place (apakah memerlukan memori ekstra). Untuk sorting, fokus pada comparison-based kecuali Counting Sort yang non-comparison. Untuk searching, Linear cocok untuk data kecil atau tidak terurut, sementara Binary unggul untuk data besar terurut.

Bubble Sort: Algoritma Sorting Sederhana dengan Swap Berpasangan

Intuisi: Bayangkan gelembung naik ke atas air—elemen besar "menggelembung" ke akhir array melalui swap berulang. Cocok untuk pemula tapi tidak efisien untuk data besar karena banyak perbandingan berulang. Mekanisme Kerja:

  1. Mulai dari awal array, bandingkan elemen berdekatan (arr[j] dan arr[j+1]).

  2. Jika arr[j] > arr[j+1], tukar posisi.

  3. Ulangi untuk seluruh array (pass pertama mengurutkan elemen terbesar ke akhir).

  4. Ulangi pass hingga n-1 kali, kurangi ukuran per pass karena akhir sudah urut.

  5. Optimasi: Gunakan flag swapped; jika tak ada swap di satu pass, array sudah urut dan berhenti dini. Ini stabil (urutan elemen sama dipertahankan) dan in-place (hanya O(1) memori ekstra untuk variabel temp). Perhitungan Big O:

  • Waktu: Di worst case (array terbalik), setiap pass i (i=1 to n-1) lakukan n-i perbandingan dan swap. Total perbandingan: ∑(n-i) dari i=1 ke n-1 = (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ O(n²). Average case serupa karena asumsi data acak. Best case (sudah urut): Hanya 1 pass dengan n-1 perbandingan, O(n).

  • Ruang: O(1), hanya variabel sementara, tidak bergantung pada n. Kode Go:

package main
import "fmt"
func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = true
            }
        }
        if !swapped { break }
    }
}
func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    bubbleSort(arr)
    fmt.Println("Array terurut:", arr) // [11 12 22 25 34 64 90]
}

Contoh: Untuk array [5,3,8,4], pass 1: [3,5,4,8] (swap 5-3, 5-4); pass 2: [3,4,5,8] (swap 5-4). Total 6 perbandingan untuk n=4, mendekati n²/2=8.

Selection Sort: Pemilihan Elemen Minimum Berulang

Intuisi: Seperti memilih pemain terbaik untuk tim—cari elemen terkecil di subarray tak terurut, tukar ke depan. Lebih sedikit swap daripada Bubble, tapi tetap banyak perbandingan. Mekanisme Kerja:

  1. Untuk setiap i dari 0 ke n-2, asumsikan min di i.

  2. Scan dari i+1 ke n-1, update min jika temukan lebih kecil.

  3. Tukar arr[i] dengan arr[min] jika berbeda.

  4. Ulangi hingga subarray tak terurut habis. Tidak stabil (urutan elemen sama bisa berubah), tapi in-place. Perhitungan Big O:

  • Waktu: Selalu O(n²)—untuk setiap i, scan n-i elemen. Total: ∑(n-i) = n(n-1)/2 ≈ O(n²) untuk semua kasus, karena tak ada early stop.

  • Ruang: O(1), hanya index min dan swap. Kode Go:

func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}

Contoh: Array [5,3,8,4]—pass 1: min=3, tukar jadi [3,5,8,4]; pass 2: min=4, tukar [3,4,8,5]; pass 3: min=5, tukar [3,4,5,8]. Total perbandingan: 3+2+1=6 untuk n=4.

Insertion Sort: Penyisipan Elemen ke Subarray Terurut

Intuisi: Seperti mengurutkan kartu di tangan—ambil elemen baru, geser elemen lebih besar untuk sisipkan di posisi benar. Efisien untuk data hampir urut. Mekanisme Kerja:

  1. Asumsikan subarray pertama (indeks 0) sudah urut.

  2. Untuk i=1 ke n-1, ambil key=arr[i].

  3. Geser elemen > key di subarray [0..i-1] ke kanan.

  4. Sisipkan key di posisi kosong. Stabil dan in-place. Perhitungan Big O:

  • Waktu: Worst/average: O(n²), karena untuk setiap i, bisa geser hingga i elemen (∑i dari 1 ke n-1 = n(n-1)/2). Best: O(n), jika sudah urut, hanya perbandingan tanpa geser.

  • Ruang: O(1). Kode Go:

func insertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

Contoh: [5,3,8,4]—i=1: geser 5, jadi [3,5,8,4]; i=2: tak geser; i=3: geser 8 dan 5, jadi [3,4,5,8].

Merge Sort: Divide and Conquer dengan Penggabungan

Intuisi: Bagi array jadi dua, urutkan rekursif, gabung urut—like memecah masalah besar jadi kecil lalu gabung solusi. Mekanisme Kerja:

  1. Bagi array jadi dua hingga subarray tunggal (basis rekursi).

  2. Gabung dua subarray urut: bandingkan elemen depan, ambil kecil, ulangi hingga habis.

  3. Gunakan array sementara untuk gabung. Stabil, tapi tidak in-place. Perhitungan Big O:

  • Waktu: Recurrence: T(n) = 2T(n/2) + O(n) (bagi + gabung). Solusi Master Theorem: O(n log n) untuk semua kasus, karena log n tingkat rekursi, tiap tingkat O(n) gabung.

  • Ruang: O(n) untuk array sementara. Kode Go:

func mergeSort(arr []int) []int {
    if len(arr) <= 1 { return arr }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}
func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] < right[j] { result = append(result, left[i]); i++ } else { result = append(result, right[j]); j++ }
    }
    return append(append(result, left[i:]...), right[j:]...)
}

Contoh: [5,3,8,4]—bagi [5,3] dan [8,4]; urut [3,5] dan [4,8]; gabung [3,4,5,8].

Quick Sort: Partisi Cepat dengan Pivot

Intuisi: Pilih pivot, partisi array jadi pivot, rekursif—like keputusan cepat memisah kelompok. Mekanisme Kerja:

  1. Pilih pivot (misal akhir).

  2. Partisi: pointer i scan kecil, tukar dengan >pivot.

  3. Tukar pivot ke posisi benar.

  4. Rekursi subarray kiri dan kanan. Tidak stabil, tapi in-place. Perhitungan Big O:

  • Waktu: Average/best: T(n)=2T(n/2)+O(n) → O(n log n). Worst (pivot buruk, partisi 1 dan n-1): T(n)=T(n-1)+O(n) → O(n²).

  • Ruang: O(log n) rekursi rata-rata, O(n) worst. Kode Go:

func quickSort(arr []int, low, high int) {
    if low < high {
        pi := partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}
func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] < pivot { i++; arr[i], arr[j] = arr[j], arr[i] }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

Contoh: [5,3,8,4], pivot=4: partisi [3,5,8,4] → [3,4,8,5]; rekursi.

Heap Sort: Sorting Menggunakan Binary Heap

Intuisi: Bangun max-heap (parent > child), ekstrak max berulang—like turnamen di mana pemenang (root) diambil dan heap direstrukturisasi. Mekanisme Kerja:

  1. Bangun max-heap: heapify dari tengah ke atas.

  2. Tukar root (max) dengan akhir, kurangi heap size.

  3. Heapify root ulang. Tidak stabil, in-place. Perhitungan Big O:

  • Waktu: Build heap O(n), tiap ekstrak O(log n) x n = O(n log n). Total O(n log n) semua kasus, karena height heap log n.

  • Ruang: O(1). Kode Go:

func heapSort(arr []int) {
    n := len(arr)
    for i := n/2 - 1; i >= 0; i-- { heapify(arr, n, i) }
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
}
func heapify(arr []int, n, i int) {
    largest := i
    l, r := 2*i+1, 2*i+2
    if l < n && arr[l] > arr[largest] { largest = l }
    if r < n && arr[r] > arr[largest] { largest = r }
    if largest != i { arr[i], arr[largest] = arr[largest], arr[i]; heapify(arr, n, largest) }
}

Contoh: [5,3,8,4]—build heap [8,4,5,3]; ekstrak 8 → [5,4,3,8], heapify dst.

Counting Sort: Sorting Non-Comparison untuk Rentang Terbatas

Intuisi: Hitung frekuensi nilai, rekonstruksi array—like menghitung suara dan susun berdasarkan jumlah. Mekanisme Kerja:

  1. Temukan max k, buat count array [0..k].

  2. Hitung frekuensi setiap nilai.

  3. Modifikasi count jadi posisi kumulatif.

  4. Bangun output dari akhir untuk stabilitas. Stabil, tidak in-place, cocok untuk integer rentang kecil. Perhitungan Big O:

  • Waktu: O(n + k)—loop n untuk hitung, k untuk kumulatif dan output. Semua kasus sama karena linear.

  • Ruang: O(k). Kode Go (asumsi non-negatif):

func countingSort(arr []int, maxVal int) []int {
    count := make([]int, maxVal+1)
    for _, val := range arr { count[val]++ }
    for i := 1; i <= maxVal; i++ { count[i] += count[i-1] }
    sorted := make([]int, len(arr))
    for i := len(arr)-1; i >= 0; i-- {
        sorted[count[arr[i]]-1] = arr[i]
        count[arr[i]]--
    }
    return sorted
}

Contoh: [5,3,3,4]—count[3]=2, [4]=1, [5]=1; kumulatif [0,0,0,2,3,4]; output [3,3,4,5].

Linear Search: Pencarian Sekuensial Sederhana

Intuisi: Cek setiap elemen satu per satu seperti mencari nama di daftar telepon tak terurut—mudah tapi lambat untuk daftar panjang. Mekanisme Kerja:

  1. Mulai dari indeks 0.

  2. Bandingkan dengan target; jika cocok, kembalikan indeks.

  3. Lanjut hingga akhir; jika tidak ada, -1. Tidak memerlukan sorting awal. Perhitungan Big O:

  • Waktu: Worst: O(n), cek semua. Average: O(n/2) ≈ O(n). Best: O(1), jika di awal.

  • Ruang: O(1). Kode Go:

func linearSearch(arr []int, target int) int {
    for i, val := range arr {
        if val == target { return i }
    }
    return -1
}

Contoh: [5,3,8,4], target=8: cek 5(no),3(no),8(ya)—indeks 2, 3 perbandingan.

Binary Search: Pencarian Divide-and-Conquer pada Data Terurut

Intuisi: Bagi rentang jadi dua berulang seperti tebak angka (lebih tinggi/rendah)—efisien karena kurangi separuh pencarian tiap langkah. Mekanisme Kerja:

  1. Set low=0, high=n-1.

  2. Hitung mid=(low+high)/2.

  3. Jika arr[mid]==target, kembalikan mid.

  4. Jika <, low=mid+1; jika >, high=mid-1.

  5. Ulang hingga low>high. Memerlukan array terurut; bisa rekursif atau iteratif. Perhitungan Big O:

  • Waktu: Recurrence T(n)=T(n/2)+O(1). Solusi: O(log n), karena bagi 2 tiap langkah hingga 1 (log2 n langkah).

  • Ruang: O(1) iteratif, O(log n) rekursif. Kode Go:

func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        mid := low + (high-low)/2
        if arr[mid] == target { return mid }
        if arr[mid] < target { low = mid + 1 } else { high = mid - 1 }
    }
    return -1
}

Contoh: [3,4,5,8], target=5: mid=4 (indeks 1), <5 → low=2; mid=2 (5), ya—2 langkah untuk n=4 (log2 4=2).

Penjelasan ini komprehensif untuk persiapan interview; latihlah variasi seperti handling duplikat atau optimasi pivot di Quick Sort untuk pertanyaan lanjutan.

Key Citations

PreviousFuzzy Search vs FTSNextTree

Last updated