Strategi Algoritma: Marge Sort Dengan Algoritma Divide and Conquer

Definisi Divide and Conquer

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

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

Combine: mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.  

Disini kita akan membahas contoh marge sort dengan algoritma Divide and Conquer.

Berikut misalkan tabel A berisi elemen-elemen berikut:

Algortimanya:

Skema utama divide dan conquer

procedure DIVIDE_and_CONQUER(input n : integer) { Menyelesaikan masalah dengan algoritma D-and-C. Masukan: masukan yang berukuran n Keluaran: solusi dari masalah semula } Deklarasi r, k : integer Algoritma if n  n0 then {ukuran masalah sudah cukup kecil } SOLVE upa-masalah yang berukuran n ini else Bagi menjadi r upa-masalah, masing-masing berukuran n/k for masing-masing dari r upa-masalah do DIVIDE_and_CONQUER(n/k) endfor COMBINE solusi dari r upa-masalah menjadi solusi masalah semula } endif

Jika pembagian selalu menghasilkan dua upa-masalah yang berukuran sama:
procedure DIVIDE_and_CONQUER(input n : integer) { Menyelesaikan masalah dengan algoritma D-and-C. Masukan: masukan yang berukuran n Keluaran: solusi dari masalah semula } Deklarasi r, k : integer Algoritma if n  n0 then {ukuran masalah sudah cukup kecil } SOLVE upa-masalah yang berukuran n ini else Bagi menjadi 2 upa-masalah, masing-masing berukuran n/2 DIVIDE_and_CONQUER(upa-masalah pertama yang berukuran n/2) DIVIDE_and_CONQUER(upa-masalah kedua yang berukuran n/2) COMBINE solusi dari 2 upa-masalah endif
Codingnya Mengunakan Bahasa Pemrograman C++:

#include <cstdlib> #include <iostream> using namespace std; typedef int larik [10];//tipe data untuk merge void baca_data(int A[], int n){ /*proses input dan baca data*/ for (int i = 0; i < n; i++){ cout <<"Data ke - " << i + 1 <<" : "; cin >> A[i];}} void cetak_data(int A[], int n){ /*cetak data*/ for (int i = 0; i < n; i++){ cout << A[i] <<" ";}} void tukar_data(int *a, int *b){ /*tukar data*/ int temp; temp = *a; *a = *b; *b = temp;} void minimum(int A[], int dari, int n, int *tempat){ int i, min; min = A[dari]; *tempat = dari; for (i = dari + 1; i < n; i++) if (A[i] < min){ min = A[i]; *tempat = i;}} void merge(larik a, int kiri, int tengah, int kanan){ int bagkir, postemp, bykel, i; larik temp; bagkir = tengah -1; postemp = kiri; bykel = kanan - kiri + 1; while ((kiri <= bagkir) && (tengah <= kanan)) if ((a[kiri] <= a[tengah])){ temp[postemp] = a[kiri]; postemp = postemp + 1; kiri = kiri + 1;} else { temp[postemp] = a[tengah]; postemp = postemp + 1; tengah = tengah + 1;} while ((kiri <= bagkir)){ temp[postemp] = a[kiri]; postemp = postemp + 1; kiri = kiri + 1;} while ((tengah <= kanan)){ temp[postemp] = a[tengah]; postemp = postemp + 1; tengah = tengah + 1;} for (i = 1; i <= bykel; i++){ a[kanan] = temp[kanan]; kanan = kanan -1;}} void merge_sort(larik A, int kiri, int kanan){ int tengah; if (kiri < kanan){ tengah = (kiri + kanan) / 2; merge_sort(A, kiri, tengah); merge_sort(A, tengah + 1, kanan); merge(A, kiri, tengah + 1, kanan);}} int main(int argc, char *argv[]){ int data[10], n; cout <<"\tMERGE SORT April 2012\n"; cout <<"\nBanyak data : "; cin >> n; baca_data(data, n); cout <<"\nData yang anda masukan : "; cetak_data(data, n); merge_sort(data, 0, n - 1); cout <<"\n\nSetelah urutkan : "; cetak_data(data, n); system("PAUSE"); return EXIT_SUCCESS; }

Outputnya:

Oke untuk sementara itu saja yang dapat Saya bagikan kepada Teman-teman Informatika, kalau ada kekurangan dalam postingan ini mohon di maklumi karena saya masih dalam tahap belajar :D

Ulasan lain tentang  Strategi Algoritma