Merge Sort di C++: Pengertian, Cara Kerja, dan Contoh Program

Algoritma pengurutan atau sorting algorithm memiliki peran krusial dalam dunia pemrograman. Salah satu algoritma pengurutan yang efisien dan banyak digunakan adalah Merge Sort, terutama dalam bahasa pemrograman seperti C++. Dalam artikel ini, kita akan membahas secara lengkap tentang Merge Sort di C++, mulai dari pengertiannya, cara kerjanya, hingga contoh programnya.

Merge Sort di C++

Pengertian Merge Sort

Merge Sort adalah sebuah algoritma pengurutan yang dibangun dengan menggunakan pendekatan divide and conquer. Algoritma ini pertama kali diperkenalkan oleh John von Neumann pada tahun 1945. Keunggulan dari Merge Sort di C++ adalah efisiensinya, terutama dalam menangani array atau list yang besar.

Cara Kerja Merge Sort

Merge Sort adalah sebuah algoritma yang menggunakan pendekatan divide and conquer. Ini berarti bahwa algoritma ini memecah masalah yang kompleks menjadi sub-masalah yang lebih sederhana, menyelesaikan sub-masalah tersebut, dan menggabungkannya kembali untuk mendapatkan solusi dari masalah awal.

Langkah-langkah Cara Kerja

Cara kerja Merge Sort di C++ dapat dijabarkan menjadi beberapa langkah berikut:

1. Pembagian (Divide): Algoritma ini memulai dengan membagi array atau list yang akan diurutkan menjadi dua bagian yang hampir sama besar. Jika jumlah elemen dalam array adalah ganjil, maka salah satu dari dua bagian tersebut akan memiliki satu elemen lebih banyak daripada bagian yang lain.
   Misalkan Anda memiliki array [38,27,43,3,9,82,10]. Algoritma ini akan membagi array ini menjadi dua bagian: [38,27,43] dan [3,9,82,10].
   
   
2. Rekursi: Langkah pembagian ini diulang secara rekursif untuk setiap sub-array yang dihasilkan, hingga setiap sub-array hanya berisi satu elemen. Satu elemen dianggap sudah "terurut", sehingga kita bisa mulai menggabungkannya kembali.
   Misalnya, array [38,27,43] akan terus dibagi menjadi [38], [27], dan [43].
   
   
3. Penggabungan (Merge): Setelah setiap sub-array hanya berisi satu elemen, langkah selanjutnya adalah menggabungkannya kembali dalam urutan yang sudah terurut. Ini dilakukan dengan membandingkan elemen pertama dari setiap sub-array dan memilih elemen yang lebih kecil untuk ditempatkan di array hasil.
   Misalnya, [38] dan [27] akan digabungkan menjadi [27,38].
   
   
4. Penggabungan Kembali (Conquer): Penggabungan ini terus diulang, membangun kembali sub-array yang lebih besar dan sudah terurut, hingga seluruh array sudah kembali utuh dan terurut.
   Akhirnya, [27,38,43] akan digabungkan kembali dengan [3,9,10,82] untuk membentuk array [3,9,10,27,38,43,82] yang sudah terurut.

Kompleksitas Waktu

Salah satu keuntungan dari Merge Sort di C++ adalah efisiensinya dalam hal waktu. Algoritma ini memiliki kompleksitas waktu O(nlogn) untuk kasus terbaik, rata-rata, dan terburuk.

Baca Juga: Tutorial Lengkap Belajar Bahasa Pemrograman C++

Contoh Program Merge Sort di C++

Berikut adalah contoh program yang mengimplementasikan algoritma Merge Sort di C++:

#include <iostream>

#include <vector>

using namespace std;

void merge(vector<int> &arr, int l, int m, int r) {

    int i, j, k;

    int n1 = m - l + 1;

    int n2 = r - m;

    vector<int> L(n1), R(n2);

    for (i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[m + 1 + j];

    i = 0;

    j = 0;

    k = l;

    while (i < n1 && j < n2) {

        if (L[i] <= R[j]) {

            arr[k] = L[i];

            i++;

        } else {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

    while (i < n1) {

        arr[k] = L[i];

        i++;

        k++;

    }

    while (j < n2) {

        arr[k] = R[j];

        j++;

        k++;

    }

}

void mergeSort(vector<int> &arr, int l, int r) {

    if (l >= r) return;

    int m = l + (r - l) / 2;

    mergeSort(arr, l, m);

    mergeSort(arr, m + 1, r);

    merge(arr, l, m, r);

}

int main() {

    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

    int arr_size = arr.size();

    mergeSort(arr, 0, arr_size - 1);

    for (auto &num : arr) {

        cout << num << " ";

    }

    return 0;

}

Output

3 9 10 27 38 43 82

Penjelasan Program

Mengimpor Pustaka: Kode di atas menggunakan pustaka standar <iostream> untuk operasi input/output dan <vector> untuk menggunakan struktur data vektor. Sedangkan using namespace std agar kita tidak perlu menulis std:: sebelum setiap fungsi bawaan C++.

#include <iostream>

#include <vector>

using namespace std;

Fungsi merge(): Fungsi ini bertanggung jawab untuk menggabungkan dua bagian dari array yang sudah diurutkan. Ini merupakan inti dari algoritma Merge Sort di C++. Namun, dalam contoh ini, fungsi ini sengaja dikosongkan untuk fokus pada struktur kode keseluruhan.

void merge(vector<int> &arr, int l, int m, int r) {

    // Kode untuk proses merging

}

Fungsi mergeSort(): Fungsi ini mengimplementasikan logika divide and conquer. Pertama, ia membagi array menjadi dua. Kemudian, fungsi ini memanggil dirinya sendiri secara rekursif untuk setiap bagian hingga array tersebut benar-benar terpecah menjadi elemen-elemen tunggal. Selanjutnya, ia memanggil fungsi merge() untuk mulai menggabungkan dan mengurutkan elemen-elemen tersebut.

void mergeSort(vector<int> &arr, int l, int r) {

    if (l >= r) return;

    int m = l + (r - l) / 2;

    mergeSort(arr, l, m);

    mergeSort(arr, m + 1, r);

    merge(arr, l, m, r);

}

Fungsi main(): Fungsi ini adalah titik awal dari program. Di sini, kita mendefinisikan array yang akan diurutkan dan memanggil fungsi mergeSort().

int main() {

    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

    int arr_size = arr.size();

    mergeSort(arr, 0, arr_size - 1);

    for (auto &num : arr) {

        cout << num << " ";

    }

    return 0;

}

Dengan memahami setiap komponen kode di atas, Anda akan mendapatkan gambaran yang lebih baik tentang bagaimana algoritma Merge Sort di C++ bekerja dari awal hingga akhir.

Kelebihan dan Kekurangan Merge Sort

Kelebihan Merge Sort:

• Efisiensi Waktu: Merge Sort memiliki kompleksitas waktu O(nlogn) dalam semua kasus (terbaik, rata-rata, dan terburuk), menjadikannya salah satu algoritma sorting yang paling efisien.
• Stabilitas: Merge Sort adalah algoritma yang stabil. Ini berarti bahwa elemen dengan nilai yang sama akan tetap berada pada urutan relatif mereka sesuai dengan array asli, bahkan setelah diurutkan.
• Penggunaan Memori Konstan: Meskipun memerlukan ruang memori tambahan, penggunaan memori adalah konstan dan tidak bergantung pada kasus khusus dari data masukan.
• Bekerja Baik pada Data Besar: Merge Sort di C++ bekerja sangat efisien bahkan pada data set yang besar dan terdistribusi dalam berbagai medium.

Kekurangan Merge Sort:

• Penggunaan Memori Tambahan: Salah satu kekurangan besar dari Merge Sort adalah kebutuhannya akan memori tambahan. Ini bisa menjadi masalah jika memori yang tersedia sangat terbatas.
• Kompleksitas Implementasi: Dibandingkan dengan algoritma seperti Bubble Sort atau Insertion Sort, Merge Sort cenderung lebih sulit untuk diimplementasikan dan memahami logikanya.
• Kecepatan pada Data Kecil: Untuk data set yang relatif kecil, algoritma lain seperti Quick Sort dapat lebih cepat dalam beberapa kasus.
• Ketergantungan pada Fungsi Merge: Efisiensi algoritma ini sangat bergantung pada implementasi fungsi merge(). Kesalahan kecil dalam fungsi ini bisa berdampak besar pada efisiensi keseluruhan.

Merge Sort di C++ adalah salah satu algoritma pengurutan yang efisien dan sering digunakan. Dengan memahami pengertian dan cara kerjanya, Anda bisa mengimplementasikannya dalam berbagai kasus pengurutan data. Algoritma ini memiliki keunggulan dalam efisiensi waktu dengan kompleksitas O(nlogn).

Daftar Pustaka

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• von Neumann, J. (1945). First Draft of a Report on the EDVAC. IEEE Annals of the History of Computing.

Sekian artikel mengenai Merge Sort di C++. Semoga artikel ini dapat bermanfaat baik untuk menambah ilmu, mengerjakan tugas, maupun untuk sekedar menambah wawasan, Terimakasih atas kunjungannya.

MateriDosen.Com

Berbagi: