MATA KULIAH ALGORITMA DAN STRUKTUR DATA

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 program

memberikan   niai   awal   pada   suatu variabel atau counter

menunjukkan  pengolahan  aritmatika dan pemindahan data

menunjukkan     proses     input     atau output

untuk mewakili operasi perbandingan logika

proses    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 “

Dari algoritma diatas dipilih algortima pertama. Proses perulangan akan dilakukan yaitu :

mencetak bilangan dari 1 -10

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

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.

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:

List baru:
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

List baru:	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;
}