TENTANG AJENG: ltm 10

PERTEMUAN 10

METODE DEVIDE AND CONQUER (SORTING)

1. Jelaskan pengertian Metoda Devide And Conquer serta tujuannya

2. Sebutkan Algoritma Metoda sorting

a. Metoda Selection Sort

b. Buble Sort

c. Merge Sort

d. Quick Sort

e. Insertion Sort

3. Terdapat deret angka : 99 , 34 , 11 , 50 , 23 , 89 , 65 , 2 , 6 , 37 , 74 , 44 Urutkan dengan Seluruh teknik sorting yang ada

4. Terdapat deret angka :

12 , 45, 10 , 55 , 32 , 81 , 59 , 21 , 16 , 71 , 40 , 90

Urutkan dengan Seluruh teknik sorting yang ada

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

TENTANG AJENG

Sabtu, 22 Maret 2014

ltm 10

Tidak ada komentar:

Posting Komentar