Algoritma MergeSort dalam C dan Java

Informatec Digital » Algoritma » Algoritma MergeSort dalam C dan Java

Pengisihan data adalah tugas asas dalam pengaturcaraan dan analisis algoritma. Terdapat banyak teknik pengisihan yang tersedia, dan salah satu yang paling berkesan ialah algoritma MergeSort. Algoritma ini menggunakan pendekatan "bahagi dan takluk" untuk mengisih senarai elemen secara rekursif.

Dalam artikel ini, kami akan menumpukan pada pelaksanaan algoritma MergeSort dalam bahasa pengaturcaraan C dan Java. Kami akan meneroka langkah demi langkah bagaimana algoritma ini berfungsi dan bagaimana anda boleh menggunakannya dalam projek anda sendiri. Kami juga akan membincangkan kerumitan masa MergeSort dan membandingkan prestasinya dengan algoritma pengisihan yang lain.

Algoritma MergeSort dalam C dan Java

Algoritma MergeSort menggunakan strategi bahagi dan takluk untuk menyusun senarai item. Proses ini dilakukan dalam tiga peringkat utama: bahagi, takluk dan gabung. Mari kita lihat cara melaksanakan algoritma ini dalam bahasa pengaturcaraan C dan Java.

Pelaksanaan MergeSort dalam C

Berikut ialah pelaksanaan 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 pelaksanaan ini, kita mula-mula menentukan fungsi merge yang bertanggungjawab untuk menggabungkan dua subarray tersusun ke dalam tatasusunan utama. Kemudian fungsi mergeSort secara rekursif membahagi tatasusunan kepada subarray yang lebih kecil dan mengisihnya menggunakan fungsi tersebut merge. Akhirnya, dalam fungsi main, kami mencipta tatasusunan ujian, kami panggil mergeSort dan kami menunjukkan susunan yang dipesan pada skrin.

Melaksanakan MergeSort dalam Java

Sekarang, mari lihat cara melaksanakan algoritma MergeSort dalam 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 pelaksanaan MergeSort dalam Java ini, kami menggunakan kaedah statik untuk fungsi tersebut merge y mergeSort. Fungsi merge melaksanakan tugas yang sama seperti dalam pelaksanaan C, dan fungsi mergeSort mengikut logik yang sama iaitu membelah dan menggabungkan subarray. Pada majlis tersebut main, kami mencipta tatasusunan ujian, kami panggil mergeSort dan kami memaparkan tatasusunan yang diisih dalam konsol.

Apakah kerumitan masa algoritma MergeSort?

Kerumitan masa algoritma MergeSort ialah O(n log n), dengan “n” mewakili bilangan elemen dalam tatasusunan yang hendak diisih. Ini bermakna bahawa masa berjalan algoritma meningkat secara berkadar kepada hasil darab "n" dan logaritma asas 2 bagi "n". Kerumitan ini menjadikan MergeSort sebagai salah satu algoritma pengisihan paling cekap yang tersedia.

Perbandingan MergeSort dengan algoritma pengisihan lain

MergeSort menonjol kerana kecekapannya dalam menyusun data. Berbanding dengan algoritma popular lain seperti Bubble Sort atau Selection Sort, MergeSort mempunyai kerumitan masa yang jauh lebih baik. Walaupun Isih Buih dan Isih Pemilihan mempunyai kerumitan masa O(n^2), MergeSort mempunyai kerumitan masa O(n log n). Ini bermakna MergeSort mampu mengendalikan volum data yang besar dengan lebih cekap dan lebih pantas daripada algoritma yang kurang cekap ini.

Soalan yang kerap ditanya

1: Mengapa menggunakan MergeSort dan bukannya algoritma pengisihan lain?

MergeSort diutamakan berbanding algoritma pengisihan lain kerana kecekapan dan prestasinya. Dengan kerumitan masa O(n log n), MergeSort dapat mengisih set data yang besar dengan lebih pantas dan lebih cekap daripada algoritma dengan kerumitan kuadratik, seperti Bubble Sort atau Selection Sort. Selain itu, MergeSort ialah algoritma yang stabil, bermakna ia mengekalkan susunan relatif elemen dengan nilai yang sama, yang boleh menjadi penting dalam konteks tertentu.

2: Bilakah saya harus menggunakan MergeSort dalam projek saya?

Anda mungkin mempertimbangkan untuk menggunakan MergeSort apabila anda perlu mengisih set data yang besar dengan cekap. Jika anda mempunyai senarai item yang tidak tersusun dan ingin mendapatkan senarai yang diisih dalam masa yang sesingkat mungkin, MergeSort ialah pilihan yang bagus. Walau bagaimanapun, ambil perhatian bahawa MergeSort mungkin memerlukan lebih banyak ruang memori berbanding dengan algoritma pengisihan lain kerana ia mencipta subarray tambahan semasa pelaksanaannya.

3: Adakah terdapat sebarang kelemahan untuk menggunakan MergeSort?

Kemungkinan kelemahan MergeSort ialah penggunaan memori tambahannya. Semasa pelaksanaan algoritma, subarray tambahan dicipta untuk memisahkan dan menggabungkan data, yang boleh meningkatkan keperluan memori, terutamanya apabila bekerja dengan set data yang sangat besar. Walau bagaimanapun, dalam kebanyakan kes, kelemahan ini adalah tidak penting berbanding dengan kecekapan algoritma.

4: Bolehkah MergeSort mengendalikan elemen pendua dalam tatasusunan?

Ya, MergeSort boleh mengendalikan elemen pendua dalam tatasusunan. Algoritma adalah stabil, bermakna ia mengekalkan susunan relatif elemen dengan nilai yang sama. Ini penting apabila anda ingin mengekalkan susunan asal item sekiranya terdapat pendua. MergeSort memastikan elemen pendua muncul dalam susunan relatif yang sama dalam kedua-dua tatasusunan input dan tatasusunan yang diisih.

5: Adakah terdapat sebarang variasi atau penambahbaikan pada algoritma MergeSort?

Ya, terdapat beberapa varian dan penambahbaikan pada algoritma MergeSort. Beberapa varian ini termasuk MergeSort berulang, MergeSort dengan pengoptimuman penggabungan subarray dan MergeSort hibrid yang menggabungkan MergeSort dengan algoritma pengisihan lain, seperti Insertion Sort, untuk mencapai prestasi yang lebih baik dalam kes tertentu. Varian ini berusaha untuk meningkatkan prestasi dan kecekapan algoritma MergeSort dalam situasi tertentu.

6: Di manakah saya boleh mengetahui lebih lanjut tentang MergeSort dan algoritma pengisihan lain?

Jika anda ingin mengetahui lebih lanjut tentang MergeSort dan algoritma pengisihan lain, anda boleh menyemak sumber berikut:

• Wikipedia – Isih Gabung
• GeeksforGeeks – Isih Gabung

Kesimpulan

Dalam artikel ini, kami telah meneroka algoritma MergeSort dalam bahasa pengaturcaraan C dan Java. Kami telah mempelajari cara melaksanakan algoritma pengisihan data yang cekap ini dan membincangkan kerumitan masanya. Melalui contoh dan penjelasan terperinci, anda kini mempunyai pemahaman yang kukuh tentang cara MergeSort berfungsi dalam C dan Java, dan cara anda boleh menggunakannya dalam projek anda sendiri.

MergeSort ialah alat yang berkuasa untuk mengisih set data yang besar dan kerumitan masa O(n log n) menjadikannya pilihan yang menarik berbanding dengan algoritma pengisihan lain yang kurang cekap. Jika anda perlu mengisih data dengan cekap dan cepat, pertimbangkan untuk menggunakan MergeSort sebagai algoritma pilihan anda.

Teroka dan bereksperimen dengan MergeSort dalam projek anda untuk meraih faedahnya dan menikmati prestasi pengisihan data yang optimum!