Implementasi Algoritma Divided & Conquer

-

Implementasi Algoritma Divided & Conquer

  • Implementasi Algoritma Divided & Conquer Quick Sort

            Quick Sort ditemukan oleh C.A.R Hoare. Algoritma ini sama seperti merge sort yaitu berdasarkan pada pola divide & conquer. Walaupun sama namun algoritma ini terdapat perbedaan dalam langkah - langkah penyelesaiannya, yaitu :

  1. Divide

    2. Memilah rangkaian data menjadi dua bagian rangkaian A[p...q - 1] dan A[q + 1...r] dimana setiap elemen A[p...q + 1] adalah kurang atau sama dengan A[q] dan setiap elemen A[q + 1...r] adalah lebih atau sama dengan A[q]. A[q] merupakan elemen pivot dan perhitungan elemen q merupakan salah satu bagian dari prosedur pemisahan.

  2. Conquer

    3. Mengurutkan elemen pada sub-rangkaian secara rekursif.

Berikut ini algoritma dari quick sort

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);
    }
}
 

  • Implementasi Algoritma Divided & Conquer Linear Search
            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. Berikut algoritma dari Linear Search :


void seqSearch1 (int T[], int Nmax, int value, int *idx) { 
int i; 
i = 1 
while ((i<Nmax) && (T[i] != value)) { 
    i = i + 1; 
    } 

if (T[i] == value) {
*idx = i; 
    }
else {
*idx = 0;
    }
}

            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.

void seqSearch1 (int T[], int Nmax, int value, int *idx) { 
int i; 
boolean found; 
i = 1 
found = false; 
while ((i<Nmax) && (!found)) { 
    if (T[i] == value) { 
        found = true; 
        } 
    else { 
i = i + 1; 
    } 
} 
if (found) {
*idx = i; 
    }
else {
*idx = 0;
    }
}

 Tentang Pembuat :





Nama    : Eugiutama Fitra Luqman
NPM     : 20312109
Kelas     : IF 20 C

Webstie Teknokrat :

FSIP Teknokrat 

Komentar

Posting Komentar

Postingan populer dari blog ini

Macam - Macam Permasalahan dalam Algoritma

-
Gambar
Permasalahan pada Algoritma Combinatorial Problems  atau Masalah Kombinatorial adalah salah satu pokok bahasan pada Matematika Diskrit yang berfungsi untuk menyusun, mengelompokkan, mengurutkan atau memilih sejumlah objek diskrit tertentu. Dalam perkembangan Matematika, dapat dilihat bahwa kajian kombinatorial sangat menarik bagi sebagian orang. Berikut ini adalah beberapa kesulitan yang terdapat pada Combinatorial Problems : Beberapa objek karbinatorik tumbuh dengan cepat seiring dengan bertambahnya masalah Belum diketahuinya algoritma pasti yang dapat menyelesaikan masalah pada Combinatorial Problems. Combinatorial Problem memiliki beberapa contoh sebagai berikut : Travelling Salesman Problems           Travelling Salesman Problem atau yg disingkat dengan TSP adalah sebuah masalah kombinasi optimasi dalam operasi penelitian dan teori ilmu komputer. Dengan daftar sejumlah kota yang akan dikunjungi, cara ini sangat bagus untuk menemukan dengan cepat kota yang akan dikunjungi. TSP adal
Baca selengkapnya

IMPLEMENTASI ALGORITMA BRANCH & BOUND

-
Gambar
                 Sebagaimana pada algortima runut-balik, algoritma Branch & Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang Solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status. Pembentukan pohon ruang status pada algoritma B&B berbeda dengan pembentukan pohon pada algoritma runutbalik. Bila pada algoritma runut-balik ruang solusi dibangun secara Depth-First Search(DFS), maka pada algoritma B&B ruang solusi dibangun dengan skema Breadth-First Search (BFS).                Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost). Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound). Pada prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan. Fungsi heuristik untuk menghitung taksiran nilai tersebut dinyatakan secara umum sebagai : (i) = (i) + (i) yang dalam hal ini : (i) = o
Baca selengkapnya