Implementasi Algoritma Divide and Conquer
Quick Sort dan Sequential Search
Algoritma merupakan kumpulan perintah yang memiliki daya guna yang sangat besar bagi masyarakat. Algoritma biasanya digunakan sebagai kumpulan perintah untuk menyelesaikan suatu masalah. Algoritma ini memiliki aplikasi yang bermacam-macam dalam setiap masalah yang ada. Contohnya saja adalah algoritma cara menyelesaikan suatu aritmatika yang rumit, algoritma untuk menghitung luas penampang dari suatu kabel, atau bahkan untuk menghitung bayaran parkir di setiap mal.
Salah satu aplikasi bentuk pemrograman ini adalah dalam bahasa permrograman yang disebut bahasa C. Dimana bahasa C ini memiliki suatu aturan-aturan tertentu yang sangat penting sehingga dalam penggunaanya kita harus memperhatikan cara menggunakan aturan tersebut.
Implementasi Algoritma Divide and Conquer 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.
void insertionSort(Object array[], int startIdx, int endIdx)
{
for (int i = startIdx; i < endIdx; i++) {
int k = i;
for (int j = i + 1; j < endIdx; j++) {
if(((Comparable) array[k]).compareTo(array[j])>0) {
k = j;
}
}
swap(array[i],array[k]);
}
};
Implementasi Algoritma Divide and Conquer 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
void quickSort(Object array[], int leftIdx, int rightIdx) {
int pivotIdx;
/* Kondisi Terminasi */
if (rightIdx > leftIdx) {
pivotIdx = partition(array, leftIdx, rightIdx);
quickSort(array, leftIdx, pivotIdx-1);
quickSort(array, pivotIdx+1, rightIdx);
}
}
Atau dapat dijelaskan dengan cara berikut ini :
Quick sort melakukan proses langsung di dalam array masalah sehingga tidak memerlukan memory tambahan untuk menyimpan submasalah. Merge sort melakukan sebaliknya.
Tehnik quick sort sebagai berikut
· Mempartisi table sehingga diasumsikan pengurutan dari kiri ke kanan
· Elemen T[i] berada di tempat yang benar
· Tidak ada elemen yang lebih besar nilainya di kiri i
· Tidak ada elemen yang nilainya lebih kecil di kanan i
· Partisi tabel (secara implisit juga melakukan pengurutan tabel). Jika belum urut, partisi kembali partisi dari table (rekursif)
· Gabungkan semua partisi.
Berikut ilustrasi quick sort : Ilustrasi Quick
Implementasi Algoritma Divide and Conquer Sequential Sort
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.
void SeqSearch1 (int T[], int Nmax,
int value, int *idx)
{
/*kamus lokal*/
int i;
/*Algoritma*/
i = 1;
while ((i<Nmax) && (T[i] !=
value))
{
i = i + 1;
}
if (T[i]==value)
{
*idx = i;
}
else
{
*idx = 0;
}
}
Atau juga bisa dengan pemahaman berikut :
Sequential search Dikenal sebagai linear search Mencari key(info yang dicari) pada suatu data tak terurut hingga data di temukan atau data sudah mencapai akhir larik
Syarat menggunakan sekuential search adalah :
• Data tersimpan dalam keadaan terurut
• Pencarian secara ascending atau descending
• Alamat terakhir(P1) dari larik (P) adalah = 0<= P1 <= P-1
contoh :
Nama : Muhammad Fitriyan
NPM : 19312310
Kelas : IF 19 GX
Fakultas : http://ftik.teknokrat.ac.id/
Universitas : https://teknokrat.ac.id/
Belum ada Komentar untuk "Implementasi Algoritma Divide and Conquer"
Posting Komentar