Nama : Diani Widyaningrum
NPM : 21382004P
Kelas : IF 20 Dx
Mata Kuliah :Algoritma dan Struktur Data
Divide-and-conquer adalah metode pemecahan
masalah yang bekerja dengan membagi suatu masalah menjadi beberapa sub-masalah
yang lebih kecil, menyelesaikannya masing-masing secara individual, dan
akhirnya menggabungkan solusi dari setiap sub-masalah menjadi solusi dari
masalah aslinya. Algoritma bagi-dan-taklukkan adalah solusi untuk masalah
lambung cembung. Algoritma ini memiliki
kompleksitas waktu yang relatif rendah dan secara efektif menyelesaikan masalah ini (dibandingkan
dengan algoritma lain). Selain itu, algoritma ini dapat digeneralisasi untuk
masalah convex hulls dengan dimensi lebih besar dari 3.
Algoritma divide-and-conquer (ANDDC)
memecah masalah menjadi lebih kecil,
sub-masalah independen, membuatnya lebih mudah untuk mendapatkan solusi untuk
sub-masalah. Kemudian menggabungkan solusi untuk sub-masalah untuk memecahkan
masalah secara keseluruhan. Prinsip
dasar dari algoritma ini adalah membagi
n input menjadi k subset input yang berbeda (1
k sub-masalah dari k subset input yang berbeda. Setiap sub-masalah
memiliki solusinya sendiri, sehingga Anda akan menerima k sub-solusi. Kemudian,
solusi optimal atau yang diharapkan dapat diperoleh dari k dekomposisi parsial. Beberapa Contoh
Implementasinya adalah:
1.
Selection Sort
Selection
Sort adalah teknik pengurutan yang menemukan nilai tertinggi / terendah dalam array dan menempatkannya di tempat yang
benar. Algoritma ini dapat mengurutkan data dari besar ke kecil (ascending) dan
kecil ke besar (descending). Kompleksitas algoritma ini adalah (x2) dan n
adalah jumlah elemen, sehingga algoritma ini tidak cocok untuk kumpulan data
yang besar. Selection sort
merupakan metode pengurutan dengan mencari nilai data terkecil
dimulai dari data diposisi 0 hingga diposisi N-1. Jika terdapat N data dan data
terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan
metode selection sortadalah sebagai berikut:
a. Cari data terkecil dalam interval j= 0 sampai dengan j= N-1
b. Jika pada posisi pos
ditemukan data yang terkecil, tukarkan data diposisi pos dengan data di posisi i jika k.
c.
Ulangi langkah 1 dan 2 dengan
j= j+isampai dengan j= N-1, dan seterusnya sampai j = N
2.
Insertion sort
Insertion
sort merupakan algoritma pengurutan O(n2) yang memindahkan elemen satu per satu
ke posisi yang benar. Algoritma berkerja dengan memasukkan satu elemen pada
satu waktu ke bagian array yang diurutkan sebelumnya, memindahkan elemen dengan
peringkat yang lebih tinggi ke atas sesuai kebutuhan. Awal mulai, elemen
pertama (atau terkecil, atau sembarang) dari array yang tidak diurutkan
dianggap sebagai bagian yang diurutkan.
Untuk
mempermudah, algoritma insertion sort bisa dianalogikan dengan pengurutan
kartu. Misalnya hendak mengurutkan satu set kartu dari kartu yang bernilai
paling kecil hingga yang bernilai paling besar. Berikut penganalogiannya:
a. Semuanya dimulai dari posisi tangan kosong dan semua kartu masih
tersimpan di atas meja. Anggap saja kita hendak menyusun kartu ke tangan kiri.
b. Lalu kita mengambil kartu pertama dari meja dan menyimpannya di
tangan kiri.
c. Kemudian, kita ambil kartu kedua dari meja. Lalu, membandingkan
kartu tersebut dengan kartu yang ada di tangan kiri.
d. Jika kartu yang baru saja diambil dari meja memiliki nilai yang lebih
kecil daripada kartu di tangan kiri, maka kartu tersebut akan diletakan di
depan kartu pembanding
e. Kartu yang telah dibandingkan akan bergeser mundur.
f.
Proses ini akan terus
berlangsung sampai semua kartu terurut dengan benar sesuai kriteria pengurutannya.
g.
Setelah semua kartu
terurut, satu set kartu yang sudah terurut akan disimpan kembali ke meja.
3.
Radix Sort
Radix
Sort adalah algortima atau metode pengurutan (sorting) tanpa pembandingan
dengan kata lain, sorting Non-Comparasion sort dimana dalam prosesnya tidak
melakukan perbandingan antar data. Kata radix bermakna harafiah posisi dalam
angka. Di mana sederhananya, dalam representasi desimal, radix adalah digitnya.
Dalam implementasinya, Radix Sort merupakan algoritma pengurutan yang cepat,
mudah, dan sangat efektif. Namun banyak yangmengira bahwa algoritma radix
memiliki banyak batasan di mana untuk kasus-kasus tertentu tidak dapat
dilakukan dengan algoritma ini, seperti pengurutan bilangan pecahan dan
bilangan negative.
Berdasarkan
urutan pemrosesan radixnya, Radix Sort terbagi 2 macam, yaitu:
a. LSD (Least Significant Digit), di mana pemrosesan dimulai dari
radix yang paling tidak signifikan. Sorting dilakukan dengan cara mengurutkan
nilai-nilai input berdasarkan digit terjahir ke digit pertama.
b.
MSD (Most Significant
Digit), di mana pemrosesan dimulai dari radix yang paling signifikan. Sorting
dilakukan dengan cara mengurutkan nilai-nilai input berdasarkan digit pertama,
lalu dilanjutkan lagi berdasarkan radix keuda dan seterusnya.
AlAlamat web Program studi, Fakultas, Universitas
http://ti.ftik.teknokrat.ac.id, http://ftik.teknokrat.ac.id, www.teknokrat.ac.id
0 komentar:
Posting Komentar