Skip to main content
Pelajar Koding

follow us

Memahami Merge Sort Step By Step


Pengurutan yaitu hal yang tentu sangat penting. Merge sort yaitu salah satu algoritma yang mempunyai worst case O(n log n). Tentu sangat jago dong. Quicksort saja mempunyai worst case n pangkat 2 atau n kuadrat. Nah, bahwasanya bagaimana cara kerja merge sort ini ? Yuk kita pelajari bersama.

Merge Sort Step By Step

Contoh : Kita mempunyai array ibarat ini
90 12 34 10 55 44 88 23 77

Langkah pertama yaitu membagi menjadi 9 bab 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 bab 1 dan bab 2 dan seterusnya (bagian n dan n + 1). Cari yang lebih kecil, kemudian masukan ke bab yang gres yang berukuran bab kini x 2 yaitu 1 x 2 = 2. 
Kaprikornus dibandingkan 90 dengan 12, mana yang lebih kecil ? Kan 12.  Maka 12 dimasukan ke bab yang baru.
  
90                34     10         55     44         88     23       77
1        2         3       4           5       6           7       8         9

12
 1

Karena pada bab 1 dan 2 hanya tersisa 1 bab yaitu bab 1 dengan hanya 1 elemen. Maka pribadi masukan ke bab 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 sampai semua habis. Kaprikornus kita bandingkan 34 dengan 10, mana yang lebih kecil ? 10 kan. Maka masukan 10 ke bab yang baru.

                    34                  55     44         88     23       77
1        2         3       4           5       6           7       8         9

12   90       10
     1            2

Lalu alasannya tinggal 1 elemen yaitu 34, maka masukan 34 ke bab gres 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 yaitu 44. Setelah 44, hanya tinggal 55, maka sesudah memasukan 44 pribadi 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 yaitu 23. Setelah 23, hanya tinggal 88, maka sesudah memasukan 23 pribadi 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 alasannya tinggal 1 bab yaitu bab 9 dan tinggal 1 elemen, maka pribadi masukan ke bab gres 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 bab tadi.

12   90       10  34     44  55      23  88      77
     1               2              3             4           5

Sekarang kita lakukan sama persis ibarat tadi, bandingkan elemen pertama di kedua bagian, kemudian masukan elemen yang terkecil ke bab yang baru. Jadi, kini kita bandingkan 12 dan 10, maka masukan 10 ke bab baru. Oh iya, jangan lupa bab yang gres mempunyai ukuran 2x bab yang lama. jadi bab gres mempunyai 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 bab 1 dan bab 2 tinggal 1 elemen yaitu 90, maka pribadi masukan 90.

                                  44  55      23  88      77
        1            2              3             4           5

10  12  34  90
        1

Sekarang bab 1 (baru) sudah selesai, kini saatnya mengisi bab 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 yaitu elemen terakir, maka pribadi 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 pribadi ke elemen 3(baru).

                                                                 
        1            2              3             4           5

10  12  34  90         23  44  55 88           77
        1                               2                     3

Lalu hapus 5 bab sebelumnya.

10  12  34  90         23  44  55 88           77
        1                               2                     3

Nah kini caranya sama, Ingat bab gres akan berukuran bab 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 bab 1 yaitu 90, maka pribadi masukan 90.

                                                               77
            1                           2                     3

10 12 23 34 44 55 88 90
                  1

Karena tinggal 1 elemen pada bab 3, maka masukan elemen tersebut ke bab 2(baru). Mengapa tidak di bab 1(baru) ? Karena ibarat yang sudah saya katakan diatas, ukuran bab itu yaitu 4x2 = 8.

                                                               
            1                           2                     3

10 12 23 34 44 55 88 90            77
                  1                                2

Hapus 3 bab tersebut.

10 12 23 34 44 55 88 90            77
                  1                                2

Lalu caranya sama ibarat tadi bandingkan elemen pertama pada bab 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 bab 2 sudah kosong, jadi 88 mau dicocokin dengan apa. jadi pribadi masukin pribadi aja 88 dan 90 secara urut.

                                     
                  1                           2

10 12 23 34 44 55 77 88 90
                1

hapus 2 bab tersebut.

10 12 23 34 44 55 77 88 90
                1

akibat ! SORTED !
10 12 23 34 44 55 77 88 90

Masih belum mengerti ? Yuk tonton video ini  !



Sumber http://komputer67.blogspot.com

You Might Also Like:

Comment Policy: Silahkan tuliskan komentar Anda yang sesuai dengan topik postingan halaman ini. Komentar yang berisi tautan tidak akan ditampilkan sebelum disetujui.
Buka Komentar