Nama    : Aldo Fernanda

NPM    : 20312055

Kelas    : IF 20 B

IMPLEMENTASI ALGORITMA DIVIDE DAN CONQUER PADA SORTING DAN SEARCHING

Algoritma Divide and Conquer adalah algoritma yang sangat populer pada di dunia ilmu komputer. Algoritma Divide and Conquer adalah algoritma yang memiliki prinsip untuk membagi-bagi permasalahan yang terlalu besar menjadi beberapa atau sub-masalah yang lebih kecil sehingga menjadi mudah untuk diselesaikan. sub-sub masalah yang telah dibagi menjadi beberapa bagian yang lebih kecil kemudian akan dicari solusinya, setelah mendapatkan solusinya, solusi dari sub-sub masalah tersebut akan digabung menjadi satu untuk menyelesaikan masalah awal atau masalah utama. 

Algoritma Sorting atau algoritma pengurutan adalah suatu langkah yang sistematis dan berurutan. atau algoritma untuk meletakkan kumpulan data ke dalam suatu urutan tertentu berdasarkan satu atau beberapa "kunci" pada tiap-tiap elemen.

Algoritma Searching atau algoritma pencarian adalah algoritma yang menerima suatu argumen "kunci" dan dengan menggunakan suatu langkah-langkah tertentu akan mencari "kunci" tersebut. Setelah proses pencarian dilakukan, akan diperoleh salah satu dari dua kemungkinan, yaitu data berhasil ditemukan, atau data tidak ditemukan.

Divide and Conquer Pada Sorting

1. Selection Sort

Selection Sort adalah sebuah teknik pengurutan dengan cara mencari nilai tertinggi / terendah pada suatu kumpulan data (array) kemudian menempatkan nilai tersebut pada tempatnya. Algoritma ini dibagi menjadi dua berdasarkan urutan datanya, yaitu : dari kecil ke besar (Ascending), dan dari besar ke kecil (Descending). Algoritma ini pada dasarnya memilih nilai yang terbesar/terkecil, dan menukarkan nilai tersebut dengan nilai disebelah kiri/kanan pada data. Dan kemudian langkah tersebut diulang secara terus menerus hingga data tersusun. Algoritma ini tidak efektif bila digunakan pada array yang jumlah nya besar karena kompleksitas dari algoritma ini adalah O(x2) dimana n adalah jumlah item.

2. Insertion Sort

Algoritma Insertion Sort adalah sebuah teknik pengurutan dengan cara membandingkan dan mengurutkan dua data pertama pada suatu kumpulan data (array). Algoritma ini pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, data yang belum diurutkan, dan data yang sudah diurutkan. Elemen data pertama diambil dari bagian data yang belum diurutkan dan diletakkan pada posisinya di bagian data yang telah diurutkan. Algoritma ini dapat mengurutkan data secara ascending dan descending. Algoritma ini tidak efektif bila digunakan pada array dengan jumlah besar, karena kompleksitas algoritma ini adalah O() dimana n adalah jumlah item.

3. Quick Sort

Algoritma Quick Sort adalah salah satu algoritma pengurutan data, algoritma ini menggunakan teknik pemecahan data menjadi beberapa bagian atau partisi, sehingga algoritma ini disebut juga dengan nama partition exchange sort. 

Algoritma ini mengambil salah satu elemen pada suatu data secara acak (tengah) yang disebut dengan pivot lalu menyimpan semua elemen yang lebih kecil disebelah kiri pivot dan elemen yang lebih besar pada sebelah kanan pivot. Langkah tersebut dilakukan secara berulang sampai semua elemen menjadi terurut.

Divide and Conquer Pada Searching

1. Binary Search

Algoritma Binary Search atau algoritma pencarian Biner, salah satu teknik pencarian yang dilakukan secara berulang kali  membagi setengah dari jumlah data yang dicari sehingga dapat memperkecil lokasi pencarian. Dengan begitu dapat mempercepat waktu pencarian. Jika ditemukan kecocokan pada suatu data dengan data yang dicari maka pencarian akan selesai, jika tidak, pencarian akan terus dilakukan hingga akhir dari bagian data tersebut. Algoritma ini cocok untuk mencari pada jumlah data yang banyak, karena kompleksitas algoritma ini adalah O(log n) dimana n adalah jumlah item. Tetapi sebelum menggunakan algoritma ini, pastikan data sudah terurut. Jika tidak maka pencarian tidak bisa dilakukan.

2. Linear Search

Algoritma Linear Search atau pencarian linear, adalah salah satu teknik dari pencarian data, teknik ini mencari data dengan mengecek semua data secara satu per satu. Apabila ditemukan kecocokan pada data dengan data yang dicari, maka pencarian akan selesai. Jika tidak, pencarian akan terus dilakukan hingga data terakhir. Algoritma ini tidak efektif jika digunakan pada data yang besar karena kompleksitas algoritma ini adalah O(n) dimana n adalah jumlah item. Dan jika data yang dicari berada pada bagian paling akhir dari kumpulan data tersebut (array), maka pencarian tetap harus dilakukan dari yang paling awal, sehingga membutuhkan waktu yang lama. 

Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

 Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

 Sejarah Divide & Conquer

pada zaman dahulu, divide and conquer merupakan strategi militer yang dikenal dengan nama divide ut imperes. saat ini strategi tersebut menjadi strategi fundamental di dalam imlmi komputer dengan nama divide and qonqer. algoritma divide dan qonquer ini ditemukan oleh seorang ilmuan Rusia bernama Anatolii Alexeevich Karatsuba pada tahun 1960. pada mulanya beliau menemukan algoritma yang lebih mangkus untuk mengalikan dua buah bilangan bulat yang besar.

Algoritma divide and conquer di mana sub-masalah berukuran kira-kira setengah dari ukuran aslinya, memiliki sejarah yang panjang. Sementara deskripsi yang jelas tentang algoritma pada komputer muncul pada tahun 1946 dalam sebuah artikel oleh John Mauchly, gagasan untuk menggunakan daftar item yang disortir untuk memfasilitasi pencarian berasal dari setidaknya sejauh Babylonia pada 200 SM. Algoritma divide and conquer kuno lainnya adalah algoritma Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi bilangan tersebut menjadi subproblem ekuivalen yang lebih kecil dan lebih kecil, yang berasal dari beberapa abad SM.

Contoh awal dari algoritma bagi dan aklukkan dengan beberapa subproblem adalah deskripsi Gauss tahun 1805 tentang apa yang sekarang disebut algoritma Cooley-Tukey fast Fourier transform (FFT), meskipun dia tidak menganalisis jumlah operasinya secara kuantitatif, dan FFT tidak tersebar luas sampai ditemukan kembali lebih dari satu abad kemudian.

Algoritma D&C dua subproblem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan tepat adalah algoritma pengurutan gabungan, yang ditemukan oleh John von Neumann pada tahun 1945. Contoh penting lainnya adalah algoritma yang ditemukan oleh Anatolii A. Karatsuba pada tahun 1960 yang dapat mengalikan dua angka n- digit dalam O operasi (dalam notasi Big O). Algoritma ini membantah dugaan tahun 1956 Andrey Kolmogorov operasi akan diperlukan untuk tugas itu. Sebagai contoh lain dari algoritma bagi-dan-taklukkan yang awalnya tidak melibatkan komputer, Donald Knuth memberikan metode yang biasanya digunakan kantor pos untuk merutekan surat: surat diurutkan ke dalam kantong terpisah untuk wilayah geografis yang berbeda, masing-masing kantong ini diurutkan sendiri ke dalam batch untuk sub-wilayah yang lebih kecil, dan seterusnya sampai dikirimkan. Ini terkait dengan jenis radix, dijelaskan untuk mesin sortir kartu berlubang sejak tahun 1929.

 DEFINISI

Divide : membagi masalah menjadi beberaapa upa-masalah yang memiliki kemiripan dengan masalah semula namun yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama)

Conquer : memecahkan (menyelesaikan) masing-masing upa-masalah (secara rekursif)

Cara Kerja Divide and Conquer

Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif ( perulangan dengan memanggil dirinya sendiri ). Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif.

Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array.

Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu :

a. Merge sort

b. Insert sort

c. Quick sort

d. Selection sort.