Metode Devide And Conquer

Metode Devide And Conquer

SORTING

•Metode Selection Sort

•Metode Buble Sort

•Metode Merge Sort

•Metode Quick Sort

•Metode Insertion.

Hal yg mempengaruhi Kecepatan Algoritma Sort :

Jumlah Operasi Perbandingan & Jumlah Operasi

Pemindahan Data

SELECTION SORT

Tehnik pengurutan dgn cara pemilihan elemen atau proses kerja dgn memilih elemen data terkecil utk kemudian dibandingkan & ditukarkan dgn elemen pd data awal, dst s/d seluruh elemen shg akan menghasilkan pola data yg telah disort.

Prinsip Kerja dari Teknik Selection Sort ini adalah :

• Pengecekan dimulai 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 urutan yg optimal.

Contoh : 22 10 15 3 8 2

Iterasi 1

1 2 3 4 5 6

Langkah 1 : 22 10 15 3 8 2

Langkah 2 : 22 10 15 3 8 2

Langkah 3 : 2 10 15 3 8 22

Langkah 4 : Ulangi langkah 2 dan 3 .

Iterasi 2

Langkah 1: 2 10 15 3 8 22

Langkah 2: 2 10 15 3 8 22

Langkah 3: 2 3 15 10 8 22

Langkah 4: Ulangi langkah 2 dan 3 .

Lakukan Iterasi selanjutnya sampai iterasi

ke-6

BUBLE SORT
Tehnik Sort yg bekerja dgn menggunakan prinsip gelembung (buble) udara yg akan bergerak naik ke atas scr satuper satu.

Prinsip Kerja dari Buble Sort adalah :

• Pengecekan mulai dari data ke-1 sampai data ke-n
• Bandingkan data ke-n dengan data sebelumnya (n-1)
• Jika lebih kecil maka pindahkan bilangan tersebut dengan bilangan yg ada didepannya ( sebelumnya ) satu persatu (n-1,n-2,n-3,….dst)
• Jika lebih besar maka tidak terjadi pemindahan
• Ulangi langkah 2 dan 3 s/d sort optimal.

Contoh : 22 10 15 3 8 2

terasi 1

1 2 3 4 5 6

Langkah 1 : 22 10 15 3 8 2

Langkah 2 : 22 10 15 3 8 2

Langkah 3 : 2 22 10 15 3 8

Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 2

Langkah 1 : 2 22 10 15 3 8

Langkah 2 : 2 22 10 15 3 8 – 8>3, maka 8 tidak pindah, untuk selanjutnya bandingkan data sebelunya yaitu 3.

Langkah 3 : 2 3 22 10 15 8

Langkah 4 : Ulangi langkah 2 dan 3

Lakukan Iterasi selanjutnya sampai iterasi ke- 6

QUICK SORT
Sort dgn iterasi scr urut dr posisi elemen 1, ke-2 dstnya. Tukarkan setiap elemen pd posisi tsb dgn elemen lain yg nilainya memang shrsnya berada pd posisi tsb.

Prinsip Kerja dari Quick Sort adalah :

•Tentukan Lower Bound (Batas Bawah) & Upper Bound (Batas Atas)

•Bandingkan Lower Bound (LB) dengan Upper Bound (UB)

•Jika LB>UB, Tukar (cari operasi perbandingan yang optimal/terkecil)

•Jika LB =< UB, maka Next Upper Bound & Lower Bound

•Ulangi langkah diatas s/d sort.

Contoh : 22 10 15 3 8 2

Iterasi 1

1 2 3 4 5 6

Langkah 1 : 22 10 15 3 8 2

LB UB

Langkah 2 :2 10 15 3 8 22

Iterasi 2

Langkah 1 : 2 10 15 3 8 22

LB/UB

Langkah 2 :2 10 15 3 8 22

LB UB

Iterasi 3

Langkah 1 :2 10 15 3 8 22

LB UB

Langkah 2 :2 8 15 3 10 22

Iterasi 4

Langkah 1 :2 8 15 3 10 22

LB UB

Langkah 2 :2 3 15 8 10 22

Lakukan Iterasi selanjutnya sampai iterasi

ke- 6

INSERTION SORT
Prinsip dasar Insertion adalah secara berulang-ulang menyisipkan / memasukan setiap elemen. ke dlm posisinya / tempatnya yg benar.

Prinsip Kerja Insertion Sort adalah

• Pengecekan mulai dari data ke-1 sampai data ke-n
• Bandingkan data ke-I ( I = data ke-2 s/d data ke-n )
• Bandingkan data ke-I tersebut dengan data sebelumnya (I-1), Jika lebih kecil maka data tersebut dapat disisipkan ke data awal sesuai dgn posisisi yg seharusnya
• Lakukan langkah 2 dan 3 untuk bilangan berikutnya ( I= I+1 ) sampai didapatkan urutan yg optimal.

Contoh : 22 10 15 3 8 2

Iterasi 1

1 2 3 4 5 6

Langkah 1: 22 10 15 3 8 2

Langkah 2: 22 10 15 3 8 2

Langkah 3: 10 22 15 3 8 2

Langkah 4: Ulangi langkah 2 dan 3

Iterasi 2

Langkah 1: 10 22 15 3 8 2

Langkah 2: 10 22 15 3 8 2

Langkah 3: 10 15 22 3 8 2

Langkah 4: Ulangi langkah 2 dan 3

Lakukan Iterasi selanjutnya sampai iterasi

ke- 6

Catatan : Setiap ada pemindahan, maka elemen. Yang sudah ada akan di insert sehingga akan bergeser kebelakang.

MERGE SORT

Prinsip Kerja Merge Sort adalah :

• Kelompokan deret bilangan kedalam 2 bagian, 4 bagian, 8 bagian, ……dst à (2n)
• Urutkan secara langsung bilangan dalam kelompok tsb.
• Lakukan langkah diatas untuk kondisi bilangan yg lain sampai didapatkan urutan yg optimal .

Contoh : 22 10 15 3 8 2

Iterasi 1

1 2 3 4 5 6

Langkah 1 : 22 10 15 3 8 2

Langkah 2 : 10 22 3 15 2 8

Iterasi 2

Langkah 1 : 10 22 3 15 2 8

Langkah 2 : 3 10 15 22 2 8

Iterasi 3

Langkah 1 :3 10 15 22 2 8

Langkah 2 :2 3 8 10 15 22

Mata Kuliah : Logika dan Algoritma

Oleh : Dani Rohpandi S.kom

Sumber : Modul Kuliah STMIK Tasikmalaya