Bubble Sort Vs Merge Sort: Contoh Implementasi Mudah

Hey guys! Pernah nggak sih kalian penasaran gimana sih cara kerja algoritma sorting yang sering banget kita dengar, kayak Bubble Sort dan Merge Sort? Dua algoritma ini memang jadi bahan pembicaraan klasik di dunia pemrograman. Keduanya punya cara kerja yang beda banget, dan implikasinya juga terasa di performa program kita. Nah, di artikel ini, kita bakal bedah tuntas contoh implementasi Bubble Sort dan Merge Sort pakai bahasa pemrograman Python. Kita akan lihat gimana sih mereka bekerja langkah demi langkah, plus sedikit bahas kelebihan dan kekurangannya. Jadi, siapin kopi kalian, dan mari kita mulai petualangan kita ke dunia algoritma sorting!

Memahami Algoritma Bubble Sort: Cara Kerja Sederhana tapi Lambat

Oke, pertama kita bahas Bubble Sort. Sesuai namanya, algoritma ini bekerja dengan cara membandingkan elemen-elemen yang berdekatan satu per satu dan menukarnya jika urutannya salah. Proses ini diulang terus menerus sampai seluruh array terurut. Ibaratnya kayak gelembung udara yang naik ke permukaan, elemen terkecil atau terbesar bakal 'menggelembung' ke posisi yang seharusnya. Bayangin kalian punya tumpukan kartu yang belum urut, dan kalian membandingkan kartu pertama sama kartu kedua, kalau salah ya ditukar. Terus kartu kedua sama ketiga, kalau salah ditukar lagi. Sampai akhir, kalau nggak ada pertukaran sama sekali di satu putaran penuh, berarti kartunya udah urut, guys! Makanya, contoh implementasi bubble sort ini sering jadi algoritma pertama yang diajarkan karena konsepnya paling mudah dicerna. Tapi, jangan salah, kesederhanaannya ini yang bikin dia jadi kurang efisien buat data yang banyak. Kenapa? Karena dia harus bolak-balik membandingkan elemen yang mungkin udah di posisi yang benar berkali-kali. Time complexity-nya di kasus terburuk dan rata-rata itu O(n^2), yang artinya kalau datanya 1000, operasinya bisa jadi jutaan kali! Nggak kebayang kan kalau datanya jutaan? Makanya, buat data yang kecil-kecil atau udah hampir urut, Bubble Sort masih oke lah. Tapi buat aplikasi beneran yang butuh performa tinggi, mending lirik algoritma lain.

Implementasi Bubble Sort dalam Python

Biar lebih kebayang, yuk kita lihat kodenya dalam Python. Gampang kok! Kita pakai contoh array [64, 34, 25, 12, 22, 11, 90].

def bubble_sort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n):
        # Last i elements are already in place
        swapped = False
        for j in range(0, n-i-1):
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j] # Tukar elemen
                swapped = True
        # If no two elements were swapped by inner loop, then break
        if swapped == False:
            break
    return arr

# Contoh penggunaan
my_array = [64, 34, 25, 12, 22, 11, 90]
print("Array sebelum diurutkan:", my_array)

sorted_array = bubble_sort(my_array)
print("Array setelah diurutkan dengan Bubble Sort:", sorted_array)

Di kode ini, n itu panjang array. Loop luar (for i in range(n)) itu buat nentuin berapa kali kita harus bolak-balik ngecek. Loop dalam (for j in range(0, n-i-1)) itu yang beneran ngebandingin elemen berdekatan. n-i-1 karena elemen terakhir udah pasti di tempatnya setelah setiap putaran. Nah, yang seru itu ada variabel swapped. Kalau dalam satu putaran penuh nggak ada yang ditukar (swapped tetap False), berarti arraynya udah urut dan kita bisa langsung break dari loop biar nggak buang-buang waktu. Ini optimasi kecil tapi penting. Hasilnya, array [64, 34, 25, 12, 22, 11, 90] akan jadi [11, 12, 22, 25, 34, 64, 90]. Gimana, gampang kan? Tapi inget, ini buat contoh aja ya, jangan dipakai buat data besar!

Menyelami Algoritma Merge Sort: Efisien dengan Pendekatan Divide and Conquer

Sekarang, kita pindah ke Merge Sort. Kalau Bubble Sort itu sederhana tapi lambat, Merge Sort ini kebalikannya: lebih kompleks konsepnya, tapi jauh lebih efisien, terutama buat data yang besar. Contoh implementasi merge sort ini pakai strategi yang namanya Divide and Conquer. Apa tuh? Jadi, array yang mau diurutkan itu dibagi-bagi terus sampai jadi bagian-bagian kecil yang cuma terdiri dari satu elemen (yang otomatis dianggap udah terurut). Setelah itu, bagian-bagian kecil ini digabung lagi (di-merge) secara berpasangan dengan urutan yang benar. Proses penggabungannya ini yang krusial. Misalnya, ada dua subarray yang udah terurut, kita mau gabungin. Kita ambil elemen terkecil dari kedua subarray itu, taruh di array baru, terus lanjutin sampai semua elemen dari kedua subarray habis. Proses ini diulang terus sampai semua bagian kecil tadi gabung jadi satu array utuh yang udah terurut sempurna. Kayak menyusun puzzle gitu, guys. Dari potongan-potongan kecil, disusun jadi gambar besar yang rapi. Kelebihan utamanya Merge Sort itu stabilitas dan time complexity-nya yang konsisten bagus, yaitu O(n log n) di semua kasus (terbaik, rata-rata, terburuk). Ini jauh lebih baik dari O(n^2) milik Bubble Sort. Makanya, Merge Sort jadi pilihan favorit buat aplikasi yang butuh sorting super cepat dan andal, kayak di database atau sistem operasi.

Implementasi Merge Sort dalam Python

Kode Merge Sort memang sedikit lebih panjang dan rumit dibanding Bubble Sort, tapi konsepnya tetap seru buat dipelajari. Yuk, kita pakai array yang sama: [64, 34, 25, 12, 22, 11, 90].

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2 # Cari titik tengah array
        L = arr[:mid] # Buat subarray kiri
        R = arr[mid:] # Buat subarray kanan

        # Panggil merge_sort secara rekursif buat kedua subarray
        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        # Copy data ke temp arrays L[] dan R[]
        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

        # Cek apakah ada sisa elemen di L
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        # Cek apakah ada sisa elemen di R
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

# Contoh penggunaan
my_array_merge = [64, 34, 25, 12, 22, 11, 90]
print("\nArray sebelum diurutkan:", my_array_merge)

sorted_array_merge = merge_sort(my_array_merge)
print("Array setelah diurutkan dengan Merge Sort:", sorted_array_merge)

Logika di sini adalah rekursi. Fungsi merge_sort akan terus memanggil dirinya sendiri untuk memecah array jadi dua sampai ukurannya jadi 1. Setelah itu, proses penggabungan (merge) dimulai. Bagian while i < len(L) and j < len(R): itu intinya membandingkan elemen dari subarray kiri (L) dan kanan (R), lalu menaruh yang lebih kecil ke array utama (arr). Kalau salah satu subarray udah habis elemennya, sisa elemen dari subarray lain tinggal dimasukkin aja. Voilà! Array [64, 34, 25, 12, 22, 11, 90] pun akan jadi [11, 12, 22, 25, 34, 64, 90]. Kelihatan lebih 'canggih' kan? Tapi itulah hebatnya Divide and Conquer, memecah masalah besar jadi kecil, lalu menyatukannya kembali dengan solusi yang efisien.

Perbandingan Kinerja: Kapan Pakai yang Mana?

Setelah kita lihat contoh implementasi bubble sort dan merge sort, sekarang saatnya kita bandingkan langsung performanya. Singkatnya gini, guys: kalau kamu lagi ngerjain proyek kecil-kecilan, data yang mau diurutkan nggak banyak (misalnya di bawah 100 elemen), atau kamu lagi belajar konsep dasar sorting, Bubble Sort bisa jadi pilihan yang menyenangkan karena kodenya simpel dan mudah dipahami. Tapi, kalau performa itu krusial, atau data yang kamu hadapi itu besar (ribuan, jutaan, atau lebih), Merge Sort jelas juaranya. Time complexity O(n log n) bikin dia jauh lebih cepat dan skalabel dibandingkan O(n^2) milik Bubble Sort. Bayangin aja bedanya antara 1000 operasi bandingin sama 1.000.000 operasi bandingin! Itu beda dunia, lho. Selain itu, Merge Sort juga punya sifat stabil, artinya kalau ada dua elemen yang nilainya sama, urutan relatif mereka di array asli akan tetap terjaga setelah diurutkan. Bubble Sort juga stabil sih, tapi performanya itu lho, yang jadi masalah utama. Jadi, untuk memilih algoritma yang tepat, selalu pertimbangkan ukuran data, kebutuhan kecepatan, dan kompleksitas implementasi yang kamu inginkan. Pilihlah alat yang sesuai dengan pekerjaanmu, ya!

Kesimpulan: Dua Wajah Sorting yang Berbeda

Gimana, guys? Sekarang udah lebih tercerahkan kan soal Bubble Sort dan Merge Sort? Kita udah lihat contoh implementasi bubble sort yang sederhana tapi punya kelemahan di performa, dan contoh implementasi merge sort yang lebih kompleks tapi sangat efisien buat data besar. Keduanya punya tempatnya masing-masing dalam dunia pemrograman. Bubble Sort mengajarkan kita konsep dasar perbandingan dan penukaran elemen yang mudah dipahami. Sementara Merge Sort menunjukkan kekuatan strategi Divide and Conquer yang bisa menyelesaikan masalah besar dengan cara yang cerdas dan efisien. Memahami kedua algoritma ini nggak cuma nambah insight kamu tentang sorting, tapi juga ngebantu kamu bikin keputusan yang lebih baik saat memilih algoritma yang paling cocok buat kebutuhan coding kamu. Ingat, knowledge is power, apalagi di dunia teknologi yang terus berkembang! Terus belajar dan bereksperimen ya, guys!