LTM LOGIKA ALGORITMA PERTEMUAN 10 (jawaban)

Metode Devide dan Conquer (Sorting)

JAWAB

1. Metode Devide dan Conquer adalah metode pemecahan masalah yang besar dengan cara melakukan pembagian masalah yang besar tersebut menjadi beberapa bagian yang lebih kecil secara rekursif hingga masalah tersebut dapat dipecahkan secara langsung.

   Tujuan : untuk dapat memecahkan masalah sorting dan searching.

2. Algoritma metode Sorting..

a. Selection sort :            - pengecekan dimulai dari data ke-1 sampai dengan data ke-n ,

                                                - tentukan bilangan dengan index terkecil dari data bilangan tersebut,

                    - tukar bilangan dengan index terkecil tersebut dengan bilangan                                pertama (i=1) dari data bilangan tersebut,

                    - lakukan langkah 2 dan 3 untuk bilangan berikutnya (i=i+1) sampai

                      didapatkan bilangan yang optimal.

    b. Bubble sort    :            - pengecekan dimulai dari data ke-1 sampai dengan data ke-n ,

                                    - bandingkan data ke-n dengan data sebelumnya (n-1),

                    - jika lebih kecil maka pindahkan bilangan tersebut dengan bilangan

                      yang ada didepannya satu persatu (n-1,n-2,n-3,…dst),

                                    - jika lebih besarmaka tidak terjadi pemindahan,

                                    - ulangi langkah 2 dan 3 sampai dengan sort optimal.

    c. Marge sort     :            - kelompokan deret bilangan kedalam 2 bagian,4 bagian,8bagian dst(2ⁿ) 

                                    - urutkan secara langsung bilangan dalam kelompok tsb,

                                    - lakukan langkah diatas sampai didapatkan urutan yang optimal.

    d. Quick sort     :            - tentukan Lower Bound (Batas Bawah)&Upper Bound (Batas Atas),

                                    - bandinglan Lower Bound (LB) dan Upper Bound (Up),

                                    - jika LB>UB tukar(cari operasi perbandingan yang optimal/terkecil),

                                    - jika LB=<UB, maka next Upper Bound & Lower Bound,

                                    - ulangi langkah diatas sampai dengan sort optimal.

   e. Insertion sort : - pengecekan mulai dari data ke-1 sampai data ke-n,

                                    - bandingkan data ke-i (i=data ke-2 sampai data ke-n),

                                    - bandingkan data ke-i tsb dengan data sebelumnya (i-1), jika lebih

                                      kecil maka data tsb dapat disisipkan ke data awal sesuai dengan

                                      posisi yang seharusnya.

                                    - lakukan langkah 2 dan 3 untuk bilangan berikutnya (i=i+1) sampai

                                      didapatkan urutan yang optimal.

3. Diketahui deret angka : 99   34   11   50   23   89   65   2   6   37   74   44

                                                   

    a. Selection sort

       I₁                = 2       34        11         50        23        89        65        99        6          37        74        44

       I₂                = 2       6          11         50        23        89        65        99        34        37        74        44       

       I₃            = 2       6          11         23        50        89        65        99        34        37        74        44

       I₄                = 2       6          11         23        34        89        65        99        50        37        74        44

       I₅            = 2       6          11         23        34        37        65        99        50        89        74        44

       I₆            = 2       6          11         23        34        37        44        99        50        89        74        65

       I₇            = 2       6          11         23        34        37        44        50        99        89        74        65

       I₈            = 2       6          11         23        34        37        44        50        65        89        74        99

       I₉            = 2       6          11         23        34        37        44        50        65        74        89        99

    b. Bubble sort

       I₁            = 99    34        11         50        23        89        65        2          6          37        44        74

       I₂            = 2       99        34        11         50        23        89        65        6          37        44        74

       I₃                = 2       6          99        34        11         50        23        89        65        37        44        74

       I₄            = 2       6          99        34        11         50        23        37        89        65        44        74

       I₅                = 2       6          99        34        11         50        23        37        44        89        65        74

       I₆                = 2       6          99        34        11         50        23        37        44        65        89        74

       I₇            = 2       6          99        34        11         50        23        37        44        65        74        89

       I₈            = 2       6          99        34        11         23        50        37        44        65        74        89

       I₉            = 2       6          99        34        11         23        37        50        44        65        74        89

       I₁₀= 2     6          99        34        11         23        37        44        50        65        74        89

       I₁₁           = 2       6          99        11         34        23        37        44        50        65        74        89

       I₁₂= 2     6          99        11         23        34        37        44        50        65        74        89

       I₁₃= 2     6          11         99        23        34        37        44        50        65        74        89

       I₁₄= 2     6          11         23        99        34        37        44        50        65        74        89

       I₁₅= 2     6          11         23        34        99        37        44        50        65        74        89

       I₁₆= 2     6          11         23        34        37        99        44        50        65        74        89

       I₁₇= 2     6          11         23        34        37        44        99        50        65        74        89

       I₁₈= 2     6          11         23        34        37        44        50        99        65        74        89

       I₁₉= 2     6          11         23        34        37        44        50        65        99        74        89

       I₂₀=2      6          11         23        34        37        44        50        65        74        99        89       

       I₂₁= 2     6          11         23        34        37        44        50        65        74        89        99 

    c. Marge sort

       I₁            = 34    99        11         50        23        89        2          65        6          37        44        74

       I₂            = 11     34        50        99       2          23        65        89        6          37        44        74

       I₃            = 2       11         23        34        50        65        89        99        6          37        44        74

       I₄                = 2       6          11         23        34        37        44        50        65        74        89        99

    d. Quick sort

       I₁                = 44    34        11         50        23        89        65        2          6          37        74        99

       I₂            = 37    34        11         50        23        89        65        2          6          44        74        99  

       I₃            = 6       34        11         50        23        89        65        2          37        44        74        99

       I₄                = 2       34        11         50        23        89        65        6          37        44        74        99

       I₅            = 2       6          11         50        23        89        65        34        37        44        74        99

       I₆            = 2       6          11         44        23        89        65        34        37        50        74        99

       I₇            = 2       6          11         37        23        89        65        34        44        50        74        99

       I₈            = 2       6          11         34        23        89        65        37        44        50        74        99

       I₉            = 2       6          11         23        34        89        65        37        44        50        74        99

       I₁₀= 2     6          11         23        34        74        65        37        44        50        89        99

       I₁₁              = 2       6          11         23        34        50        65        37        44        74        89        99

       I₁₂= 2     6          11         23        34        44        65        37        50        74        89        99

       I₁₃= 2     6          11         23        34        37        65        44        50        74        89        99

       I₁₄= 2     6          11         23        34        37        50        44        65        74        89        99

       I₁₅= 2     6          11         23        34        37        44        50        65        74        89        99

    e. Insertion sort

       I₁            = 34    99        11         50        23        89        65        2          6          37        74        44

       I₂            = 34    11         99        50        23        89        65        2          6          37        74        44

       I₃                = 11     34        99        50        23        89        65        2          6          37        74        44

       I₄            = 11     34      50        99        23        89        65        2          6          37        74        44

       I₅            = 11     34        50        23        99        89        65        2          6          37        74        44

       I₆            = 11     34        23        50        99        89        65        2          6          37        74        44

       I₇            = 11     23        34        50        99        89        65        2          6          37        74        44

       I₈            = 11     23        34        50        89        99        65        2          6          37        74        44

       I₉            = 11     23        34        50        89        65        99        2          6          37        74        44

       I₁₀= 11    23        34        50        65        89        99        2          6          37        74        44

       I₁₁           = 11     23        34        50        65        89        2          99        6          37        74        44

       I₁₂= 11    23        34        50        65        2          89        99        6          37        74        44

       I₁₃= 11    23        34        50        2          65        89        99        6          37        74        44

       I₁₄= 11    23        34        2          50        65        89        99        6          37        74        44

       I₁₅= 11    23        2          34        50        65        89        99        6          37        74        44

       I₁₆= 11    2          23        34        50        65        89        99        6          37        74        44

       I₁₇= 2     11         23        34        50       65        89        99        6          37        74        44

       I₁₈= 2     11         23        34        50       65        89       6          99        37        74        44

       I₁₉= 2     11         23        34        50       65        6          89        99        37        74        44

       I₂₀= 2     11         23        34        50        6          65        89        99        37        74        44

       I₂₁= 2     11         23        34        6          50        65        89        99        37        74        44       

       I₂₂=2      11         23        6          34        50        65        89        99        37        74        44

       I₂₃=2      11         6          23        34        50        65        89        99        37        74        44

       I₂₄=2      6          11         23        34        50        65        89        99        37        74        44

       I₂₅=2      6          11         23        34        50        65        89        37        99        74        44

       I₂₆=2      6          11         23        34        50        65        37        89        99        74        44

       I₂₇=2      6          11         23        34        50        37        65        89        99        74        44

       I₂₈=2      6          11         23        34        37        50        65        89        99        74        44

       I₂₉=2      6          11         23        34        37        50        65        89        74        99        44

       I₃₀=2      6          11         23        34        37        50        65        74        89        99        44

       I₃₁=2      6          11         23        34        37        50        65        74        89        44        99

       I₃₂=2      6          11         23        34        37        50        65        74        44        89        99

       I₃₃=2      6          11         23        34        37        50        65        44        74        89        99

       I₃₄=2      6          11         23        34        37        50        44        65        74        89        99

       I₃₅=2      6          11         23        34        37        44        50        65        74        89        99

4. Diketahui deret angka : 12   45   10   35   32   81   59   21   16   71   40   90

    a. Selection sort

       I₁            = 10     45        12        35        32        81        59        21        16        71        40        90

       I₂            = 10     12        45        35        32        81        59        21        16        71        40        90

       I₃                = 10     12        16        35        32        81        59        21        45        71        40        90

       I₄            = 10     12        16        21        32        81        59        35        45        71        40        90

       I₅            = 10     12        16        21        32        35        59        81        45        71        40        90

       I₆            = 10     12        16        21        32        35        40        81        45        71        59        90

       I₇            = 10     12        16        21        32        35        40        45        81        71        59        90

       I₈            = 10     12        16        21        32        35        40        45        59        71        81        90

   b. Bubble sort

       I₁            = 12     45        10        35        32        81        59        21        16        40        71        90

       I₂            = 12     45        10        16        35        32        81        59        21        40        71        90

       I₃            = 12     45        10        16        21        35        32        81        59        40        71        90

       I₄            = 12     45        10        16        21        35        32        40        81        59        71        90

       I₅            = 12     45        10        16        21        35        32        40        59        81        71        90

       I₆            = 12     45        10        16        21        35        32        40        59        71        81        90

       I₇            = 12     45        10        16        21        32        35        40        59        71        81        90

       I₈            = 10     12        45        16        21        32        35        40        59        71        81        90

       I₉            = 10     12        16        45        21        32        35        40        59        71        81        90

       I₁₀= 10   12        16        21        45        32        35        40        59        71        81        90

       I₁₁           = 10     12        16        21        32        45        35        40        59        71        81        90

       I₁₂= 10   12        16        21        32        35        45        40        59        71        81        90

       I₁₃= 10   12        16        21        32        35        40        45        59        71        81        90

    c. Marge sort

       I₁            = 12     45        10        35        32        81        59        21        16        71        40        90

       I₂            = 10     12        35        45       21        32        59        81        16        40        71        90

       I₃            = 10     12        21        32        35        45        59        81        16        40        71        90

       I₄            = 10     12        16        21        32        35        40        45        59        71        81        90

    d. Quick sort

       I₁            = 10     45        12        35        32        81        59        21        16        71        40        90

       I₂            = 10     40        12        35        32        81        59        21        16        71        45        90

       I₃            = 10     16        12        35        32        81        59        21        40        71        45        90

       I₄            = 10     12        16        35        32        81        59        21        40        71        45        90

       I₅            = 10     12        16        21        32        81        59        35        40        71        45        90

       I₆            = 10     12        16        21        32        45        59        35        40        71        81        90

       I₇            = 10     12        16        21        32        40        59        35        45        71        81        90

       I₈            = 10     12        16        21        32        35        59        40        45        71        81        90

       I₉            = 10     12        16        21        32        35        45        40        59        71        81        90

       I₁₀= 10   12        16        21        32        35        40        45        59        71        81        90

   e. Insertion sort

       I₁            = 12     10        45        35        32        81        59        21        16        71        40        90        

       I₂            = 10     12        45        35        32        81        59        21        16        71        40        90

       I₃            = 10     12        35        45        32        81        59        21        16        71        40        90

       I₄ = 10   12        35        32        45        81        59        21        16        71        40        90       

       I₅            = 10     12        32        35        45        81        59        21        16        71        40        90

       I₆            = 10     12        32        35        45        59        81        21        16        71        40        90

       I₇            = 10     12        32        35        45        59        21        81        16        71        40        90

       I₈            = 10     12        32        32        45        21        59        81        16        71        40        90

       I₉            = 10     12        32        35        21        45        59        81        16        71        40        90

       I₁₀= 10   12        32        21        35        45        59        81        16        71        40        90

       I₁₁           = 10     12        21        32        35        45        59        81        16        71        40        90              

       I₁₂= 10   12        21        32        35        45        59        16        81        71        40        90

       I₁₃= 10   12        21        32        35        45        16        59        81        71        40        90

       I₁₄= 10   12        21        32        35        16        45        59        81        71        40        90

       I₁₅= 10   12        21        32        16        35        45        59        81        71        40        90

       I₁₆= 10   12        21        16        32        35        45        59        81        71        40        90

       I₁₇= 10   12        16        21        32        35        45        59        81        71        40        90

       I₁₈= 10   12        16        21        32        35        45        59        71        81        40        90

       I₁₉= 10   12        16        21        32        35        45        59        71        40        81        90

       I₂₀=10    12        16        21        32        35        45        59        40        71        81        90

       I₂₁= 10   12        16        21        32        35        45        40        59        71        81        90

       I₂₂=10    12        16        21        32        35        40        45        59        71        81        90