Struktur Data : Merge Sort dalam Bahasa C

📋 Daftar Isi

Algoritma ini dirancang untuk memenuhi kebutuhan pengurutan data yang tidak memungkinkan untuk ditampung dalam memori komputer karena ukurannya yang terlalu besar.

Menggunakan cara divide and conquer yaitu dengan memecah, kemudian menyelesaikan setiap bagian, kemudian menggabungkannya kembali.

Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data
Kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.
Setelah itu digabungkan kembali dengan membandingkan data pada blok i apakah data lebih besar daripada data di blok setelahnya i+1, jika ya maka data blok setelahnya dipindah sebagai data pertama di blok yang baru (digabungkan). Demikian seterusnya sampai menjadi satu blok utuh seperti awalnya.

Ilustrasi Merge Sort

Contoh Program

void mergeDesc(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    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 mergeAsc(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    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 mergeSortAsc(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;
        mergeSortAsc(arr, l, m);
        mergeSortAsc(arr, m + 1, r);
        mergeAsc(arr, l, m, r);
    }
}

void mergeSortDesc(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;
        mergeSortDesc(arr, l, m);
        mergeSortDesc(arr, m + 1, r);
        mergeDesc(arr, l, m, r);
    }
}