-->

Memahami Merge Sort Step By Step


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

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 Response to "Memahami Merge Sort Step By Step"

Post a Comment

Popular posts

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel