Merge Sort Step By Step
Contoh : Kita memiliki array seperti ini
90 12 34 10 55 44 88 23 77
Langkah pertama adalah membagi menjadi 9 bagian di setiap masing-masing elemen.
90 12 34 10 55 44 88 23 77
1 2 3 4 5 6 7 8 9
Caranya membandingkan elemen pertama pada bagian 1 dan bagian 2 dan seterusnya (bagian n dan n + 1). Cari yang lebih kecil, lalu masukan ke bagian yang baru yang berukuran bagian sekarang x 2 yaitu 1 x 2 = 2.
Jadi dibandingkan 90 dengan 12, mana yang lebih kecil ? Kan 12. Maka 12 dimasukan ke bagian yang baru.
90 34 10 55 44 88 23 77
1 2 3 4 5 6 7 8 9
12
1
Karena pada bagian 1 dan 2 hanya tersisa 1 bagian yaitu bagian 1 dengan hanya 1 elemen. Maka langsung masukan ke bagian yang baru.
34 10 55 44 88 23 77
1 2 3 4 5 6 7 8 9
12 90
1
Lalu kita bandingkan lagi hingga semua habis. Jadi kita bandingkan 34 dengan 10, mana yang lebih kecil ? 10 kan. Maka masukan 10 ke bagian yang baru.
34 55 44 88 23 77
1 2 3 4 5 6 7 8 9
12 90 10
1 2
Lalu karena tinggal 1 elemen yaitu 34, maka masukan 34 ke bagian baru 2.
55 44 88 23 77
1 2 3 4 5 6 7 8 9
12 90 10 34
1 2
Lalu cek 55 dengan 44, yang lebih kecil adalah 44. Setelah 44, hanya tinggal 55, maka sehabis memasukan 44 langsung memasukan 55.
88 23 77
1 2 3 4 5 6 7 8 9
12 90 10 34 44 55
1 2 3
Lalu cek 88 dengan 23, yang lebih kecil adalah 23. Setelah 23, hanya tinggal 88, maka sehabis memasukan 23 langsung memasukan 88
77
1 2 3 4 5 6 7 8 9
12 90 10 34 44 55 23 88
1 2 3 4
Setelah itu karena tinggal 1 bagian yaitu bagian 9 dan tinggal 1 elemen, maka langsung masukan ke bagian baru tapi terpaksa dengan 1 elemen saja.
1 2 3 4 5 6 7 8 9
12 90 10 34 44 55 23 88 77
1 2 3 4 5
Mari kita hapus 9 bagian tadi.
12 90 10 34 44 55 23 88 77
1 2 3 4 5
Sekarang kita lakukan sama persis seperti tadi, bandingkan elemen pertama di kedua bagian, lalu masukan elemen yang terkecil ke bagian yang baru. Jadi, sekarang kita bandingkan 12 dan 10, maka masukan 10 ke bagian baru. Oh iya, jangan lupa bagian yang baru memiliki ukuran 2x bagian yang lama. jadi bagian baru memiliki ukuran 2x2 = 4 elemen.
12 90 34 44 55 23 88 77
1 2 3 4 5
10
1
Bandingkan 34 dengan 12. Lebih kecil 12, maka masukan 12.
90 34 44 55 23 88 77
1 2 3 4 5
10 12
1
Bandingkan 94 dengan 34, lebih kecil 34 , maka masukan 34.
90 44 55 23 88 77
1 2 3 4 5
10 12 34
1
Karena bagian 1 dan bagian 2 tinggal 1 elemen yaitu 90, maka langsung masukan 90.
44 55 23 88 77
1 2 3 4 5
10 12 34 90
1
Sekarang bagian 1 (baru) sudah selesai, kini saatnya mengisi bagian 2(baru) . Kita cek 44 dengan 23, lebih kecil 23. maka masukan 23
44 55 88 77
1 2 3 4 5
10 12 34 90 23
1 2
Cek, 88 dengan 44. Lebih kecil 44
55 88 77
1 2 3 4 5
10 12 34 90 23 44
1 2
Cek 55 dengan 88, lebih kecil 55.
88 77
1 2 3 4 5
10 12 34 90 23 44 55
1 2
Karena 88 adalah elemen terakir, maka langsung masukan 88.
77
1 2 3 4 5
10 12 34 90 23 44 55 88
1 2
Karena 77 juga elemen terakir maka masukan 77 langsung ke elemen 3(baru).
1 2 3 4 5
10 12 34 90 23 44 55 88 77
1 2 3
Lalu hapus 5 bagian sebelumnya.
10 12 34 90 23 44 55 88 77
1 2 3
Nah sekarang caranya sama, Ingat bagian baru akan berukuran bagian pertama dikali 2 yaitu 4x2 = 8. Bandingkan 10 dengan 23, lebih kecil 10.
12 34 90 23 44 55 88 77
1 2 3
10
1
Bandingkan 12 dengan 23. lebih kecil 12, masukan 12.
34 90 23 44 55 88 77
1 2 3
10 12
1
Bandingkan 34 dengan 23, lebih kecil 23. masukan 23
34 90 44 55 88 77
1 2 3
10 12 23
1
Bandingkan 44 dengan 34, lebih kecil 34. masukan 34
90 44 55 88 77
1 2 3
10 12 23 34
1
Bandingkan 44 dengan 90, lebih kecil 44, maka masukan 44.
90 55 88 77
1 2 3
10 12 23 34 44
1
Bandingkan 55 dengan 90, lebih kecil 55, maka masukan 55.
90 88 77
1 2 3
10 12 23 34 44 55
1
Bandingkan 88 dengan 90, lebih kecil 88, maka masukan 88.
90 77
1 2 3
10 12 23 34 44 55 88
1
Karena tinggal 1 elemen pada bagian 1 yaitu 90, maka langsung masukan 90.
77
1 2 3
10 12 23 34 44 55 88 90
1
Karena tinggal 1 elemen pada bagian 3, maka masukan elemen tersebut ke bagian 2(baru). Mengapa tidak di bagian 1(baru) ? Karena seperti yang sudah saya katakan diatas, ukuran bagian itu adalah 4x2 = 8.
1 2 3
10 12 23 34 44 55 88 90 77
1 2
Hapus 3 bagian tersebut.
10 12 23 34 44 55 88 90 77
1 2
Lalu caranya sama seperti tadi bandingkan elemen pertama pada bagian 1 dan 2, yang lebih kecil, masukan duluan. Jadi, cek 10 dengan 77, lebih kecil 10, maka masukan 10.
12 23 34 44 55 88 90 77
1 2
10
1
cek 12 dengan 77, lebih kecil 12, maka masukan 12.
23 34 44 55 88 90 77
1 2
10 12
1
Cek 23 dengan 77, lebih kecil 23. masukan 23
34 44 55 88 90 77
1 2
10 12 23
1
Cek 34 dengan 77, lebih kecil 34. masukan 34
44 55 88 90 77
1 2
10 12 23 34
1
Cek 44 dengan 77, lebih kecil 44, masukan 44.
55 88 90 77
1 2
10 12 23 34 44
1
Cek 55 dengan 77, lebih kecil 55, masukan 55.
88 90 77
1 2
10 12 23 34 44 55
1
Cek 88 dengan 77, lebih kecil 77, masukan 77.
88 90
1 2
10 12 23 34 44 55 77
1
Karena pada bagian 2 sudah kosong, jadi 88 mau dicocokin dengan apa. jadi langsung masukin langsung aja 88 dan 90 secara urut.
1 2
10 12 23 34 44 55 77 88 90
1
hapus 2 bagian tersebut.
10 12 23 34 44 55 77 88 90
1
selesai ! SORTED !
10 12 23 34 44 55 77 88 90
Masih belum mengerti ? Yuk tonton video ini !
0 komentar :
Post a Comment