Posted in Informatika

Merge Sort

Merge sort berbasiskan pada paradigma “divide and conquer” . Secara sederhana algoritma penyelesaian merge sort yaitu dengan membagi suatu array menjadi dua bagian terus menerus ( rekursi ) hingga tidak dapat dibagi lagi. Kemudian antar  bagian tersebut dibandingkan masing-masing elemennya untuk mengurutkan sekaligus menggabungkannya lagi.

merge sort dibagi menjadi 3 fase yaitu :

1. Divide Step

Jika array yang diberikan hanya mempunyai 1 anggota, langsung di-return bahwa sudah di sort, jika tidak, bagi array A[a . . n]  menjadi 2 sub array A[a…b] dan A[b+1 .. n]  masing masing mengandung setengah dari element A[a..n] yaitu b adalah tengah-tengah dari index a->n

2. Conquer Step

Conquer secara rekursif dengan men-sort dua sub array  A[a..b] dan A[b+1 .. n].

3. Combine Step

Mengkombinasikan kembali elemen menjadi A[a…n] dengan menggabungkan 2 sub array yang telah di sort A[a..b] dan A[b+1 ..n] menjadi sebuah array yang telah di sort.


Analisis Merge Sort

menganalisis merge sort menggunakan master theorem yaitu menggunakan T(n) = AT(n/b) + f(n) …

basis rekursi dari fungsi merge sort ketika n = 1 dan merge sort ketika n>1 maka…

merge sort merekursif 2 array hasil pembagian array awal dan masing-masing mempuyai ukuran (n/2)

maka master theoremnya = 2T(n/2)+f(n)

dengan melihat aturan master theorem maka

T (n) = Θ(n lg n).

SOURCE CODE

berikut source code yang saya buat
#include <stdio.h>
#include <stdlib.h>

void merge(int,int,int);
void mergesort(int ,int);

int *a,*b,*c;

int main()
{
a = (int*)malloc(sizeof(int));
b= (int*)malloc(sizeof(int));
c= (int*)malloc(sizeof(int));
int n = 0;
printf(“masukkan jumlah angka = “);
scanf(“%d”,&n);

for ( int i = 0 ; i< n ;i++)
{
printf(“masukkan angka (maksimal 8 digit)”);
scanf(“%d”,&a[i]);
}

mergesort(0,n);
for ( int i = 0 ; i< n ;i++)
{
printf(“\n %d”,a[i]);
}
system(“pause”);
}

void mergesort(int lo, int hi)
{
if (lo {
int m=(lo+hi)/2;
mergesort(lo, m);
mergesort(m+1, hi);
merge(lo, m, hi);
}
}

void merge(int lo, int m, int hi)
{
int i, j, k;

// copy both halves of a to auxiliary array b
for (i=lo; i b[i]=a[i];

i=lo; j=m+1; k=lo;
// copy back next-greatest element at each time
while (i if (b[i] a[k++]=b[i++];
else
a[k++]=b[j++];

// copy back remaining elements of first half (if any)
while (i a[k++]=b[i++];
}

happy coding ^^V!

Advertisements

Author:

Insan biasa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s