Program C++ tentang Merge Sort

Merge sort is a sorting algorithm in computer science designed to meet the needs of sorting on a data set that does not allow to be stored in computer memory because the amount is too large. This algorithm was invented by John von Neumann in 1945.

Algoritma :

Procedure merge_sort (input : data (larik),n; output : data(larik))

Deklarasi

data                    : integer of array

n                         : integer

Deskripsi

read(data)

int temp[100], tempAwal = awal, tempMid = mid, i = 0

while (tempAwal < mid && tempMid < akhir) do

if(data[tempAwal] < data[tempMid]) then

temp[i] = data[tempAwal]

else

temp[i] = data[tempMid]

endif

endwhile

while(tempAwal < mid)do

temp[i] = data[tempAwal]

endif

while(tempMid < akhir)do

temp[i] = data[tempMid]

endif

for j <= 0 to i do

for k <= awal to akhir do

data[k] = temp[j]

endfor

endfor

if(akhir-awal != 1)

int mid = (awal+akhir)/2

merge(awal, mid)

merge(mid, akhir)

mergeSort(awal, mid, akhir)

endif

read(n)

for i ß 0 to n do

data[i]

merge(0,n)

endfor

Berikut kode programnya :

#include <iostream>

  

int data[100];

void mergeSort(int awal, int mid, int akhir)

{

    cout<<endl;

    int temp[100], tempAwal = awal, tempMid = mid, i = 0;

    while(tempAwal < mid && tempMid < akhir)

    {

        if(data[tempAwal] < data[tempMid])

            temp[i] = data[tempAwal],tempAwal++;

        else

            temp[i] = data[tempMid],tempMid++;

        i++;

    }

    while(tempAwal < mid)  //kalau masih ada yang sisa

        temp[i] = data[tempAwal],tempAwal++,i++;

    while(tempMid < akhir)

        temp[i] = data[tempMid],tempMid++,i++;

    for(int j=0,k=awal;j<i,k<akhir;j++,k++)  //mengembalikan ke array semula, tapi

        cout<<data[k]<<' '<<temp[j]<<endl, data[k] = temp[j]; //sudah urut

}

void merge(int awal, int akhir) //membagi data secara rekursif

{

    if(akhir-awal != 1)

    {

        int mid = (awal+akhir)/2;

        merge(awal, mid);

        merge(mid, akhir);

        mergeSort(awal, mid, akhir);

    }

}

int main()

{

    int n;

    cout<<"Masukan banya data = ";cin>>n;

    cout<<"Masukan data yang akan di susun = ";

    for(int i=0;i<n;i++)

        cin>>data[i];

    merge(0,n);

    for(int i=0;i<n;i++)

        cout<<data[i]<<' ';

    return 0;

}

explanation:

The program above is a merge sort program is one method of sorting. Merge sort is done recursively. Step of the algorithm is a data line is divided into 2 subbarisan then sort recursively and join the results of step 2 of 2 subbarisan are sorted into the sorted sequence.

Ilustration :