Tutorial Merge Sort di Python

Mengurutkan data adalah salah satu operasi paling umum yang dilakukan praktisi data dalam pekerjaan sehari-hari. Sering kali kita perlu menampilkan data dalam urutan tertentu untuk mengekstrak informasi yang bermakna. Untungnya, saat ini kita tidak perlu melakukan tugas ini secara manual. Komputer dapat melakukan keajaiban ini untuk kita dengan performa yang tak tertandingi.

Ada beberapa strategi untuk mengurutkan data. Dalam tutorial ini, kita akan menganalisis salah satu teknik pengurutan yang paling efektif. Algoritma “merge sort” menggunakan strategi divide-and-conquer untuk mengurutkan sebuah array yang tidak terurut dengan terlebih dahulu memecahnya menjadi array yang lebih kecil, yang kemudian digabungkan kembali dalam urutan yang benar. 

Pada bagian berikutnya, kita akan membahas semua detail algoritma merge sort, seperti apa implementasinya di Python, dan beberapa kiat praktis untuk implementasi yang lancar.

Apa itu Merge Sort?

Ada banyak algoritma pengurutan di luar sana, tetapi sulit menemukan yang kinerjanya lebih baik daripada merge sort. Tidak mengherankan, algoritma ini digunakan dalam berbagai aplikasi dunia nyata, seperti mengurutkan basis data besar atau mengatur file di komputer biasa.

Algoritma ini didasarkan pada paradigma divide-and-conquer, yang dapat diuraikan menjadi tiga bagian:

• Divide: proses ini membagi masalah menjadi submasalah yang lebih kecil. 
• Conquer: submasalah diselesaikan secara rekursif. 
• Combine: solusi dari submasalah digabungkan untuk mencapai solusi akhir.

Strategi divide and conquer

Mari kita lihat bagaimana merge sort bekerja. Misalkan kita ingin mengurutkan angka-angka berikut dengan menerapkan algoritma merge sort. Algoritma akan membagi data secara rekursif menjadi dua bagian dan terus membaginya hingga setiap daftar berisi satu elemen. Lalu, kita menggabungkannya dengan mengurutkannya ke dalam daftar lain.

Masalah Merge Sort. Sumber: DataCamp

Kompleksitas Waktu dan Ruang pada Merge Sort

Tidak mungkin mengetahui sebelumnya algoritma pengurutan mana yang bekerja paling baik untuk masalah tertentu. Ada beberapa variabel yang perlu dipertimbangkan selain algoritma itu sendiri, termasuk bahasa pemrograman yang digunakan untuk menulis kode, perangkat keras tempat algoritma dijalankan, dan kekhasan data yang akan diurutkan. 

Meskipun kita tidak dapat memprediksi waktu eksekusi pasti dari suatu algoritma pengurutan, kita tetap dapat membandingkan kinerja berbagai algoritma pengurutan dengan menganalisis kompleksitas waktu dan ruang.

Kompleksitas waktu pada merge sort

Seperti yang kami jelaskan dalam panduan terpisah tentang Notasi Big O dan Kompleksitas Waktu, tujuan analisis kompleksitas waktu bukan untuk memprediksi waktu eksekusi tepat dari sebuah algoritma, melainkan untuk mengevaluasi seberapa efisien suatu algoritma dengan menganalisis bagaimana waktu eksekusinya berubah ketika jumlah data masukan meningkat.

Analisis kompleksitas waktu ditulis dalam notasi Big O, yaitu notasi matematika yang menggambarkan laju pertumbuhan atau penurunan sebuah fungsi. Merge sort memiliki kompleksitas waktu log-linear atau linearithmic, ditulis sebagai O(N log(N)), di mana N adalah jumlah elemen dalam daftar. Huruf 'O' merupakan singkatan dari 'order' pertumbuhan. 

Dalam analisis kompleksitas waktu, kompleksitas linearithmic berperilaku kurang lebih mirip dengan kompleksitas linear, yang berarti eksekusinya akan berbanding lurus dengan jumlah data. Jadi, jika jumlah data digandakan, waktu yang dibutuhkan algoritma untuk memproses data juga seharusnya menjadi dua kali lipat, yakni jumlah pembagian dan penggabungannya akan berlipat ganda.

Karena kompleksitas waktu merge sort berperilaku secara linear, kompleksitasnya tetap sama untuk skenario terbaik, rata-rata, dan terburuk. Artinya, terlepas dari urutan input, algoritma akan selalu melakukan jumlah langkah yang sama untuk selesai.

Kompleksitas ruang pada merge sort

Akhirnya, selain waktu yang diperlukan untuk menyelesaikan tugas, aspek penting lainnya saat menganalisis kompleksitas algoritma adalah memperkirakan berapa banyak memori yang akan diperlukan algoritma untuk menyelesaikan tugas ketika ukuran masalah semakin besar. 

Hal ini tercakup oleh konsep kompleksitas ruang dan ruang bantu (auxiliary space). Yang terakhir mengacu pada ruang tambahan atau ruang sementara yang digunakan oleh sebuah algoritma, sedangkan yang pertama mengacu pada total ruang yang digunakan oleh algoritma terhadap ukuran input. Dengan kata lain, kompleksitas ruang mencakup ruang bantu dan ruang yang digunakan oleh input.

Merge sort memiliki kompleksitas ruang O(N). Ini karena ia menggunakan array bantu berukuran N untuk menggabungkan dua bagian terurut dari array input. Array bantu digunakan untuk menyimpan hasil gabungan, dan array input ditimpa dengan hasil yang sudah diurutkan.

Implementasi Merge Sort di Python

Mari kita implementasikan algoritma merge sort di Python. Ada beberapa cara untuk menulis kode algoritma ini; namun, kita akan menggunakan pendekatan berbasis rekursi, yang bisa dibilang paling mudah dipahami dan membutuhkan lebih sedikit baris kode dibandingkan alternatif berbasis iterasi.

Memahami rekursi pada merge sort

Jika Anda baru dengan topik ini, dalam pemrograman, rekursi terjadi ketika sebuah fungsi memanggil dirinya sendiri. Anda dapat melihat Tutorial Memahami Fungsi Rekursif di Python kami untuk mempelajari semua hal tentang fungsi-fungsi yang kuat ini.

Untuk mengimplementasikan merge sort, pertama-tama kita menentukan kasus dasar: jika daftar hanya memiliki satu elemen, maka daftar tersebut sudah terurut, jadi kita langsung mengembalikannya. Jika tidak, kita membagi daftar menjadi dua bagian, left_half dan right_half, lalu memanggil merge_sort() secara rekursif pada masing-masing bagian. Proses ini berlanjut hingga semua subdaftar berisi satu elemen.

Setelah kita memiliki subdaftar yang sudah terurut ini, kita mulai proses penggabungan. Untuk melakukannya, kita menginisialisasi tiga variabel indeks: i untuk melacak posisi pada left_half, j untuk right_half, dan k untuk daftar gabungan akhir. Lalu, kita membandingkan elemen dari kedua bagian. Jika elemen saat ini di left_half lebih kecil, kita menempatkannya di my_list[k] dan memajukan i. Jika tidak, kita mengambil elemen dari right_half, menempatkannya di my_list[k], dan menambah j. Setelah setiap perbandingan, kita memajukan k ke posisi berikutnya dalam daftar akhir.

Proses ini berlanjut hingga kita telah membandingkan semua elemen di salah satu bagian. Jika masih ada elemen yang tersisa di left_half atau right_half, kita menambahkannya langsung ke daftar akhir, memastikan tidak ada data yang tertinggal. Karena merge sort beroperasi secara rekursif, proses penggabungan ini dijalankan pada setiap level rekursi hingga seluruh daftar terurut.

Implementasi Python

Di bawah ini, Anda dapat menemukan kodenya menggunakan daftar tidak terurut dari diagram sebelumnya sebagai contoh:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]Didukung oleh

Merge Sort vs Algoritma Pengurutan Lain

Merge sort adalah algoritma pengurutan yang cukup cepat, sangat cocok untuk basis data besar, dan sering digunakan sebagai tolok ukur bagi algoritma lain. Namun, untuk daftar yang lebih pendek, kinerjanya cenderung lebih rendah dibandingkan algoritma pengurutan lainnya.

Pada tabel berikut, Anda dapat menemukan perbandingan antara merge sort dan algoritma pengurutan populer lainnya.

Aplikasi Praktis Merge Sort

Merge sort memiliki performa tinggi saat mengurutkan daftar besar, tetapi efisiensinya menurun saat bekerja dengan daftar yang lebih kecil. Demikian juga, algoritma ini cenderung kurang efisien dalam skenario di mana sudah ada tingkat keterurutan pada daftar input, karena merge sort akan melakukan langkah yang sama apa pun urutan daftarnya.

Salah satu kasus penggunaan yang sangat cocok untuk merge sort adalah linked list. Linked list adalah struktur data yang terdiri dari kumpulan node yang terhubung satu sama lain secara linear. Setiap node berisi data dan tautan untuk menghubungkannya dengan node berikutnya.

Merge sort lebih disukai untuk linked list karena hanya memerlukan akses data secara sekuensial, yang selaras dengan sifat linked list. Selain itu, merge sort adalah algoritma pengurutan yang stabil (yaitu mempertahankan urutan relatif elemen yang sama pada keluaran yang terurut), yang merupakan pertimbangan sangat penting untuk menjaga keterurutan linked list.

Kesalahan Umum dan Pemecahan Masalah

Algoritma merge sort cukup lugas, dan ruang untuk perbaikan pada kodenya terbatas. Namun, Anda dapat meningkatkan kompleksitas strategi pengurutan dengan mempertimbangkan ukuran data masukan. 

Kita sudah menetapkan bahwa merge sort bekerja lebih baik dengan dataset yang lebih besar. Untuk dataset yang lebih kecil, algoritma pengurutan lain dengan kompleksitas waktu O(N^2), seperti insertion sort, bisa jadi bekerja lebih baik. Dalam kasus ini, Anda hanya perlu membuat ambang batas ukuran di bawahnya Anda akan memilih algoritma insertion sort alih-alih merge sort.

Selain itu, ide bagus lainnya untuk dieksplorasi adalah paralelisasi. Langkah-langkah merge sort dapat dengan mudah diparalelkan dengan daya komputasi yang tepat, sehingga mengurangi waktu penyelesaian. Baca panduan CPU vs GPU kami untuk mempelajari lebih lanjut tentang komputasi paralel. 

Kesimpulan

Merge sort adalah salah satu algoritma pengurutan yang paling efektif dan populer, tetapi masih banyak hal untuk dipelajari di dunia algoritma yang menakjubkan dan terus berkembang. Jika Anda tertarik pada aspek teknis algoritma, cara kerjanya, serta kompleksitas, keunggulan, dan kelemahannya, sumber daya DataCamp berikut dapat membantu Anda melanjutkan pembelajaran:

• Kursus Pengantar Struktur Data dan Algoritma 
• Skill Track Pemrograman Python
• Skill Track Dasar-dasar Data Python
• Kursus Python Tingkat Menengah
• Career Track Analis Data dengan Python 
• Notasi Big O dan Kompleksitas Waktu