Metode Divide And Conquer

Metode Divide And Conquer

        Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma 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 ).
• Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.

       Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut, maka 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 merge sort, insert sort, quick sort, dan selection sort.

SORTING

1. Metode Selection Sort
2. Metode Buble Sort
3. Metode Merge Sort
4. Metode Quick Sort
5. Metode Insertion.

Hal yg mempengaruhi Kecepatan Algoritma Sort : Jumlah Operasi Perbandingan & Jumlah Operasi Pemindahan Data.

SELECTION SORT

Tehnik pengurutan dengan cara pemilihan elemen atau proses kerja dengan memilih elemen data terkecil untuk kemudian dibandingkan & ditukarkan dengan elemen pada data awal, dst s/d seluruh elemen sehing akan menghasilkan pola data yg telah disort.

Prinsip Kerja dari Teknik Selection Sort ini adalah :

1. Pengecekan dimulai data ke-1 sampai dengan data ke-n
2. Tentukan bilangan dengan Index terkecil dari data bilangan tersebut
3. Tukar bilangan dengan Index terkecil tersebut dengan bilangan pertama ( I = 1 ) dari data bilangan tersebut.
4. Lakukan langkah 2 dan 3 untuk bilangan berikutnya ( I= I+1 ) sampai didapatkan urutan yg optimal.

Contoh : 22 10 15 3 8 2

Iterasi 1

                     1   2   3  4 5 6

Langkah 1 : 22 10 15 3 8 2

Langkah 2 : 2 22 10 15 3 8

Langkah 3 : 2 10 15 3 8 22

Langkah 4 : Ulangi langkah 2 dan 3 .

Iterasi 2

Langkah 1 : 2 10 15 3 8 22

Langkah 2 : 2 10 15 3 8 22

Langkah 3 : 2 3 15 10 8 22

Langkah 4 : Ulangi langkah 2 dan 3 .

Lakukan Iterasi selanjutnya sampai iterasi ke-6

BUBBLE SORT

Tehnik Sort yg bekerja dgn menggunakan prinsip gelembung (bubble) udara yg akan bergerak naik ke atas secara satuper satu.

Prinsip Kerja dari Bubble Sort adalah :

1. Pengecekan mulai dari data ke-1 sampai data ke-n
2. Bandingkan data ke-n dengan data sebelumnya (n-1)
3. Jika lebih kecil maka pindahkan bilangan tersebut dengan bilangan yg ada didepannya ( sebelumnya ) satu persatu (n-1,n-2,n-3,....dst).
4. Jika lebih besar maka tidak terjadi pemindahan
5. Ulangi langkah 2 dan 3 s/d sort optimal.

Contoh : 22 10 15 3 8 2

terasi 1

                    1   2   3  4 5 6

Langkah 1: 22 10 15 3 8 2

Langkah 2: 22 10 15 3 8 2

Langkah 3: 22 10 15 3 2 8

Langkah 4: Ulangi langkah 2 dan 3

Hasil iterasi 1 : 2 22 10 15 3 8

QUICK SORT

Metode QuickSort sering disebut metode partition exchange sort, Diperkenalkan oleh C.A.R. Hoare. Pada metode ini jarak kedua elemen yang akan ditukarkan nilainya ditentukan cukup besar. Misal ada N elemen dalam keadaan urut turun, adalah mungkin untuk mengurutkan N elemen tersebut dengan

N/2 kali, yakni pertama kali menukarkan elemen paling kiri dengan paling kanan, kemudian secara bertahap menuju ke elemen yang ada di tengah. Tetapi hal ini hanya bisa dilakukan jika kita tahu pasti bahwa urutannya adalah urut turun.

INSERTION SORT

Prinsip dasar Insertion adalah secara berulang-ulang menyisipkan / memasukan setiap elemen. ke dlm posisinya / tempatnya yg benar.

1. Prinsip Kerja Insertion Sort adalah
2. Pengecekan mulai dari data ke-1 sampai data ke-n
3. Bandingkan data ke-I ( I = data ke-2 s/d data ke-n )
4. Bandingkan data ke-I tersebut dengan data sebelumnya (I-1), Jika lebih kecil maka data tersebut dapat disisipkan ke data awal sesuai dgn posisisi yg seharusnya
5. Lakukan langkah 2 dan 3 untuk bilangan berikutnya ( I= I+1 ) sampai didapatkan urutan yg optimal.

Contoh : 22 10 15 3 8 2

Iterasi 1

                     1   2   3  4 5 6

Langkah 1 : 22 10 15 3 8 2

Langkah 2 : 22 10 15 3 8 2

Langkah 3 : 10 22 15 3 8 2

Langkah 4 : Ulangi langkah 2 dan 3

Iterasi 2

Langkah 1 : 10 22 15 3 8 2

Langkah 2 : 10 22 15 3 8 2

Langkah 3 : 10 15 22 3 8 2

Langkah 4 : Ulangi langkah 2 dan 3

Lakukan Iterasi selanjutnya sampai iterasi ke- 6

Catatan : Setiap ada pemindahan, maka elemen. Yang sudah ada akan di insert sehingga akan bergeser kebelakang.

MERGE SORT

Prinsip Kerja Merge Sort adalah :

1. Kelompokan deret bilangan kedalam 2 bagian, 4 bagian, 8 bagian, ......dst (2n)
2. Urutkan secara langsung bilangan dalam kelompok tsb.
3. Lakukan langkah diatas untuk kondisi bilangan yg lain sampai didapatkan urutan yg optimal .

Contoh : 22 10 15 3 8 2

Iterasi 1

                    1   2   3  4 5 6

Langkah 1: 22 10 15 3 8 2

Langkah 2: 10 22 3 15 2 8

Iterasi 2

Langkah 1: 10 22 3 15 2 8

Langkah 2: 3 10 15 22 2 8

Download Data Metode Divide And Conquer (Klik Disini)


Sekian pembahasan dari Metode Divide And Conquer. Semoga bermamfaat dan terima kasih.

Read More

KONSEP TIPE DATA C++

TIPE DATA UNTUK PEMROGRAMAN C++
Konsep tipe data C++ dibagi menjadi beberapa tipe data, seperti:

1. Tipe Sederhana(Simple type)
   ➤Int ( Integer )
   ➤Bool ( Boolean )
   ➤Char ( Charakter )
   ➤Tipe Float
2. Tipe String
   ➤Operasi String
3. Tipe Terstuktur
   ➤Array
   ➤Struc

Variabel & Konstanta :

Variabel :

• Untuk menyimpan suatu nilai, dan nilai yang ada padanya dapat diubah selama eksekusi berlangsung.
• Penamaan variabel bersifat case sensitive (huruf besar & huruf kecil dianggap berbeda).
• Harus dideklarasikan dahulu sebelum digunakan

Konstanta :

Sebuah variabel dengan tipe data tertentu dan memiliki nilai data yang akan selalu tetap di dalam program.

1. TIPE DATA SEDERHANA
     ⇨Tipe Int ( Integer )
Adalah tipe data yang nilainya tidak memiliki titik desimal. Dalam bahasa pemrograman pascal hanya digit yang bisa muncul sebagai Integer,tidak boleh ada character lain lain termasuk koma kecuali + dan -.

     ⇨Bool ( Boolean )

Adalah nilai data yang sangat penting untuk pengambilan suatu keputusan dalam suatu program karena pada tipe ini data akan mempunyai dua nilai, yaitu benar atau salah, True or False.
     ⇨Char ( Charakter )

Kata ini digunakan untuk menampung data sebuah karakter. Dan hanya memuat satu karakter saja berupa huruf, angka atau simbol. Karakter perlu ditulis didalam tanda petik tunggal(‘). Contoh : ‘A’, ‘a’, ‘B’, ‘b’
     ⇨Tipe Float

Adalah tipe data yang nilainya pecahan(memiliki titik desimal).

2. TIPE STRING
Operasi String adalah data yang berisi sederetan karakter yang banyaknya bisa berubah-ubah sesuai kebutuhan. Dengan ketentuan besarnya adalah 1 s/d 255 karakter.
Cara pendeklarasian adalah :
Contoh : char nama[50];
                 char *alamat;

Fungsi pada Operasi STRING

1. Strcpy() : untuk menyalin nilai string.
   Contoh dalam penggalan program c++:
   Cout<<“Masukan Kata ? “;gets(kata);
   Strcpy(copy,kata);
   Cout<<“Hasilnya ? “<<copy;
2. Strcat() : untuk menggabungkan nilai string.
   Contoh dlm penggalan program c++ :
   Cout<<“Kata Pertama ? “;gets(a);
   Cout<<“Kata Kedua ? “;cin(b);
   Strcat(a,b);
   Cout<<“Hasil Gabungan : “<<a;
3. Strcmp() : untuk membandingkan 2 nilai string.
   Contoh dalam penggalan program c++:
   char sa[]="Logika";
   char sb[]="Logika Algoritma";
   char sc[]="Logika Algoritma & Pemprograman";
   /*Melakukan perbandingan terhadap dua string dan penampilan nilainya*/
   printf("Nilai Yang dibandingkan sa,sb :
   %d\n",strcmp(sa,sb));
   printf("Nilai Yang dibandingkan sa,sc :
   %d\n",strcmp(sa,sc));
   printf("Nilai Yang dibandingkan sb,sa :
   %d\n",strcmp(sb,sa));
   getch();
   return 0;
   }
4. Strlen() : untuk mengetahui panjang nilai string
   Contoh dalam penggalan program c++:
   cout<<"Masukkan Kata = ";
   cout<<"Masukkan Kata = ";
   cout<<"Panjang Kata yang telah diinput = ";
   cout<<strlen(angka);
5. Strchr () : untuk mencari nilai karakter dalam string.
   Contoh dalam penggalan program C++:
   int main(void){
   char str [100]="Aisyah Zahra";
   char karakter='Z';
   char *hasil;
   hasil=strchr(str,karakter);
   printf("Hasil Peubah :%s\n",hasil);
   printf("Karakter %c ditemukan pada indeks ke-%d",karakter,(hasil-str));
   getch();
   return 0; }

3. TIPE TERSTRUKTUR

• Array
  Adalah tipe data terstruktur yang mempunyai komponen dalam jumlah yang tetap dan setiap komponen mempunyai tipe data yang sama. Posisi komponen dalam larik dinyatakan sebagai nomor index.
• Struct
  Adalah kumpulan vaariabel yang dinyatakan dengan sebuah nama,dengan sifat setiap variabel dapat memiliki tipe ang berlainan. Untuk menyimpan suatu variabel dalam pemrograman C++, diperlukan suatu tempat khusus di dalam memori komputer.
  struct data_pegawai
  {
  int nip;
  char nama[25];
  char alamat[40];
  }

Download Data :

KONSEP TIPE DATA C++

Sekian pembahasan dari KONSEP TIPE DATA C++. Saya Mr.JAR mengucapkan terima kasih dan Semoga bermamfaat.

Read More

LARIK ATAU ARRAY

       Array atau Larik adalah struktur data yang menyimpan sekumpulan elemen yang bertipe sama yang disimpan ke dalam variabel dengan nama yang sama, setiap elemen diakses langsung melalui indeksnya. Indeks array haruslah tipe data yang menyatakan keterurutan, misalnya integer atau karakter.

Variabel Array terdiri dari :

1.  Array Berdimensi Satu
2.  Array Berdimensi Dua

Array 1 (satu) Dimensi

Array berdimensi satu dapat dikatakan sebagai suatu daftar yang linier atau sebuah kolom. Bentuk deklarasi dari array jenis ini dalam bahasa C++ adalah :Tipe_Data Nama_Variabel [ukuran];

Array 2 (Dua) Dimensi

Bentuk Umum :

Tipe_Data Nama_Variabel [index-1] [index-2]

Diberikan Matrik A sebagai berikut :
1  1  1  1
0  1  1  1
0  0  1  1
0  0  0  1
Perintah pokok yang digunakan pada pengisian Matriks A adalah:
jawabannya:
Jika i<=j maka A[i,j]=1, Jika i>j maka A[i,j]=0

Penjelasannya:
Matrik A kita kita ganti dengan sitem Array dimensi 2(bisa di mulai dari [0,0] atau [1,1] tergantung dari matriksnya)
[0.0]  [0.1]  [0.2]  [0.3]  =  [1]  [1]  [1]  [1]
[1.0]  [1.1]  [1.2]  [1.3]  =  [0]  [1]  [1]  [1]
[2.0]  [2.1]  [2.2]  [2.3]  =  [0]  [0]  [1]  [1]
[3.0]  [3.1]  [3.2]  [3.3]  =  [0]  [0]  [0]  [1]
[i , j] [i , j]  [i , j]  [i , j]

maka dari penjelasan di atas kita bisa mengambil kesimpulan:
Jika i<=j maka A[i,j]=1, Jika i>j maka A[i,j]=0

Contoh lainya
Diberikan Matrik A sebagai berikut :
1  2  3  4
0  2  3  4
0  0  3  4
0  0  0  4
Perintah pokok yang digunakan pada pengisian Matriks A adalah:
jawabanya :
Matrik A kita kita ganti dengan sitem Array dimensi 2(bisa di mulai dari [0,0] atau [1,1] tergantung dari matriksnya)
[1.1]  [1.2]  [1.3]  [1.4]  =  [1]  [2]  [3]  [4]
[2.1]  [2.2]  [2.3]  [2.4]  =  [0]  [2]  [3]  [4]
[3.1]  [3.2]  [3.3]  [3.4]  =  [0]  [0]  [3]  [4]
[4.1]  [4.2]  [4.3]  [4.4]  =  [0]  [0]  [0]  [4]
[i , j] [i , j]  [i , j]  [i , j]

maka dari penjelasan di atas kita bisa mengambil kesimpulan:
Jika i<=j maka A[i,j]=j, Jika i>j maka A[i,j]=0

Download Data:LARIK ATAU ARRAY

Sekian pembahasan dari Larik atau Array. Saya Mr.JAR mengucapkan terima kasih dan Semoga bermamfaat.

Read More