algoritma merge sort

Algoritma Merge Sort: Pengertian, Cara Kerja dan Implementasi

Algoritma Merge Sort adalah salah satu algoritma pengurutan yang terkenal dalam ilmu komputer. Algoritma ini dikenal karena efisiensinya dalam menangani berbagai jenis data dan kemampuannya untuk bekerja dengan kompleksitas waktu yang stabil.

Dalam artikel ini, kita akan membahas algoritma Merge Sort secara mendalam, termasuk cara kerjanya, implementasinya, serta kelebihan dan kekurangannya.

Apa Itu Algoritma Merge Sort

Algoritma Merge Sort pertama kali diperkenalkan oleh John von Neumann pada tahun 1945. Algoritma ini merupakan contoh dari teknik “divide and conquer“, di mana masalah besar dipecah menjadi sub-masalah yang lebih kecil dan lebih mudah dipecahkan. Merge Sort bekerja dengan membagi array atau daftar yang ingin diurutkan menjadi dua bagian yang lebih kecil, mengurutkan masing-masing bagian dan kemudian menggabungkannya kembali menjadi satu daftar yang terurut.

Cara Kerja Algoritma Merge Sort

Mari kita lihat contoh langkah demi langkah untuk lebih memahami cara kerja algoritma ini:

1.Langkah-langkah Merge Sort

  1. Pembagian (Divide):
    • Langkah pertama dalam adalah membagi array yang akan diurutkan menjadi dua bagian yang lebih kecil. Proses ini dilakukan secara rekursif hingga setiap bagian hanya mengandung satu elemen. Pada titik ini, setiap elemen dianggap sudah terurut.
  2. Penggabungan (Conquer):
    • Setelah array dipecah menjadi bagian-bagian kecil, langkah berikutnya adalah menggabungkan bagian-bagian ini kembali menjadi satu array yang terurut. Penggabungan ini dilakukan dengan membandingkan elemen-elemen dari dua bagian yang berbeda dan menyusunnya dalam urutan yang benar.

2.Ilustrasi Cara Kerja Merge Sort

Misalkan kita memiliki array berikut yang ingin diurutkan: [38, 27, 43, 3, 9, 82, 10].

1. Pembagian (Divide):

  • Bagilah array menjadi dua bagian: [38, 27, 43, 3] dan [9, 82, 10].
  • Lanjutkan membagi setiap bagian hingga hanya ada satu elemen di setiap bagian:
    • [38, 27, 43, 3] menjadi [38, 27] dan [43, 3].
    • [9, 82, 10] menjadi [9, 82] dan [10].
    • [38, 27] menjadi [38] dan [27].
    • [43, 3] menjadi [43] dan [3].
    • [9, 82] menjadi [9] dan [82].
Baca juga :   Metode Agile Adalah: Pengertian, Cara Kerja, Prinsip dan Manfaat

Pada titik ini, kita memiliki sub-array yang hanya mengandung satu elemen:

  • [38], [27], [43], [3], [9], [82], [10].

2. Penggabungan (Conquer):

  • Mulai gabungkan sub-array yang hanya mengandung satu elemen:
    • Gabungkan [38] dan [27] menjadi [27, 38].
    • Gabungkan [43] dan [3] menjadi [3, 43].
    • Gabungkan [9] dan [82] menjadi [9, 82].
    • [10] tetap sebagai [10] karena sudah terurut dan hanya satu elemen.
  • Lanjutkan proses penggabungan:
    • Gabungkan [27, 38] dan [3, 43] menjadi [3, 27, 38, 43].
    • Gabungkan [9, 82] dan [10] menjadi [9, 10, 82].
  • Penggabungan terakhir:
    • Gabungkan [3, 27, 38, 43] dan [9, 10, 82] menjadi [3, 9, 10, 27, 38, 43, 82].

Sekarang kita memiliki array yang sudah terurut: [3, 9, 10, 27, 38, 43, 82].

Implementasi Kode Merge Sort

Implementasi Merge Sort dalam Python

Berikut adalah implementasi dalam bahasa pemrograman Python:

def merge_sort(arr):
    if len(arr) > 1:
        
        mid = len(arr) // 2  
        
        left_half = arr[:mid]  
        right_half = arr[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]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
       
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
       
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("Array yang sudah diurutkan:", arr)

Penjelasan Implementasi

  1. Fungsi merge_sort(arr): Fungsi ini adalah fungsi utama untuk mengurutkan array arr. Jika panjang array lebih dari satu, array akan dibagi menjadi dua bagian, left_half dan right_half.
  2. Pembagian Rekursif: Fungsi merge_sort dipanggil secara rekursif untuk left_half dan right_half hingga setiap bagian hanya mengandung satu elemen.
  3. Penggabungan: Dua bagian yang terpisah kemudian digabungkan kembali menjadi satu array yang terurut. Ini dilakukan dengan membandingkan elemen dari left_half dan right_half satu per satu dan menyusunnya dalam urutan yang benar.
  4. Menggabungkan Sisa Elemen: Setelah perbandingan utama selesai, sisa elemen di left_half dan right_half ditambahkan kembali ke array arr.

Implementasi Merge Sort dalam PHP

Berikut adalah implementasi dalam bahasa pemrograman PHP beserta penjelasannya.

<?php
function mergeSort($arr) {

    if(count($arr) <= 1) {
        return $arr;
    }

    $middle = floor(count($arr) / 2);

    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);

    $left = mergeSort($left);
    $right = mergeSort($right);

    return merge($left, $right);
}

function merge($left, $right) {
    $result = array();
    $i = 0;
    $j = 0;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $result[] = $left[$i];
            $i++;
        } else {
            $result[] = $right[$j];
            $j++;
        }
    }

    while ($i < count($left)) {
        $result[] = $left[$i];
        $i++;
    }

    while ($j < count($right)) {
        $result[] = $right[$j];
        $j++;
    }

    return $result;
}

$arr = array(38, 27, 43, 3, 9, 82, 10);
$arr = mergeSort($arr);
print("Array yang sudah diurutkan: ");
print_r($arr);
?>

Penjelasan Implementasi

  1. Fungsi mergeSort($arr):
    • Fungsi ini adalah fungsi utama yang digunakan untuk mengurutkan array $arr.
    • Jika panjang array kurang dari atau sama dengan satu, maka array dianggap sudah terurut dan langsung dikembalikan.
    • Tentukan titik tengah array dengan floor(count($arr) / 2).
    • Array dibagi menjadi dua bagian: $left dan $right menggunakan array_slice.
  2. Pembagian Rekursif:
    • Fungsi mergeSort dipanggil secara rekursif untuk $left dan $right hingga setiap bagian hanya mengandung satu elemen.
  3. Fungsi merge($left, $right):
    • Fungsi ini digunakan untuk menggabungkan dua bagian array yang sudah terurut menjadi satu array yang terurut.
    • Dua indeks ($i dan $j) digunakan untuk melacak posisi saat ini dalam $left dan $right.
    • Bandingkan elemen dari $left dan $right, dan tambahkan elemen yang lebih kecil ke dalam array hasil $result.
    • Setelah perbandingan utama selesai, tambahkan sisa elemen dari $left dan $right ke dalam $result.
  4. Penggabungan Hasil:
    • Fungsi merge menggabungkan dua array terurut menjadi satu array terurut dan mengembalikannya ke mergeSort.
    • Array yang sudah diurutkan akhirnya dikembalikan oleh mergeSort dan ditampilkan menggunakan print_r.
Baca juga :   Cara Membuat Tabel MySQL dengan CMD Hingga Edit dan Hapus

Contoh Penggunaan

$arr = array(38, 27, 43, 3, 9, 82, 10);
$arr = mergeSort($arr);
print("Array yang sudah diurutkan: ");
print_r($arr);

Output:

Array yang sudah diurutkan: Array ( [0] => 3 [1] => 9 [2] => 10 [3] => 27 [4] => 38 [5] => 43 [6] => 82 )

Kelebihan dan Kekurangan Merge Sort

Algoritma ini memiliki beberapa kelebihan dan kekurangan yang perlu dipertimbangkan dalam penggunaannya. Berikut adalah penjelasan mendetail mengenai kelebihan dan kekurangan yang dimiliki algoritma ini.

Kelebihan Merge Sort

  1. Kompleksitas Waktu yang Konsisten:
    • Memiliki kompleksitas waktu O(n log n) di semua kasus: terbaik, rata-rata, dan terburuk. Hal ini menjadikan Merge Sort efisien dan dapat diandalkan untuk pengurutan data dalam jumlah besar, tidak peduli bagaimana data tersebut diurutkan awalnya.
  2. Stabilitas:
    • Algoritma pengurutan yang stabil. Artinya, jika ada dua elemen dengan nilai yang sama, urutan relatif mereka dalam array yang terurut akan tetap sama seperti dalam array awal. Stabilitas ini penting dalam beberapa aplikasi di mana urutan relatif dari elemen yang sama perlu dipertahankan.
  3. Tidak Bergantung pada Urutan Data Awal:
    • Performansi algoritma ini tidak tergantung pada urutan data awal. Baik data yang diurutkan sepenuhnya, terbalik atau acak, Merge Sort akan tetap bekerja dengan kompleksitas waktu yang sama.
  4. Cocok untuk Pengurutan Eksternal:
    • Merge Sort sangat efektif untuk pengurutan eksternal di mana data yang akan diurutkan tidak bisa dimuat seluruhnya ke dalam memori (misalnya pengurutan file besar yang disimpan di disk). Algoritma ini dapat menggabungkan blok data yang diurutkan secara independen, yang sangat berguna untuk skenario pengurutan eksternal.
  5. Implementasi Sederhana:
    • Konsep dan implementasi cukup sederhana dan mudah dipahami. Ini memudahkan dalam menulis dan memelihara kode yang menggunakan algoritma ini.
Baca juga :   Perkembangan Jaringan Komputer

Kekurangan Merge Sort

  1. Penggunaan Memori:
    • Salah satu kekurangan utama adalah penggunaan memori tambahan sebesar O(n) untuk array sementara selama proses penggabungan. Hal ini bisa menjadi tidak efisien dalam sistem dengan memori terbatas atau ketika mengurutkan data dalam jumlah sangat besar.
  2. Overhead Rekursif:
    • Menggunakan pendekatan rekursif, yang menambah overhead pemanggilan fungsi. Pada data dengan ukuran kecil, overhead ini bisa membuat Merge Sort lebih lambat dibandingkan dengan algoritma pengurutan yang lebih sederhana seperti Insertion Sort.
  3. Kecepatan pada Data Kecil:
    • Pada data yang berukuran kecil, algoritma pengurutan sederhana seperti Insertion Sort atau Bubble Sort bisa lebih cepat daripada Merge Sort. Overhead dari pemanggilan rekursif dan penggabungan bisa membuat Merge Sort tidak secepat algoritma yang lebih sederhana pada dataset yang kecil.
  4. Tidak Efisien untuk Pengurutan di Tempat:
    • Algoritma pengurutan di tempat (in-place sorting). Artinya, ia memerlukan ruang tambahan di luar array asli yang sedang diurutkan. Ini berbeda dengan Quick Sort atau Heap Sort yang dapat bekerja dengan ruang tambahan yang minimal.

Kesimpulan

Pada pembahasan kita di atas dapat kita simpulkan bahwa Algoritma Merge Sort adalah metode pengurutan yang terkenal karena efisiensinya dalam menangani berbagai jenis data dengan kompleksitas waktu yang stabil, yaitu O(n log n) di semua kasus. Algoritma ini bekerja dengan prinsip divide and conquer, di mana array dibagi menjadi bagian-bagian kecil, diurutkan secara rekursif, dan kemudian digabungkan kembali menjadi satu array terurut.

Implementasi Merge Sort mudah dipahami dan sangat berguna untuk pengurutan data dalam jumlah besar atau pengurutan eksternal. Namun, algoritma ini memerlukan memori tambahan untuk array sementara dan memiliki overhead pemanggilan fungsi rekursif, yang bisa membuatnya kurang efisien dibandingkan algoritma pengurutan sederhana pada dataset kecil.

Artikel ini merupakan bagian seri artikel Programming dari KantinIT.com dan jika ada ide topik yang mau kami bahas silahkan komen di bawah ya..