Algoritma MergeSort dalam C dan Java

Informatec Digital » Algoritma » Algoritma MergeSort dalam C dan Java

Penyortiran data merupakan tugas mendasar dalam pemrograman dan analisis algoritma. Ada banyak teknik penyortiran yang tersedia, dan salah satu yang paling efisien adalah algoritma MergeSort. Algoritma ini menggunakan pendekatan "bagi dan taklukkan" untuk mengurutkan daftar elemen secara rekursif.

Pada artikel ini, kita akan fokus pada implementasi algoritma MergeSort dalam bahasa pemrograman C dan Java. Kita akan mengeksplorasi langkah demi langkah bagaimana algoritma ini bekerja dan bagaimana Anda dapat menggunakannya dalam proyek Anda sendiri. Kita juga akan membahas kompleksitas waktu MergeSort dan membandingkan kinerjanya dengan algoritma pengurutan lainnya.

Algoritma MergeSort dalam C dan Java

Algoritma MergeSort menggunakan strategi bagi-dan-taklukkan untuk mengurutkan daftar item. Proses ini dilakukan dalam tiga tahap utama: bagi, taklukkan, dan gabungkan. Mari kita lihat bagaimana mengimplementasikan algoritma ini dalam bahasa pemrograman C dan Java.

Implementasi MergeSort dalam C

Berikut adalah implementasi algoritma MergeSort dalam C:

#include <stdio.h>

void merge(int arr[], int left[], int right[], int left_size, int right_size) {
    int i = 0, j = 0, k = 0;
    
    while (i < left_size && j < right_size) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    
    while (i < left_size) {
        arr[k] = left[i];
        i++;
        k++;
    }
    
    while (j < right_size) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int size) {
    if (size < 2) {
        return;
    }
    
    int mid = size / 2;
    int left[mid];
    int right[size - mid];
    
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    
    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }
    
    mergeSort(left, mid);
    mergeSort(right, size - mid);
    merge(arr, left, right, mid, size - mid);
}

int main() {
    int arr[] = {9, 5, 2, 7, 1, 8, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    mergeSort(arr, size);
    
    printf("Sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

Dalam implementasi ini, pertama-tama kita mendefinisikan sebuah fungsi merge yang bertanggung jawab untuk menggabungkan dua subarray yang berurutan menjadi array utama. Kemudian fungsinya mergeSort membagi array secara rekursif menjadi subarray yang lebih kecil dan mengurutkannya menggunakan fungsi merge. Terakhir, dalam fungsi main, kita membuat array pengujian, kita menyebutnya mergeSort dan kami menunjukkan susunan yang teratur pada layar.

Menerapkan MergeSort di Java

Sekarang, mari kita lihat cara mengimplementasikan algoritma MergeSort di Java:

public class MergeSort {
    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length) {
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    public static void mergeSort(int[] arr) {
        if (arr.length < 2) {
            return;
        }

        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 8, 3};

        mergeSort(arr);

        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Dalam implementasi MergeSort di Java ini, kami menggunakan metode statis untuk fungsi tersebut merge y mergeSort. Fungsi merge melakukan tugas yang sama seperti pada implementasi C, dan fungsinya mergeSort mengikuti logika yang sama dalam membagi dan menggabungkan subarray. Pada acara tersebut main, kita membuat array pengujian, kita menyebutnya mergeSort dan kami menampilkan array yang telah diurutkan dalam konsol.

Berapa kompleksitas waktu dari algoritma MergeSort?

Kompleksitas waktu algoritma MergeSort adalah O(n log n), di mana “n” mewakili jumlah elemen dalam array yang akan diurutkan. Ini berarti waktu berjalan algoritma meningkat secara proporsional terhadap hasil kali "n" dan logaritma basis 2 dari "n". Kompleksitas ini menjadikan MergeSort salah satu algoritma pengurutan paling efisien yang ada.

Perbandingan MergeSort dengan algoritma pengurutan lainnya

MergeSort menonjol karena efisiensinya dalam menyortir data. Dibandingkan dengan algoritma populer lainnya seperti Bubble Sort atau Selection Sort, MergeSort memiliki kompleksitas waktu yang jauh lebih baik. Sementara Bubble Sort dan Selection Sort memiliki kompleksitas waktu O(n^2), MergeSort memiliki kompleksitas waktu O(n log n). Artinya MergeSort mampu menangani data bervolume besar secara lebih efisien dan cepat daripada algoritma yang kurang efisien tersebut.

Pertanyaan yang sering diajukan

1: Mengapa menggunakan MergeSort ketimbang algoritma pengurutan lainnya?

MergeSort lebih disukai daripada algoritma pengurutan lain karena efisiensinya dan kinerjanya. Dengan kompleksitas waktu O(n log n), MergeSort mampu mengurutkan kumpulan data besar dengan lebih cepat dan lebih efisien daripada algoritma dengan kompleksitas kuadrat, seperti Bubble Sort atau Selection Sort. Selain itu, MergeSort adalah algoritma yang stabil, artinya ia mempertahankan urutan relatif elemen dengan nilai yang sama, yang dapat menjadi penting dalam konteks tertentu.

2: Kapan saya harus menggunakan MergeSort dalam proyek saya?

Anda dapat mempertimbangkan menggunakan MergeSort saat Anda perlu mengurutkan kumpulan data besar secara efisien. Jika Anda memiliki daftar item yang tidak berurutan dan ingin mendapatkan daftar yang diurutkan dalam waktu sesingkat mungkin, MergeSort merupakan pilihan yang bagus. Namun, perlu diperhatikan bahwa MergeSort mungkin memerlukan lebih banyak ruang memori dibandingkan dengan algoritma pengurutan lain karena menciptakan subarray tambahan selama eksekusinya.

3: Apakah ada kerugian menggunakan MergeSort?

Salah satu kemungkinan kerugian dari MergeSort adalah penggunaan memori tambahannya. Selama eksekusi algoritma, subarray tambahan dibuat untuk membagi dan menggabungkan data, yang dapat meningkatkan kebutuhan memori, terutama saat bekerja dengan set data yang sangat besar. Akan tetapi, pada kebanyakan kasus, kerugian ini tidak signifikan jika dibandingkan dengan efisiensi algoritma.

4: Bisakah MergeSort menangani elemen duplikat dalam array?

Ya, MergeSort dapat menangani elemen duplikat dalam array. Algoritmanya stabil, artinya mempertahankan urutan relatif elemen dengan nilai yang sama. Hal ini penting ketika Anda ingin mempertahankan susunan item asli apabila ada duplikat. MergeSort memastikan bahwa elemen duplikat muncul dalam urutan relatif yang sama di array input dan array yang diurutkan.

5: Apakah ada varian atau peningkatan pada algoritma MergeSort?

Ya, ada beberapa varian dan penyempurnaan pada algoritma MergeSort. Beberapa varian ini termasuk MergeSort iteratif, MergeSort dengan pengoptimalan penggabungan subarray, dan MergeSort hibrid yang menggabungkan MergeSort dengan algoritma pengurutan lain, seperti Insertion Sort, untuk mencapai kinerja yang lebih baik dalam kasus tertentu. Varian ini berupaya meningkatkan kinerja dan efisiensi algoritma MergeSort dalam situasi tertentu.

6: Di mana saya dapat mempelajari lebih lanjut tentang MergeSort dan algoritma pengurutan lainnya?

Jika Anda ingin mempelajari lebih lanjut tentang MergeSort dan algoritma pengurutan lainnya, Anda dapat memeriksa sumber daya berikut:

• Wikipedia – Gabungkan Urutkan
• GeeksforGeeks – Gabungkan Urutkan

Kesimpulan

Dalam artikel ini, kami telah menjelajahi algoritma MergeSort dalam bahasa pemrograman C dan Java. Kita telah mempelajari cara mengimplementasikan algoritma penyortiran data yang efisien ini dan membahas kompleksitas waktunya. Melalui contoh dan penjelasan terperinci, Anda sekarang memiliki pemahaman mendalam tentang cara kerja MergeSort di C dan Java, dan bagaimana Anda dapat menerapkannya dalam proyek Anda sendiri.

MergeSort adalah alat yang hebat untuk menyortir set data besar dan kompleksitas waktunya sebesar O(n log n) menjadikannya pilihan yang menarik dibandingkan dengan algoritma pengurutan lain yang kurang efisien. Jika Anda perlu mengurutkan data secara efisien dan cepat, pertimbangkan untuk menggunakan MergeSort sebagai algoritma pilihan Anda.

Jelajahi dan bereksperimen dengan MergeSort dalam proyek Anda untuk mendapatkan manfaatnya dan menikmati kinerja penyortiran data yang optimal!