MergeSort


30/12/2019 06:35:53 147 Web

#include<iostream>

using namespace std;

int merges(int arr[], int f, int m, int l)
{
    int i, j, k;
    int n1 = m - f+1;
    int n2 = l - m;


    int L[n1], R[n2];


    for (i = 0; i < n1; i++)
        L[i] = arr[f + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    i=0;
    j=0;
    k = f;
    while(i < n1 && j < n2) {
        if(L[i] < R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Sisa sebelah kiri
    while(i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Sisa sebelah kanan
    while(j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

};


void mergeSort(int arr[], int f, int l)
{
    if(f < l) {

        int mid = (l+f)/2;
        mergeSort(arr, f, mid);
        mergeSort(arr, mid+1, l);

        merges(arr, f, mid, l);
    }
};



int main()
{
    int i, j, tmp, n =8;

    int arr[9] = {6, 4, 3, 9, 7, 11, 7, 2, 8};

    cout << "+------------------+\n";
    cout << "|     Data Awal    |\n";
    cout << "+------------------+\n";

    for(i=0; i<= n; i++) {
        cout << arr[i] <<"\n";
    }

    cout << "+------------------+\n";
    cout << "|    Merge Sort   |\n";
    cout << "+------------------+\n";


    mergeSort(arr, 0, 8);

    cout << "+------------------+\n";
    cout << "|    Data Akhir    |\n";
    cout << "+------------------+\n";

    for(i = 0; i <= n; i++) {
        cout << arr[i] <<"\n";
    }
}