Pada postingan
kali ini saya akan menjelaskan salah satu pengurutan dalam suatu algoritma
yaitu Merge Sort . Jika kalian belum tahu apa itu Merge Sort disini saya akan
menjelaskannya , semoga apa yang didapat dari postingan kali ini bermanfaat
untuk kalian semua para pembaca dan mohon maaf jika ada kesalahan dalam kata –
kata karena saya sendiri juga sama – sama belajar hehe...
Merge Sort
merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk
memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan
untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar.
Algoritma ini ditemukan oleh John Von Neumann pada tahun 1945.
Algoritma
pengurutan merge dilakukan dengan cara divide and conquer yaitu memecah
kemudian menyelesaikan setiap bagian , kemudian menggabungkannya kembali.
Pertama data dipecah menjadi 2 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 pada blok yang sama apakah data pertama lebih
besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai
data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data
ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh
seperti awalnya.
Contoh Soal :
Urutkan berikut menggunakan Merge Sort :
Diketahui nilai urutan sebagai berikut : 56 29 35 42 15
41 75 21
Niai akhir yang sudah diurutkan : 15 21 29 35 41 42 56
75
Untuk lebih jelasnya
perhatikan langkah – langkah dibawah ini :
Langkah –
langkahnya
- Nilai pada barisan pertama tetap masih teracak
- Bagi menjadi 2 bagian dengan cara N/2 , perhatikan gambar pada baris kedua
- Pada baris ketiga bagi lagi menjadi 2 bagian , hingga menjadi baris ke 4
- Pada baris keempat urutkan nilai terkecil hingga terbesar
- Pada baris kelima dan keenam gabungkan nilai yang sudah terurut
- Hingga menjadi hasil akhir 15 21 29 35 41 42 56 75
Cukup mudah
bukan ?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
mergesort(low,
high)
{
int
mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,high,mid);
}
)
Merge( low,
mid, high)
{
int
h,i,j,k,b[50];
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(A[h]<A[j])
{
b[i]=A[h];
h++;
}else{
b[i]=A[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=A[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=A[k];
i++;
}
}
for(k=low;k<=high;k++)
{
A[k]=b[k];
}
}
|
Cukup jelas
dan mudah bukan ? semoga materi ini bermanfaat dan menambah wawasan anda semua
. Amiin
Referensi :
https://rusdyana.wordpress.com/2009/12/03/algoritma-mergesort/
1 komentar so far
EmoticonEmoticon