Algoritma Sorting Dari Bubble Sort ke Quicksort

Bubble Sort: Dasar Pengurutan yang Sederhana Namun Tidak Efisien

Bubble sort, atau pengurutan gelembung, adalah algoritma pengurutan paling sederhana yang mungkin pernah Anda pelajari di bangku kuliah. Konsepnya sangat mudah dipahami: kita secara berulang membandingkan pasangan elemen yang berdekatan dalam sebuah array, dan menukar posisi mereka jika urutannya salah. Proses ini diulang dari awal array hingga akhir, dan kemudian diulang lagi, hingga tidak ada lagi penukaran yang diperlukan, menandakan bahwa array sudah terurut.

Bayangkan sebuah deretan balon dengan berbagai ukuran. Bubble sort akan seperti menggerakkan setiap balon berdampingan dengan balon di sebelahnya. Jika balon yang lebih besar ada di sebelah kiri balon yang lebih kecil, kita tukar posisinya. Proses ini diulangi berkali-kali sampai balon yang paling besar “mengapung” ke ujung deretan, seperti gelembung.

Contoh sederhana dalam kode Python:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Meskipun mudah dipahami, bubble sort memiliki kelemahan signifikan: kompleksitas waktu. Dalam kasus terburuk (array yang sudah terurut terbalik) dan kasus rata-rata, kompleksitas waktunya adalah O(n^2), yang berarti waktu eksekusi algoritma tumbuh secara kuadratik dengan ukuran input. Ini membuatnya sangat tidak efisien untuk dataset yang besar. Bayangkan mengurutkan jutaan data pelanggan dengan bubble sort – prosesnya akan memakan waktu yang sangat lama.

Selection Sort: Mencari yang Terkecil, Lalu Menempatkannya

Selection sort bekerja dengan cara yang berbeda. Algoritma ini mencari elemen terkecil dalam array yang belum diurutkan, dan menukarnya dengan elemen pertama dalam array yang belum diurutkan. Kemudian, ia mencari elemen terkecil berikutnya, dan menukarnya dengan elemen kedua, dan seterusnya, hingga seluruh array terurut.

Bayangkan Anda memiliki setumpuk kartu remi yang ingin Anda urutkan berdasarkan nilai. Selection sort akan seperti mencari kartu dengan nilai terendah, meletakkannya di posisi pertama, lalu mencari kartu dengan nilai terendah berikutnya dari sisa tumpukan, meletakkannya di posisi kedua, dan seterusnya.

Contoh kode Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

Selection sort juga memiliki kompleksitas waktu O(n^2) di semua kasus (terbaik, rata-rata, dan terburuk). Meskipun secara teoritis sedikit lebih efisien daripada bubble sort dalam beberapa situasi, perbedaan kinerjanya tidak signifikan untuk dataset besar. Salah satu keuntungan kecil adalah selection sort melakukan lebih sedikit penukaran daripada bubble sort, yang bisa menjadi relevan dalam kasus di mana operasi penukaran sangat mahal.

Insertion Sort: Mirip Menyusun Kartu di Tangan

Insertion sort bekerja dengan membangun array yang terurut satu elemen pada satu waktu. Algoritma ini mengambil satu elemen dari array yang belum diurutkan, dan memasukkannya ke posisi yang tepat dalam array yang sudah terurut.

Bayangkan Anda sedang bermain kartu dan menerima kartu satu per satu. Setiap kali Anda menerima kartu baru, Anda akan menyisipkannya di posisi yang tepat di tangan Anda, menjaga agar kartu-kartu Anda selalu terurut. Inilah yang dilakukan insertion sort.

Contoh kode Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j] :
                arr[j + 1] = arr[j]
                j -= 1
        arr[j + 1] = key

Insertion sort memiliki kompleksitas waktu O(n^2) dalam kasus terburuk dan rata-rata, tetapi memiliki kompleksitas waktu O(n) dalam kasus terbaik (array yang sudah terurut). Ini menjadikannya pilihan yang baik untuk mengurutkan array yang sebagian besar sudah terurut, atau untuk mengurutkan array yang sangat kecil. Misalnya, insertion sort sering digunakan sebagai bagian dari algoritma pengurutan yang lebih kompleks, seperti hybrid sorting algorithm, untuk mengurutkan subset data yang kecil.

Merge Sort: Membagi dan Menaklukkan

Merge sort adalah algoritma pengurutan divide-and-conquer. Algoritma ini membagi array menjadi dua bagian yang sama, mengurutkan setiap bagian secara rekursif, dan kemudian menggabungkan kedua bagian yang terurut menjadi satu array yang terurut.

Bayangkan Anda memiliki dua tumpukan kartu remi yang masing-masing sudah terurut. Merge sort akan seperti menggabungkan kedua tumpukan tersebut menjadi satu tumpukan yang terurut, dengan membandingkan kartu teratas dari setiap tumpukan, dan memilih kartu yang lebih kecil untuk diletakkan di tumpukan hasil.

Contoh kode Python (menggunakan rekursi):

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

Merge sort memiliki kompleksitas waktu O(n log n) di semua kasus (terbaik, rata-rata, dan terburuk). Ini menjadikannya algoritma pengurutan yang jauh lebih efisien daripada bubble sort, selection sort, dan insertion sort untuk dataset yang besar. Merge sort juga merupakan algoritma pengurutan yang stabil, yang berarti bahwa elemen dengan nilai yang sama akan mempertahankan urutan aslinya setelah pengurutan. Salah satu kekurangan merge sort adalah membutuhkan ruang tambahan untuk menyimpan array sementara selama proses penggabungan.

Quicksort: Pilihan Cerdas dengan Risiko Tersembunyi

Quicksort, seperti merge sort, adalah algoritma pengurutan divide-and-conquer. Algoritma ini memilih sebuah elemen sebagai pivot, dan kemudian mempartisi array sehingga semua elemen yang lebih kecil dari pivot berada di sebelah kiri pivot, dan semua elemen yang lebih besar dari pivot berada di sebelah kanan pivot. Kemudian, ia mengurutkan sub-array di sebelah kiri dan kanan pivot secara rekursif.

Bayangkan Anda memiliki setumpuk kartu remi dan memilih satu kartu secara acak sebagai pivot. Quicksort akan seperti membagi tumpukan kartu menjadi dua tumpukan: satu tumpukan berisi kartu yang nilainya lebih kecil dari pivot, dan satu tumpukan berisi kartu yang nilainya lebih besar dari pivot. Kemudian, proses ini diulangi untuk setiap tumpukan.

Contoh kode Python:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Quicksort memiliki kompleksitas waktu rata-rata O(n log n), yang menjadikannya salah satu algoritma pengurutan tercepat yang tersedia. Namun, dalam kasus terburuk (ketika pivot selalu elemen terkecil atau terbesar), kompleksitas waktunya menjadi O(n^2). Pilihan pivot yang baik sangat penting untuk kinerja quicksort. Berbagai strategi pemilihan pivot digunakan untuk meminimalkan kemungkinan kasus terburuk. Meskipun quicksort umumnya lebih cepat daripada merge sort, ia bukan algoritma pengurutan yang stabil. Selain itu, quicksort bisa rentan terhadap stack overflow error jika kedalaman rekursi terlalu dalam.

Kesimpulan: Memilih Algoritma yang Tepat

Dari bubble sort yang sederhana hingga quicksort yang canggih, setiap algoritma pengurutan memiliki kelebihan dan kekurangan masing-masing. Bubble sort dan selection sort mudah dipahami tetapi sangat tidak efisien untuk dataset besar. Insertion sort berguna untuk array yang sebagian besar sudah terurut. Merge sort menawarkan kinerja yang konsisten dengan kompleksitas waktu O(n log n), tetapi membutuhkan ruang tambahan. Quicksort umumnya merupakan pilihan yang cepat, tetapi rentan terhadap kasus terburuk dan tidak stabil.

Memilih algoritma pengurutan yang tepat bergantung pada beberapa faktor, termasuk ukuran dataset, tingkat keterurutan data, dan kebutuhan akan stabilitas. Untuk dataset kecil, perbedaan kinerja antara algoritma-algoritma ini mungkin tidak signifikan. Namun, untuk dataset besar, memilih algoritma yang efisien seperti merge sort atau quicksort dapat membuat perbedaan yang signifikan dalam waktu eksekusi. Pertimbangkan kebutuhan spesifik Anda dan pilih algoritma yang paling sesuai dengan kebutuhan tersebut. Apakah ada batasan memori? Apakah data sudah hampir terurut? Pertanyaan-pertanyaan ini akan membantu Anda membuat keputusan yang tepat.