BAB 1
Pengertian Dasar Logika Dan Algoritma
Sejarah Algoritma
Asal kata Algoritma berasal dari nama Abu Ja’far Mohammed Ibn Musa al-Khowarizmi, ilmuan Persia yang menulis kitab al jabr w’al-muqabala (rules of restoration and reduction) sekitar tahun 825 M
A. Algoritma
Urutan langkah-langkah untuk memecahkan masalah
Urutan logis pengambilan putusan untuk memecahkan masalah urutan langkah logis, berarti algoritma harus mengikuti suatu urutan tertentu, tidak boleh melompat-lompat.
Alur pemikiran dalam menyelesaikan suatu pekerjaan yang
dituangkan secara tertulis.
Alur pikiran yang artinya algoritma seseorang dapat berbeda dari algoritma orang lain.
tertulis, yang artinya dapat berupa kalimat, gambar, atau tabel tertentu.
Dalam bidang komputer, algoritma sangat diperlukan dalam menyelesaikan berbagai masalah pemrograman, terutama dalam komputasi numeris. Tanpa algoritma yang dirancang baik maka proses pemrograman akan menjadi salah, rusak, atau lambat dan tidak efisien.
Note:
Algoritma Di butuhkan untuk memerintah computer mengambil langkah- langkah tertentu untuk menyelesaikan masalah
Algoritma Pemrograman Program
Agar algoritma dapat memerintah (diproses) komputer, maka dirubah menjadi bentuk program (melalui proses pemrograman).
Penulisan Algoritma :
1. Menggunakan bahasa natural (Bahasa manusia: Indonesia, Inggris) Kelemahannya masih sering membingungkan (ambigu) / sulit dipahami.
2. Menggunakan Flowchart Baik karena alur algoritma dapat dilihat secara visual, tetapi repot pembuatannya jika algoritma panjang
3. Menggunakan Pseudocode
Sudah dekat dengan bahasa pemrograman, tetapi sulit dimengerti oleh orang yang belum tahu pemrograman
B. Tahap Analisa Algoritma
1. Bagaimana merencanakan algoritma
Dengan Mendefinisikan masalah.
Contoh : Permasalahan menghitung luas lingkaran,
dengan data yang diketahui adalah diameter lingkaran. Rumus : ∏ . r2 dengan Phi = 3.14 atau 22/7.
2. Bagaimana menyatakan suatu algoritma (menulis algoritma)
Dengan flowchart / diagram alir
Program Flowchart
Yaitu bagan yang menggambarkan urutan logika dari suatu prosedur pemecahan masalah.
1. Simbol yang digunakan :
2. menunjukkan awal dan akhir dari program
3. memberikan niai awal pada suatu variabel atau counter
4. menunjukkan pengolahan aritmatika dan pemindahan data
5. menunjukkan proses input atau output
6. untuk mewakili operasi perbandingan logika
7. proses yang ditulis sebagai sub program, yaitu prosedur/ fungsi
8. penghubung pada halaman yang sama
9. Penghubung pada halaman yang berbeda
Dengan statement program /penggalan program :
Dari algoritama yang telah dibuta dapat diterjemahkan ke dalam
Statemen program C++ sebagai berikut :
#include <iostream>
| ||
using namespace std;
| ||
int main()
| ||
{
| ||
float phi = 3.14;
| ||
float Diameter, Radius, Luas_Lingkaran;
| ||
cout << "Masukkan Nilai Diameter : ";
| ||
cin >> Diameter;
| ||
Radius = Diameter / 2;
| ||
Luas_Lingkaran = phi * Radius * Radius;
| ||
cout << "Luas Lingkaran adalah :
| ||
Luas_Lingkaran;
| ||
return 0;
|
Studi Kasus :
Buatlah Algoritma untuk memilih bilangan terbesar dari 3 buah bilangan
?
Dengan Bahasa Natural
1. Memasukkan bilangan pertama
2. Memasukkan bilangan kedua
3. Memasukkan bilangan ketiga
4. Ambil bilangan pertama dan set maks sama dengan bilangan pertama
5. Ambil bilangan kedua dan bandingkan dengan maks
6. Apa bila bilangan kedua lebih besar dari maks, set maks sama dengan bilangan kedua
7. Ambil blangan ketiga dan bandingan dengan maks
8. Apabila bilangan ketiga lebih besar dari maks, set maks sama dengan bilangan ketiga
9. Variabel maks berisi bilangan terbesar
10. Tampilkan hasil bilangan terbesar
11. Selesai
Dengan Flowchart
Dengan Pseudo-code
Input (Bilangan_pertama)
Input (Bilangan_kedua) Input (Bilangan_ketiga) maks bilangan_pertama
if (maks < bilangan_kedua) then maks bilangan_kedua
if (maks < bilangan_ketiga) then maks bilangan_ketiga
output (maks)
End.
Dengan Bahasa Pemrogaraman C++
BAB 2
Konsep Algoritma
KONSEP ALGORITMA
TUGAS 2 :
1. Seorang Petani akan berpergian ke kota dengan membawa seekor kambing, Anjing dan Rumput Yang ketiganya memliki berat yang tidak jauh berbeda, ditengah jalan petani harus menyebrangi sungai dengan menggunakan perahu dan untuk melaluinya petani tersebut tidak diperbolehkan membawa sekaligus bawaannya mengingat kapasitas kekuatan perahu tersebut, dan untuk melaluinya petani harus membawa satu persatu bawaannya. Ditanya: berapa kali petani tersebut harus melalui sungai dengan memperhatikan bahwa kambing makan rumput, anjing makan kambing ?.
Buatlah Algoritma Dengan Bahasa Natural dan flowchart dokumen Dari
Cerita di atas!
2. Bagaimana caranya untuk menyeberangkan tiga orang missionaris yang sedang dikejar oleh Tiga orang kanibal ke sisi pulau yang ada diseberangnya
Dengan catatan : Bila misionarisnya Lebih sedikit dari dari kanibal, maka
misionaris tersebut akan dimakannya.
Buatlah Algoritma Dengan Bahasa Natural dan flowchart dokumen Dari
Cerita di atas!
3. Seorang siswa mendaftar santri baru pada bagian registrasi, setelah menyelesaikan penulisan biodata santri, siswa tersebut di diperkenankan untuk pindah ke bagian seleksi untuk diuji baca alQur’an, jika ujian
alQur’an lulus maka siswa tersebut melanjutkan ke bagian asrama untuk menentukan asrama, jika ujian alqur’an tidak lulus maka siswa tersebut berstatus waiting list (daftar tunggu ) dan bisa kembali 1 minggu setelahnya.
Dari cerita di atas lakukan analisa dan buatlah :
a. Flowchart Proses
b. Flowchart Dokumen
c. Flowchart dengan program Raptor!
d. Program dengan bahasa C++
BAB 3
Konsep Tipe Data
Bahasa Pemrograman C++
TIPE DATA
1. Tipe data Sederhana
Tipe data yang umum digunakan dalam bahasa pemrograman C++ diataranya adalah :
a. Tipe data angka
Untuk tipe data data angka memiliki nilai dan panjang field yang berbeda
- Integer (int) : “merupakan tipe data yang digunakan untk meyimpan nilai dengan bilangan bulat positif tanpa titik decimal pada bilangan
tersebut, misalnya 1, 2, 3 ... dst”
1. Dengan nilai konstata misalnya
Int x = 5;
2. Dengan data inputan int x ;
- Floating point : “Merupakan tipe data yang digunakan untuk menyimpan data angka dengan nilai pecahan misalnya 27.72; 54.36
dst” namun pada floating point kita dapat mengenal macam-
macamnya dan mengetahui panjang field yang tersimpan pada masing-masing tipe datanya
- Tpe data floating point terbagi atas :
1. Float : “merupakan tipe data yang menyimpan nilai pecahan
penyimpanan data 4-8 bytes”
2. Double dan long : “merupakan tipe data yang menyimpan nilai 8 byte”.
Cara mendeklarasikannya yaitu :
1. Dengan nilai konstan float x = 3.12;
double x = 3.122222;
2. Dengan nilai inputan float x;
doubel x;
b. Tipe data karakter : “merupakan tipe data yang digunakan untuk menyimpan nilai karakter (1 buah huruf)”
Cara mendeklarasikannya adalah :
char nilai = ‘A’;
c. Tipe data string : “merupakan tipe data yang menyimpan nilai dari gabungan beberapa karakter” Cara mendeklarasikannya adalah : char Kota (10);
MENGENAL PEMROGRAMAN C++
Secara ringkas, struktur bahasa C++ dapat terdiri dari:
1. Header
2. Program utama
- deklarasi label
- definisi konstanta
- definisi tipe
- deklarasi variabel
- deklarasi prosedur
- deklarasi fungsi
3. Bagian Pernyataan (statetement program/baris perintah)
a. Deklarasi variabel
Untuk membuat variabel/pengenal/indentifier pada yaitu dengan menuliskan nama variabel dan tipe datanya pada bagian deklarasi variabel
Format penulisan: [tipe_data nama_identifier ; ]
contoh :
int i = 1;
char nama[10];
bool Jenis_kelamin=true;
float Luas,Panjang,Lebar;
double luas;
b. Operator Aritmatika
Operator aritmatik yang dipakai dalam C++ adalah :
+ tambah
- kurang
* kali
/ bagi
% modulus
Operator-operator di atas dikenal sebagai binary operators artinya operator-operator ini memerlukan dua operan. Operator +, -, * dan / telah jelas artinya, yang perlu dijelaskan adalah operator modulus (%), operator ini dipakai untuk mencari sisa dan pembagian antar bilangan bulat, misalnya 20 % 8 menghasilkan 4 karena sisa pembagian dari 20 dibagi 8 adalah 4. Operator + dan – dapat dipakai sebagai unary operator, artinya operator-operator ini hanya memerlukan satu operan saja. Suatu variabel dapat dinyatakan positip atau negatip dengan unary operator + atau -, misalnya:
a = -25;
b = +25;
c = -a+b; .
Suatu ekpresi dapat mengandung lebih dari satu jenis operator, C++ mengartikannya berdasar order of precedence dari operator-operator tersebut. Order of precedence dari operator menunjukkan hirarki matematis dari suatu operator misalnya:
2 + 3 * 2;
C++ akan menghitung 3*2 dulu karena operator kali (*) hirarkinya lebih tinggi dari operator + sehingga ekpresi di atas hasilnya adalah 8, bukan
10. Untuk operator aritmatik order of precedence-nya yang tinggi adalah
kali (*), bagi (/) dan modulus (%) sedang yang rendah adalah tambah (+)
dan kurang (-),Jadi C++ selalu melakukan kali, bagi dan modulus lalu
diikuti tambah dan kurang. Operator-operator dalam C++ terdistribusi dalam 15 hirarki precedence yang dapat dilihat pada tabel di bawah ini.
Berdasar table of precedence di atas assignment berlipat banyak dapat dimengerti dengan mudah, misalnya :
A = b = c = d = e = 100;
dalam hal ini assosiativitasnya adalah dari kanan ke kin, jadi 100 dipasangkan di variabel e, lalu dari variabel e ke variabel d demikian seterusnya sampai akhirnya n, sehingga setelah selesai dieksekusi variabel-variabel a, b, c, d, e mempunyai nilai 100
BAB 4
Diagram Alur / Flowchart
Flowchart
Flowchart adalah representasi grafik dari langkah-langkah yang harus diikuti dalam menyelesaikan suatu permasalahan yang terdiri atas sekumpulan simbol, dimana masing-masing simbol merepresentasikan suatu kegiatan tertentu.
Flowchart diawali dengan penerimaan input, pemrosesan input, dan diakhiri dengan penampilan output.
bagan yang menggambarkan urutan logika dari suatu prosedur pemecahan masalah.
suatu diagram yang menggambarkan susunan logika suatu program
Simbol yang digunakan :
menunjukkan awal dan akhir dari programmemberikan niai awal pada suatu variabel atau countermenunjukkan pengolahan aritmatika dan pemindahan datamenunjukkan proses input atau outputuntuk mewakili operasi perbandingan logikaproses yang ditulis sebagai sub program, yaitu prosedur/ fungsi penghubung pada halaman yang sama penghubung pada halaman yang berbeda
Simbol Flowchart dan fungsinya :
Flowchart terdiri dari 3 struktur :
1. Struktur Squence /sederhana
Diagram yang alurnya mengalir secara berurutan dari ataske bawah atau dengan kata lain tidak adanya percabangan atau pengulangan
Flowchart dengan struktur yang beurutan alirannya dari atas kebawah secara berurutan
Contoh : flowchart dari algoritma mencari luas persegi panjang, Luas
Lingkaran.
VARIABEL
Variabel, sebagai tempat untuk menyimpan suatu nilai yang sejenis. Terdiri dari nama dari variable itu sendiri dan nilai yang disimpan.
variabel / Peubah suatu nilai yg dapat berubah harganya.
Contoh pemberian nilai ke variabel : A = 5 variabel A diberi nilai 5.
A = B variabel A diberi nilai sama dengan nilai variabel B. variabel B sudah memiliki nilai sebelumnya
A = A +1 variabel A dirubah isinya dengan variabel A yang dijumlahkan dengan 1. (proses increament)
Jenis variabel terbagi atas :
1. Variabel numerik berisi angka numerik /bilangan
2. Variabel String berisi karakter.
STRUKTUR BRANCHING /Percabangan
1. Bersyarat
Diagram yg alurnya ada/banyak terjadi alih kontrol berupa percabangan & terjadi apabila kita dihadapkan pada suatu Kondisi dengan dua pilihan BENAR/ SALAH
Struktur :
If then If then else If then elseif 
Case of.
2. Tidak Bersyarat
Struktur : GOTO
Studi kasus
Buat diagram alur untuk masalah menghitung temperatur dalam derajat
Fahrenhait yang diubah ke dalam derajat Celcius & Reamur.
Dengan rumus :
C =
|
5 (F-32)
|
R =
|
4 (F-32)
|
9
|
9
|
Derajat Celsius (°C) adalah suatu satuan ukur suhu yang mendapatkan
namanya dari ahli astronomi Anders Celsius (1701–1744), yang pertama kali mengusulkannya pada tahun 1742. Skala suhu celsius didesain supaya titik beku air berada pada 0 derajat dan titik didih pada 100 derajat di tekanan atmosferik standar.
Fahreheit adalah salah satu skala temperatur selain Celsius dan kelvin. Nama Fahrenheit diambil dari ilmuwan Jerman yang bernama Gabriel Fahrenheit (1686-1736). Dalam skala ini, titik beku air adalah 32 derajat Fahrenheit (ditulis 32°F) dan titik didih air adalah 212 derajat Fahrenheit. Negatif 40 derajat Fahreheit sama dengan negatif 40
derajat Celsius.
BAB 5
Looping (Perulangan)
Suatu algoritma memiliki struktur sequence/berurutan branching/percabangan looping/perulangan.
Struktur looping digunakan untuk mengulangi langkah-langkah sebelumnya yang telah dikerjakan, kondisi perulangan dilakukan sampai
suatu kondisi berhenti terpenuhi.
Proses Perulangan digunakan contohnya untuk membuat algortima : “menampilkan bilangan berurutan dari 1 sampai dengan 10” “menampilkan deret : 3, 7, 11, 15 …… N, sampai sejumlah N” 
“menampilkan bilangan dari 10 sampai dengan 1 “
“menampilkan bilangan berurutan dari 1 sampai dengan 10” “menampilkan deret : 3, 7, 11, 15 …… N, sampai sejumlah N” “menampilkan bilangan dari 10 sampai dengan 1 “
Dari algoritma diatas dipilih algortima pertama. Proses perulangan akan dilakukan yaitu :
mencetak bilangan dari 1 -10melakukan proses increament (penambahan bilangan dengan 1) proses perulangan ini akan dilakukan sampai kondisi terakhir yaitu mencetak bilangan 10.
BAB 6
Struktur Rekursif
Rekursif adalah suatu proses yang bisa memanggil dirinya sendiri.
Perulangan Rekursif dan Perulangan Iteratif.
Perulangan rekursif merupakan salah satu metode didalam pemrograman yang mana dalam sebuah fungsi terdapat intruksi yang memanggil fungsi itu sendri, atau lebih sering disebut memanggil dirinya sendiri.
Perulangan iteratif merupakan perulangan yang melakukan proses perulangan terhadap sekelompok intruksi. Perulangan dilakukan dalam batasan syarat tertentu. Ketika syarat tersebut tidak terpenuhi lagi maka perulangan aka terhenti.
Persamaan :
1. Iteratif dan rekursif merupakan metode atau teknik didalam perulangan (looping)
2. Sama-sama memiliki bagian yang berfungsi sebagai batas dalam sebuah perulangan
Perbedaan :
Iteratif dalam melakukan perulangan membutuhkan suatu instruksi program seperti for dan while do, sedangkan rekursi tidak memakai instruksi program seperti itu. Cukup dengan fungsi tersebut.
#include <iostream>
using namespace std;
int rekursif(int f) nama fungsi: rekursif.
{
rekursif; fungsi bernama
rekursif ini dikatakan Sebagai fungsi rekursi karena dia memanggil Dirinya sendiri
}
int main()
{int x; rekursif(x); return 0;
}
Pada contoh diatas: sebuah fungsi/prosedur adalah sebuah proses.
Contoh fungsi rekursif diatas adalah sebuah
proses, dan didalam fungsi rekursif tersebut
terdapat perintah/proses yang mengerjakan/memanggil proses rekursif (memanggil dirinya sendiri),sehingga fungsi/prosedur rekursif ini dinamakan fungsi rekursi.
Pada contoh diatas proses rekursi ini tidak memiliki batas berhenti.
Untuk mengetahui contoh fungsi rekursif ini silahkan melihat pada slide perkuliahan.
BAB 7
Larik (Array)
Array
- Kumpulan variabel memiliki tipe data yang sama
- Variabel bisa simpel (char, float, double, int) atau tipe data kompleks (struct, pointer, class)
- Setiap elemen array ditandai dengan nama array dan diikuti dengantanda kurung siku buka dan tutup dimana didalamnya terdapat jumlah elemen array
- Elemen array harus dinyatakan sebagai non negatif integer
Contoh Program :
#include <iostream.h>
#include <conio.h>
main()
{
int a[5]={10,15,20,25,30};
int b[5]={10,20};
int c[5]={15,0,30};
int j;
// Menampilkan nilai dari element array
cout<<endl;
for(j=0;j<5;j++)
{
cout<<"A ["<<j<<"] = "<<a[j]<<" , B ["<<j<<"] = "<<b[j]<<" , C ["<<j<<"] = "<<c[j]<<endl;
}
getch();
}
#include <conio.h>
main()
{
int a[5]={10,15,20,25,30};
int b[5]={10,20};
int c[5]={15,0,30};
int j;
// Menampilkan nilai dari element array
cout<<endl;
for(j=0;j<5;j++)
{
cout<<"A ["<<j<<"] = "<<a[j]<<" , B ["<<j<<"] = "<<b[j]<<" , C ["<<j<<"] = "<<c[j]<<endl;
}
getch();
}
Void
Void
adalah tipe data yang digunakan untuk tipe suatu fungsi yang tidak
mengembalikan nilai. Void itu digunakan biasa nya untuk sebuah function
atau procedure yang tidak membutuhkan nilai balik. Input dalam tipe data
void disebut dengan “Parameter”.
Ciri" :
1. Tidak adanya keyword return.
2. Tidak adanya tipe data di dalam deklarasi fungsi.
3. Menggunakan keyword void.
4. Tidak dapat langsung ditampilkan hasilnya.
5. Tidak memiliki nilai kembalian fungsi.
1. Tidak adanya keyword return.
2. Tidak adanya tipe data di dalam deklarasi fungsi.
3. Menggunakan keyword void.
4. Tidak dapat langsung ditampilkan hasilnya.
5. Tidak memiliki nilai kembalian fungsi.
Contoh Program:
Void lpp (int p, int l)
{
Int luas;
Cout<<”Luasnya adalah = “<<luas;
}
void main()
{
lpp (6,5);
lpp (7,3);
lpp (8,4);
getch();
}
BAB 8
Sorting Metode Devide And Conquer
Pengurutan (Sorting). proses mangatur sekumpulan obyek/data menurut urutan atau susunan tertentu.
Urutan obyek/data tersebut dapat menaik (ascending) atau menurun
(descending).
Data yang diurutkan dapat berupa data bertipe dasar atau data bertipe struktur
Data yang sudah terurut memiliki keuntungan yaitu Mempercepat proses pencarian data.
Metode Pengurutan
Algoritma pengurutan / sorting bermacam-macam dan setiap algoritma ini memiliki kinerja yang berbeda-beda. Berikut ini macam-macam algoritma pengurutan:
1. Metode Selection Sort
2. Metode Buble Sort
3. Metode Merge Sort
4. Metode Quick Sort
5. Metode Insertion
Hal yg mempengaruhi Kecepatan Algoritma Sorting adalah Jumlah
Operasi Perbandingan & Jumlah Operasi Pemindahan Data
1. Selection Sort (Metode Seleksi).
Tehnik pengurutan dengan cara pemilihan elemen dengan memilih elemen data terkecil utk kemudian dibandingkan & ditukarkan dengan elemen pada data awal, dst s/d seluruh elemen shg akan menghasilkan pola data yg telah disort.
Merupakan kombinasi antara sorting dan searching
Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.
Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1])
ALGORITMA SELECTION SORT.
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 implementasi dalam bahasa C++ adalah sebagai berikut
/*selection Sort*/
#include <iostream>
#include <iomanip>
using namespace std;
int selectionsort (int array[], const int size)
{
int i, j, kecil, temp;
for (i=0; i<size; i++)
{
kecil=i;
for (j=i; j<size; j++)
{
if (array[kecil]>array[j]) {
kecil = j;
}
}
temp = array[i];
array[i] = array[kecil];
array[kecil] = temp;
}
}
int main()
{
int NumList[10];
int N;
cout<<"Masukkan jumlah data = ";
cin>>N;
for(int i=0;i<N;i++)
{
cout<<"Masukkan data ke-"<<(i+1)<<" = ";
cin>>NumList[i];
}
cout<<"\n\n";
selectionsort(NumList,N);
cout<<"Data setelah diurutkan:\n";
for (int i=0; i<N; i++) {
cout<<setw(3)<<NumList[i]<<"\n\n";
}
return 0;
}
2. Metode Bubble Sort (Gelembung)
Teknik yang diinspirasi oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung lebih ringan dari pada air, maka gelembung akan naik keatas. (benda yang berat akan terbenam, benda ringan terapung).Elemen data yang paling kecil diapungkan diangkat keatas melalui proses pertukaran.
Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya
Algoritma Bubble Sort
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.
Analogi :
Larik dengan urut menaik, elemen larik yang berharga paling kecil diapungkan , artinya diangkat ke atas (atau ke ujung kiri larik) melalui proses pertukaran.
Proses pengapungan ini dilakukan sebanyak N-1 langkah dengan N
adalah ukuran larik.
Pada akhir setiap langkah ke-I, larik L[1..N] akan terdiri atas dua bagian yaitu bagian yang sudah terurut, yaitu L[1..I] dan bagian yang belum terurut L[I+1..N]. Setelah langkah terakhir, diperoleh larik L[1..N] yang terurut menaik.
Bubble Sort Disebut juga dengan metode Penukaran (Exchange Sort), yaitu metoda yang mendasarkan pada penukaran elemen untuk mencapai keadaan urut yang diinginkan.
Algoritma Metode gelembung :
- langkah 0 : Baca vector yang akan diurutkan (dalam program utama)
- langkah 1 : Kerjakan langkah 2 untuk i = 1 sampai N-1
- langkah 2 : Kerjakan langkah 3 untuk j = 1 sampai N- i
- langkah 3 : Tes apakah A[j] > A[j +1] ? Jika ya, tukarkan nilai kedua elemen ini - langkah 4 : Selesai
Contoh Program Buble Sort
#include <iostream>
using namespace std;
int data[10],data2[10];
int n;
void tukar(int a,int b)
{
int t;
t = data[b]; data[b] = data[a]; data[a] = t;
}
void Input()
{
cout<<"Masukkan jumlah data = ";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"Masukkan data ke-"<<(i+1)<<" = ";
cin>>data[i]; data2[i] = data[i];
}
cout<<endl;
}
void Tampil()
{
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
}
void bubble_sort()
{
for(int i=1;i<n;i++)
{
for(int j=n-1;j>=i;j--){
if(data[j]<data[j-1]) {
tukar(j,j-1);
}
}
Tampil();
}
cout<<endl;
}
main()
{
cout<<"Fungsi Bubble Sort"<<endl; Input();
cout<<"Proses Bubble Sort"<<endl; Tampil();
bubble_sort();
return 0;
}
3. Metode INSERTION SORT (Sisip)
Algoritma ini dianalogikan seperti mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang
Analogi :
Mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.
Seluruh kartu diletakkan pada meja, kita sebut meja pertama, disusun dari kiri ke kanan dan atas ke bawah.
Kemudian pada meja kedua tempat meletakkan kartu yang diurutkan.
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.
Contoh :
Jika sudah terurut 3,6,9, dan selanjutnya belum terurut 5,7,2,....
5 akan disisipkan di antara 3 dan 6, sehingga menjadi 3,5,6,9.
7 akan disisipkan di antara 6 dan 9, sehingga menjadi 3,5,6,7,9.
2 akan disisipkan sebelum 3, sehingga menjadi 2,3,5,6,7,9.
METODE DEVIDE AND CONQUER
Devide and Qonquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah/problem menjadi beberapa sub-masalah/sub- problem yang lebih kecil, kemudian menyhelesaikan masing-masing sub- masalah secara independen dan akhirnya menggabungkan solusi masing- masing sub masalah sehingga menjadi solusi masalah semula.
Masalah
|
sub masalah 1
|
Sub solusi 1
|
Solusi masalah
|
Sub masalah 2
|
sub solusi 2
| ||
Sub-masalah 3
|
Sub solusi 3
|
Algortima devide and conquer menawarkan penyederhanaan masalah dengan pendekatan 3 langkah masalah:
pembagian masalah menjadi sekecil mungkin
penyelesaian masalah-masalah yang dikecilkan
penggabungan solusi untuk mendapatkan solusi optimal secara keseluruhan.
Tipe algoritma yang mengimplementasikan/kategori D&C antara lain merge sort
4. Metode Merge Sort
Merge sort adalah algoritma yang digunakan untuk menyusun list yang diberikan dengan cara membagi list yang diberikan menjadi dua bagian yang lebih kecil. Kedua list yang baru ini kemudian akan disusun secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk list baru yang merupakan hasil penggabungan dua buah list sebelumnya
Konsep :
1). Array yang belum terurut, dibagi menjadi separuh Proses diulang terus sampai ditemukan bagian terkecil
2). Hasil dari setiap proses digabungkan :
Membandingkan elemen pertama dari setiap bagian
|
Hapus
| |
elemen terkecil dan letakan pada hasil
Ulangi semua proses sampai semua elemen terurut
|
3 9 4 1 5 2
List diatas dibagi menjadi dua bagian:
list 1: | list 2: 3 9 4 | 1 5 2
Kedua list yang baru disusun sendiri-sendiri menjadi:
list 1: | list 2: 3 4 9 | 1 2 5
Setelah itu dubentuk list baru yang merupakan gabungan kedua list tadi:
Listbaru:
| ||
1 list 1:
|
|
|
list2:
|
3 4 9
|
|
|
2 5
|
List baru: 1 2
list 1: | list 2:
3 4 9 | 5
List baru: 1 2 3
list 1: | list 2:
4 9 | 5
Listbaru:
|
1
|
2
|
3
|
4
| ||
list1:
|
|
|
list 2: 9
|
|
|
5
| ||
List baru: 1 2 3 4 5
list 1: | list 2: 9 | kosong
List
|
baru:
|
1 2
|
3 4 5 9
| ||
list
|
1:
|
|
|
list 2: kosong
|
|
|
kosong
|
Dan akhirnya akan didapat list yang sudah tersusun:
List: 1 2 3 4 5 9
BAB 9
Algoritma Searching
Pengertian Algoritma Searching
Searching
merupakan proses dasar dalam pengolahan data. Yaitu untuk menemukan
nilai tertentu dalam sekumpulan data yang bertipe sama. Algoritma
searching dijelaskan secara luas sebagai algoritma yang menerima masukan
berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah
tersebut. Algoritma searching menerima sebuah argument kunci dan dengan
langkahlangkah tertentu akan mencari rekaman dengan kunci tersebut.
Setelah melakukan proses pencarian, akan diperoleh salah satu dari dua
kemungkinan, yaitu data yang dicari ditemukan atau tidak ditemukan.
Macam-macam Algoritma Searching
1. Pencarian Beruntun (Sequential Search)
Konsep
a)
Membandingkan setiap elemen larik satu per satu secara urut (beruntun),
mulai dari elemen pertama sampai dengan elemen yang terakhir sampai
data ditemukan atau tidak ditemukan.
b) Proses pencarian akan dihentikan jika data yang dicari sudah ditemukan.
c) Merupakan metode yang paling sederhana
d) Kelemahan pada kasus ini adalah, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
Contoh
Pemcarian angka
#include <iostream>
using namespace std;
int main()
{
cout<<"====== PROGRAM SEQUENTIAL SEARCH ========"<<endl<<endl;
int n,bil_cari,Data[100];
int i,ketemu;
cout<<" Inputan Jumlah Data Dalam Array : ";
cin>>n;
cout<<endl;
for(int c=0; c<n; c++)
{
cout<<" Elemen Data Array Ke - "<<c<<" = "; cin>>Data[c];
}
i=0;
cout<<" \n\n Inputkan Bilangan Yang Dicari = "; cin>>bil_cari; ketemu = 0;
while((i<n) && (ketemu==0))
{
if(Data[i] == bil_cari)
{
ketemu=1;
cout<<" \n Pencarian sequential "<<bil_cari<<" Ada Pada Indeks ke - " <<i;
}
else
i=i+1;
}
if(ketemu == 1)
cout<<"\n Data ditemukan!!! "<<endl;
else
cout<<"\n Data tidak ditemukan!!!"<<endl;
return 0;
}
dan setelah di run akan tampil seperti di bawah\
Dari
program di atas, terlihat bahwa dilakukan perulangan untuk mengakses
semua elemen array data satu per satu berdasarkan indeksnya.
a)
Program menggunakan sebuah variable flag yang berguna untuk menandai
ada atau tidaknya data yang dicari dalam array data. Hanya bernilai 1
atau 0.
b) Flag pertama kali diinisialisasi dengan nilai 0.
c) Jika ditemukan, maka flag akan diset menjadi 1, jika tidak ada maka flag akan tetap bernilai 0.
d) Semua elemen array data akan dibandingkan satu per satu dengan data yang dicari dan diinputkan oleh user.
2. Pencarian Bagi Dua (Binary Search)
Konsep
(a) Merupakan metode pencarian pada data terurut yang paling efisien.
(b) Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat.
(c)
Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode
ini. data yang disimpan didalam larik harus sudah terurut.
Algoritma
Algoritma pencarian biner dapat dituliskan sebagai berikut:
(a) L ← 0
(b) R ← N – 1
(c) Ketemu ← false
(d) Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8
(e) m ← (L + R) / 2
(f) jika (Data[m]) maka ketemu ← true
(g) jika (x < Data[m]) maka R ← m – 1
(h) jika (x > Data[m]) maka L ← m + 1
(i) jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak maka data tidak ditemukan.
Contoh
#include <iostream>
using namespace std;
int main()
{
int arr[100],awal,tengah,akhir,i,n,num;
cout << "\nMasukkan Jumlah data : ";
cin >> n;
cout << "\nMasukkan data yang sudah terurut : " << endl;
for (i=0;i<n;i++) {
cout << "Masukkan data ke- "<< i+1 << " : ";
cin >> arr[i];
cout << endl;
}
//inisialiasi nilai awal dan akhir
awal = 0;
akhir = n-1;
cout << "\nMasukkan angka yang dicari : ";
cin >> num;
return 0;
while (awal <= akhir) {
//menentukan tengah
tengah = (awal+akhir)/2;
//jika nilai ditemukan di tengah,maka tampilkan posisi dan keluar
if(arr[tengah] == num) {
cout << "\nAngka ditemukan pada posisi : " << (tengah+1);
return(0);
} else if (num > arr[tengah]) {
awal=tengah+1;
} else if (num < arr[tengah]) {
akhir=tengah-1;
}
}
cout << "Angka tidak ditemukan!";
return 0;
}
#include <iostream>
using namespace std;
int main()
{
int arr[100],awal,tengah,akhir,i,n,num;
cout << "\nMasukkan Jumlah data : ";
cin >> n;
cout << "\nMasukkan data yang sudah terurut : " << endl;
for (i=0;i<n;i++) {
cout << "Masukkan data ke- "<< i+1 << " : ";
cin >> arr[i];
cout << endl;
}
//inisialiasi nilai awal dan akhir
awal = 0;
akhir = n-1;
cout << "\nMasukkan angka yang dicari : ";
cin >> num;
return 0;
while (awal <= akhir) {
//menentukan tengah
tengah = (awal+akhir)/2;
//jika nilai ditemukan di tengah,maka tampilkan posisi dan keluar
if(arr[tengah] == num) {
cout << "\nAngka ditemukan pada posisi : " << (tengah+1);
return(0);
} else if (num > arr[tengah]) {
awal=tengah+1;
} else if (num < arr[tengah]) {
akhir=tengah-1;
}
}
cout << "Angka tidak ditemukan!";
return 0;
}
