IMPLEMENTASI ALGORITMA DIVIDE AND CONQUER PADA SORTING
DAN SEARCHING
1.
Insertion sort
Salah satu algoritma sorting yang paling sederhana
adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti
mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma
insertion sort bekerja dalam pengurutan kartu. Anggaplah anda ingin mengurutkan
satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.
Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama,
disusun dari kiri ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang
lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu
pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja
kedua. Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada
pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah
perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu pada meja
pertama telah diletakkan berurutan pada meja kedua. Algoritma insertion sort
pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum
diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama
diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai
posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini
dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian
array yang belum diurutkan.
Algoritmanya :
2.
Selection sort
Jika anda diminta untuk membuat algoritma sorting
tersendiri, anda mungkin akan menemukan sebuah algoritma yang mirip dengan selection
sort. Layaknya insertion sort, algoritma ini sangat rapat dan mudah untuk
diimplementasikan. Mari kita kembali menelusuri bagaimana algoritma ini
berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu tersebut akan
diurutkan secara ascending. Pada awalnya, kartu tersebut akan disusun secara
linier pada sebuah meja dari kiri ke kanan, dan dari atas ke bawah. Pilih nilai
kartu yang paling rendah, kemudian tukarkan posisi kartu ini dengan kartu yang
terletak pada pojok kiri atas meja. Lalu cari kartu dengan nilai paling rendah
diantara sisa kartu yang tersedia. Tukarkan kartu yang baru saja terpilih
dengan kartu pada posisi kedua. Ulangi langkah – langkah tersebut hingga posisi
kedua sebelum posisi terakhir dibandingkan dan dapat digeser dengan kartu yang
bernilai lebih rendah.
Ide utama dari algoritma selection sort adalah memilih
elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan
elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total
elemen dikurangi 1.
Algoritmanya :
3.
Quick sort
Quicksort ditemukan oleh C.A.R Hoare. Seperti pada
merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda
dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai
berikut :
1. Divide
Memilah rangkaian data menjadi dua sub-rangkaian
A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau
sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama
dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada
elemen q merupakan salah satu bagian dari prosedur pemisahan
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif
Pada algoritma quicksort, langkah “kombinasi” tidak di
lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array
Algoritmanya :
4.
Counting sort
Adalah sebuah algoritma sorting linear yang digunakan
untuk mengurutkan ‘item’ ketika urutannya telah ditentukan dan memiliki panjang
yang terbatas. Bilangan interval yang telah tetap, katakana k1 ke k2 adalah
contoh dari ‘item’ tersebut. Counting sort sebenarnya merupakan metode
pengurutan yang memanfaatkan index variabel array. Hanya effektif pada data
yang nilainya kecil.
Algoritma ini diproses dengan mendefinisikan sebuah
hubungan urutan antara ‘item’ yang akan disorting. Katakana ‘item’ yang akan
disorting adalah variable A. Maka, terdapat sebuah array tambahan dengan ukuran
yang serupa dengan array A. katakana array tersebut adalah array B. untuk
setiap element di A, sebut e, algoritma ini menyimpan jumlah ‘item’ di A lebih
kecil dari atau sama dengan e di B(e). jika hasil sorting yang terakhir
disimpan di array C, maka untuk masing-masing e di A, dibuat dalam arah yang
sebaliknya, yaitu C[B(e)]=e. setelah step di atas, niali dari B(e) berkurang
dengan 1.
Algoritma ini membuat 2 passover A dan passover B.
Jika ukuran dari range k lebih kecil dari ukuran input n, maka time complexity = O(n). perhatikan juga
bahwa algoritma ini stabil yang berarti bahwa sambungan diselesaikan dengan
langsung mengabarkan element-element yang muncul pertama kali.
Adapun syarat algoritma ini berjalan dengan baik
ialah:
1.
Data harus
bilangan bulat yang bernilai lebih besar atau sama dengan nol
2.
Range data diketahui
Ada 3 macam array yang terlibat:
1.
Array untuk
mengisi bilangan yang belum diurutkan.
2.
Array untuk
mengisi frekuensi bilangan itu, sekaligus sebagai penghitung kejadian.
3.
Array untuk
mengisi bilangan yang sudah diurutkan.
Algoritmanya :
5.
Radix sort
Radix sorting bisa digunakan ketika masing-masing
universal element bisa dilihat sebagai sebuah urutan digit (atau huruf atau
symbol lainnya). Sebagai contoh, kita bisa membuat masing-masing bilangan bulat
antar 0 sampai 99 sebagai sebuah urutan dengan dua digit (seperti “05”). Untuk
menyorting sebuah array dari angka 2-digit, algoritma ini membuat dua ‘passing’
sorting melalui array tersebut. Pada ‘passing’ pertama, element array disorting
pada least significant decimal digit. Kunci utama dari radix sort adalah pada
passing yang kedua. Hasilnya, setelah kedua passing melewati array tersebut, data
yang terisi telah disorting.
Algoritmanya :
6.
Linear searching
Algoritma pencarian secara linear adalah algoritma
untuk mencari sebuah nilai pada table sambarang dengan cara melakukan pass atau
transversal. Transversal dari awal sampai akhir table. Ada dua macam cara
pencarian pada table. Algoritma mempunyai dua jenis metode yaitu dengan Boolean
dan tanpa Boolean.
Algoritma di atas melakukan pengulangan sampai i sama dengan Nmax (ukuran tabel) atau harga value dalam tabel sudah ditemukan. Kemudian harga i di-assign ke dalam variable idx. Elemen terakhir diperiksa secara khusus.
Refrensi :
https://ikkholis27.wordpress.com/
Nama
: Yohanes Bosco Christo Setya Atmaka
NPM
: 19316049
Kelas
: TK 19 C
Fakultas
: http://ftik.teknokrat.ac.id/
Universitas : https://teknokrat.ac.id/
Komentar
Posting Komentar