PENGERTIAN GARAF
Graf adalah
salah satu jenis Struktur data yang terdiri dari titik (vertex) dan garis
(edge), dimana dalam tersebut, vertex-vertex yang
dihubungkan oleh edge, hingga menjadi suatu kesatuan yang
disebut graf.
Algoritma Djikstra
A. Definisi Algoritma Djikstra
Algoritma Dijkstra, (penemunya
adalah seorang ilmuwan komputer, Edsger Dijkstra),
adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak
terpendek untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai
positif.
B. Tujuan Algoritma Dijkstra
1. Tujuan Algoritma Dijkstra yaitu untuk
menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik
lainnya.
2. Kelemahan algoritma ini adalah semakin
banyak titik akan semakin memakan waktu proses.
3. Jumlah titik menentukan tingkat
efektifitas dari algoritma djikstra.
C. Urutan Logika Algoritma Dijkstra
1. Beri nilai bobot (jarak) untuk setiap
titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga
terhadap node lain (yang belum terisi).
2. Set semua node “Belum terjamah” dan set
node awal sebagai “Node keberangkatan”.
3. Dari node keberangkatan, pertimbangkan
node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.
4. Setelah selesai mempertimbangkan setiap
jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node
terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan
adalah jarak terakhir dan yang paling minimal bobotnya.
5. Set “Node belum terjamah” dengan jarak
terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan
lanjutkan dengan kembali ke step 3.
Contoh :
Titik mengambarkan lokasi dan garis menggambarkan jalan,
maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot
terkecil dari setiap titik.
Pertama tentukan titik yang akan menjadi nomor kode (node)
awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu,
lalu akan dilakukan pengembangan pencarian dari satu titik ke titik selanjutnya
(tahap demi tahap).
Node awal 1, Node tujuan 5. Setiap edge yang terhubung antar
node telah diberi nilai
SORTING
(PENGURUTAN)
Sorting secara
umum bisa didefinisikan sebagai suatu proses untuk menyusun kembali himpunan
obyek menggunakan aturan tertentu. Sorting merupakan satu dari banyak pekerjaan
komputer yang dilakukan, yang diteliti secara luas, dan memiliki banyak
algoritma yang berbeda yang dibangun. Sorting (mengurutkan) data memiliki
dampak yang sangat penting dalam pencarian. Data yang tidak terurut harus
dicari secara normal menggunakan suatu pembacaan sekuensial (sequential scan)
dari semua data. Data yang telah terurut membiarkan dirinya untuk dicari
menggunakan teknik pencarian yang sederhana.
Secara umum ada 2
jenis sorting, yaitu secara Ascending (terurut naik) dan Descending (terurut
turun). Dalam hal pengurutan data yang bertipe string atau char, nilai data
dikatakan lebih kecil atau lebih besar dari yang lain didasarkan pada urutan
relatif (collating sequence) seperti yang dinyatakan dalam tabel ASCII. Tujuan
pengurutan data adalah untuk mempermudah pencarian data. Pengurutan data menjadi
sesuatu yang penting dalam ilmu komputer karena waktu yang diperlukan untuk
melakukan proses pengurutan perlu dipertimbangkan.
Data yang akan
diurutkan tentu sangat bervariasi baik dalam hal banyak data maupun jenis
datanya. Sayangnya, tidak ada satu algoritma yang terbaik untuk setiap situasi
yang kita hadapi. Bahkan cukup sulit untuk menentukan algoritma mana yang
paling baik untuk situasi tertentu karena ada beberapa faktor yang mempengaruhi
efektifitas algoritma pengurutan. Beberapa faktor yang berpengaruh pada
efektifitas suatu algoritma pengurutan antara lain : banyak data yang akan
diurutkan, kapasitas pengingat apakah mampu menyimpan semua data yang dimiliki,
dan tempat penyimpanan data.
Pengurutan
Internal (Internal Sorting)
Algoritma Internal
Sorting seringkali mengklasifikasikan berdasarkan jumlah dari pekerjaan yang
diminta untuk mengurutkan urutan elemen. Banyaknya pekerjaan mengarah pada dua
operasi dasar dari sorting : membandingkan dua elemen dan memindahkan suatu
elemen dari satu tempat ke tempat lainnya. Teknik internal sorting yang utama
dibagi ke dalam 3 kategori dengan tanggung jawab ke pekerjaan yang dibutuhkan
untuk mengurutkan suatu urutan dari n elemen-simple sort, advanced sort dan
radix sort.
A. TEKNIK
PENGURUTAN SEDERHANA ( SIMPLE SORT
TECHNIQUES)
Selection Sort ( Metode
Seleksi )
Operasi dasar
dalam suatu selection sort adalah seleksi dari elemen yang terkecil (atau yang
terbesar) dari urutan suatu elemen. Gambar berikut akan menggambarkan proses
untuk suatu urutan.
Ascending
- Cek
seluruh elemen array, temukan nilai terkecil (1) dan tukarkan posisinya
dengan posisi nilai yang tersimpan pada posisi pertama dari array (3)
- Temukan
nilai terkecil kedua (2), dan tukarkan posisinya dengan nilai yang berada
pada posisi kedua (10)
.
- Dua
elemen biru pertama tidak akan berubah lagi sebab mereka sudah merupakan
nilai terkecil pertama dan kedua dalam array tsb.
- Sekarang,
ulangi dengan cara/proses “pilih dan tukar
Algoritma
|
Procedure
selectsort(var r:list; n: integer);
Var j, k,
small: integer;
Begin
If n >
1
Then
begin
For k := 1 to n
– 1 do
Begin
Small :=
k;
For j := k + 1
to n do
If r[j] <
r[small]
Then small :=
j;
Swap(r[k],
r[small])
End
End
End;
|
Logika dari
prosedur SelectSort adalah kekhususan dari algoritma pengurutan sederhana, yang
terdiri atas loop luar (outer loop) dan loop dalam (inner loop). Dalam prosedur
SelectSort masing-masing diimplementasikan menggunakan Pascal untuk
membangunnya. Inner loop dieksekusi mengikuti nomor waktu :
Outer loop
dieksekusi sebanyak n-1 kali. Masing-masing eksekusi dari inner loop memerlukan
satu perbandingan dan satu nomor yang tidak diketahui. Masing-masing eksekusi
dari outer loop memerlukan satu perubahan. Total usha yang dilakukan :
Perubahan = n – 1
Perbandingan = ½
n( n - 1 )
Yang perlu
diperhatikan bahwa usaha yang diperlukan, seperti yang diukur oleh perbandingan
dan perubahan, adalah pengurutan independen dari data yang diurutkan. Pada sisi
negatif, SelectSort memerlukan O(n2) perbandingan tidak perduli bagaimana
inisial data diurutkan. Sisi positifnya, ia tidak pernah memerlukan lebih dari
O(n) perpindahan. Inilah yang membuat SelectSort sebagai metode yang baik untuk
elemen yang besar (yang mahal untuk perpindahan) dengan pilihan pengurutan yang
pendek (mudah untuk dibandingkan).
Bubble Sort
Operasi dasar
dalam Exchange Sort adalah menukarkan sepasang elemen yang berdekatan. Metode
ini mudah dipahami dan diprogram, tetapi tidak efisien. Secara keseluruhan
proses pengurutan terdiri dari satu nomor yang melintasi data.
Masing-masing lintasan dimulai pada suatu akhir dari array dan bekerja ke akhir
yang lainnya. Masing-masing pasangan elemen yang keluar dari urutan ditukarkan.
Gambar berikut akan menggambarkan proses dari pengurutan secara ascending (dari
kecil ke besar ).
Proses pertama(1, 3, 7, 6, 5) menjadi (1, 3, 7, 6, 5)(1, 3,
7, 6, 5) menjadi (1, 3, 7, 6, 5)(1, 3, 7, 6, 5) menjadi (1, 3, 6, 7, 5)(1, 3,
6, 7, 5) menjadi (1, 3, 6, 5, 7)Proses kedua(1, 3, 6, 5, 7) menjadi (1, 3, 6,
5, 7)(1, 3, 6, 5, 7) menjadi (1, 3, 6, 5, 7)(1, 3, 6, 5, 7) menjadi (1, 3, 5,
6, 7)(1, 3, 5, 6, 7) menjadi (1, 3, 5, 6)
Lintasan pertama
memindahkan elemen terbesar ke posisi ke-n, membentuk list terurut pertama.
lintasan kedua hanya memikirkan n-1 elemen. Lintasan kedua memindahkan elemen
terbesar kedua ke posisi n – 1. Oleh karena itu lintasan ketiga hanya perlu
memperhatikan n – 2 elemen. Secara umum setelah i melintas elemen terbesar ke i
akan berada pada posisi terakhir, maka lintasan i + 1 hanya perlu memperhatikan
i – 1 elemen. Dalam metode ini elemen yang kecil berpindh secara pelan, atau
menggelembung, kearah atas. Oleh karena itu teknik pengurutan ini sering
disebut dengan buble sort.
Jika tidak ada
perubahan yang terjadi selama satu lintasan yang melintasi data maka data
diurutkan dan proses berhenti. Pengecekan dilakukan untuk melihat jika ada
suatu perubahan yang terjadi pada lintasan dengan menggunakan variable boolean
sorted. Pada awal setiap lintasan sorted diset ke true. Jika terjadi
suatu perubahan, kemudian sorted diset ke false (pada kenyatannya, sorted diset
ke false setiap suatu perubahan terjadi., tidak hanya pertama kali).
Algoritma
|
Procedure
exchangesort(var r: list; n: integer);
Var j, k,
small: integer;
Sorted:
boolean;
Begin
K := n; sorted
:= false;
While (k >
1) and (not sorted) do
Begin
Sorted :=
true;
For j := 1 to k
– 1 do
If r[j] >
r[j+1]
Then
begin
Swap(r[j],r[j +
1]);
Sorted :=
false
End;
K := k –
1
End;
End;
|
Dalam prosedur
exchangesort loop keluar diimplementasikan dengan satement while dalam Pascal,
dan loop ke dalam dengan statement for dalam Pascal. Loop kedalam dieksekusi
mengikuti nomor waktu :
dimana ksorted
adalah nomor dari eksekusi dari loop keluar sebelum disana ada lintasan selama
disana tidak ada perubahan. Loop kedalam memiliki satu perbandingan dan
beberapa kali perubahan. Performa terbaik yang terjadi ketika ksorted adalah 1.
Hal ini berarti tidak ada perubahan yang terjadi karena data asli telah
diurutkan. Nomor perbandingan digunakan oleh prosedur exchange sort untuk
menentukan :
Performa terburuk
yang terjadi ketika ksorted adalah n – 1. loop dalam kemudian dieksekusi
mengikuti nomor waktu : Ketika menterjemahkan eksekusi loop kedalam
pertukaran dan perbandingan, maka akan diperoleh : · worst case (kejadian terburuk)
pertukaran = ½ n(n-1) perbandingan = ½ n(n-1) ·
sorted data (data terurut) pertukaran = 0 perbandingan = n - 1 Suatu
ExchangeSort memiliki dua kekurangan. Pertama, inner loop mengandung
suatu pertukaran yang memerlukan tiga perubahan. Dalam SelectSort tidak ada
perpindahan dalam inner loop. Kedua, ketika suatu elemen dipindahkan, ia selalu
dipindahkan ke posisi terdekat. Dalam SelectSort suatu elemen mungkin berpindah
ke jarang yang jauh dan selalu berpindah ke posisi yang diurutkan. Jadi
ExchangeSort algoritma pengurutan terlam.
Insertion Sort ( Metode Penyisipan Langsung )
Operasi dasar
dalam insertion sort adalah penyisipan suatu elemen tunggal kedalam urutan
elemen yang telah diurutkan sehingga hasil dari urutan masih tetap terurut.
Gambar tersebut mengilutrasikan proses yang terjadi pada 5 elemen, dengan
setiap elemennya merupakan bilangann integer. Data yang digunakan untuk
input merupakan array 5 bilangan integer (gambar (a)). Ketika elemen ke lima,
235, diperhatikan, … Dalam transisi dari gambar (a) ke gambar (b) terjadi
penysisipan 45 ke dalam daftar elemen yang telah diurutkan. Sealama 45 kurang
dari 235, penyisipan 45 merupakan puncak dari daftar. Sebagaimana ditampilkan
dalam gambar (b), segmen yang terurutkan mempunyai panjang dua.
Transisi dari
gambar (b) ke gambar (c) diselesaikan dengan memasikkan 182 ke dalam daftar
elemen yang telah diurutkan. Selama 182 terletak diantara 35 dan 235, 182
disisipkan diantara 45 dan 235 dengan memindahkan 45 ke atas yang menciptakan
suatu ruangan. Daftar subset yang terurut tersebut sekarang mempunyai panjang
tiga. Gambar (d) diperoleh dengan menyisipkan 205 ke dalam daftar elemen
yang telah diurutkan, dilakukan dengan memindahkan 45 dan 182 naik untuk
menjadikan ruangan. Terakhir, gambar (e) diperoleh dengan memasukkan 390 ke
dalam daftar elemen (dengan panjang empat) yang telah terurut.
Gambar
mengilustrasikan prosedur yang terdapat pada algoritma insertion sort.
Algoritma melakukan penyisipan dengan melakukan dibawah elemen untuk
disisipkan. Setiap elemen yang kecil dibandingankan dengan elemen yang akan
disispkan posisinya dinaikkan satu tingkat. Selama elemen yang ditemukan lebih
besar dibandingkan dengan elemen yang akan disisipkan, pencarian akan
dihentikan dan penyisipan terjadi didepan elemen yang besar.
contoh:
contoh lain :
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 4
(last element of the array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11
before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in
A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements
from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11
to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13
Algoritma
|
Procedure
insertsort(var r; list; n: integer);
Var j, k, save:
integer;
Begin
For k := n – 1
downto 1 do
Begin
j := k + 1;save
:= r[k];
r[n + 1] :=
save;
while save >
r[j] do
begin
r[j – 1] := r
[j];
j := j +
1;
end;
r[j – 1] :=
save
end;
end;
|
Perulangan
sebelah luar dari prosedur insertsort selalu dieksekusi sebanyak n-1 kali.
Banyakanya ekseskusi yang terjadi pada perulangan sebelah dalam tergantung pada
nilai k dan urutan data. Dalam kasus data yang telah diurutkan, perulangan sisi
dalam tidak pernah dieksekusi. Dalam kasus terburuk akan dieksekusi sebanyak :
Dengan memberikan
semua inisial pengurutan data yang mungkin terjadi, rata-rata perulangan dalam
yang terjadi dieksekusi setengah dari kasus terburuk. Hal tersebut terjadi
karena perulangan sisi dalam pada prosedur insertsort memeriksa daftar yang
telah terurut dicari elemen pertama yang lebih besar dari satu yang disipkan.
Rata-rata perintah tersebut menguji setengah dari daftar yang ada.
Insertsort perulangan sisi dalam membutuhkan usaha yang lebih besar
dibandingkan dengan selectsort perulangan sisi dalam – satu perpindahan melawan
tidak ada perpindahan sama sekali. Tapi membutuhkan usaha yang lebih kecil
dibandingkan dengan exchangesort.
Untuk elemen yang
pendek, pemindahan dalam perulangan sisi dalam lebih dari diseimbangkan dengan
seringkali hanya mengeksekusi setengah perulangan sisi dalam, dan insertosrt
memberikan kinerja yang lebih baik. Karena overhead yang rendaj dan
kinerja yang cukup tinggi untuk dtaa terurut, insertsort akan dikombinasikan
dengan quicksort untuk menghasilkan algoritma pengurutan internal serbaguna yang
terbaik untuk saat ini. Sejauh ini, pengurutan data yang disimpan dalam doubly
linked list tidak dibahas, bab selanjutnya membahas tentang implementasi
insertion sort pada linked list.
sumber :
http://yogapratama1205.blogspot.com/2015/06/penjelasan-tentang-sorting-selection.html
PENGERTIAN BINARY SEARCH
Binary search adalah
metode pencarian suatu data atau elemen di dalam suatu array dengan kondisi data
dalam keadaan terurut. Proses pencarian binary search hanya dapat dilakukan
pada sekumpulan data yang sudah diurutkan terlebih dahulu. Prinsip dari binary
search terhadap N elemen dapat dijelaskan seperti berikut:
1. Tentukan posisi awal = 0 dan posisi
akhir = N-1.
2. Hitung posisi tengah = (posisi awal
+ posisi akhir)/2.
3. Bandingkan data yang dicari dengan
elemen posisi tengah.
4. Jika sama maka catat posisi dan
cetak kemudian berhenti.
5. Jika lebih besar maka akan dilakukan
pencarian kembali kebagian kanan dengan posisi awal =
posisi tengah +1 dan
posisi akhir tetap kemudian ulangi mulai poin 2.
6. Jika lebih kecil maka akan di
lakukan pencarian kembali ke bagian kiri dengan nilai posisi awal
tetap dan nilai posisi akhir =
posisi tengah-1 kemudian ulangi mulai poin 2.
Proses pencarian dilakukan untuk mengetahui
apakah data yang dicari terdapat pada sekumpulan data yang ada. Selain untuk
mengetahui keberadaan data, informasi yang lain yang bisa didapat adalah letak
dari data tersebut. Adapun jenis pencarian yaitu:
Pencarian Bagi Dua (Binary Search)
Pencarian Beruntun (Sequential Search)
Binary Search
Binary search atau pencarian bagi dua adalah salah satu metode pencarian
data salah satu nya Linear Search yang bisa kalian lihat sendiri pada
link disamping ,Binary search mempunyai kelebihan dan kekurangan bila
dibandingkan dengan Linear search , salahn satu nya binary search pencarian nya
lebih cepat tapi agak sedikit susah untuk di mengerti bila dibandingkan dengan
Linear Search yang lumayan simpel .
Sebenarnya binary Search ini sering
kita terapkan pada kehidupan kita sehari - hari . salah satu contoh nya
yaitu , Saat kita mencari kata di kamus maka kita akan membuka buku itu menjadi
dua bagian , dan membuka nya lagi menjadi dua bagian dan seterus nya sampai
ketemu , bagaimana jika kalian ingin mencari suatu kata di kamus dengan
menggunakan metode linear search ? tentu akan sangat lama ,karena linear search
konsep pencarian dengan beruntun dari halaman pertama sampai terakhir dan
sebalik nya secara terurut , jadi tidak mungkin mencari nya dengan linear
search .
Jadi binary search ini sangat dianjurkan untuk digunakan saat mencari data yang
data nya banyak .
contoh program:
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;
int main()
{
//Pendeklarassian variabel
int nilai[20];
int i,j,n;
int temp, awal, akhir, tengah, bilangan;
//Proses penginputan data
cout<<"Banyak Bilangan:
";
cin>>n;
for(i=0;i<n;i++)
{
cout<<"Elemen ke-"<<i<<" =";
cin>>nilai[i];
}
cout<<"\n\nElemen sebelum
diurut = ";
for(i=0;i<n;i++)
{
cout<<setw(3)<<nilai[i];
}
//Proses pengurutan data
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(nilai[i]>nilai[j])
{
temp = nilai[i];
nilai[i]=nilai[j];
nilai[j]=temp;
}
}
}
cout<<"\nElemen Setelah Di
Urut = ";
for(i=0;i<n;i++)
{
cout<<setw(3)<<nilai[i];
}
cout<<"\nIndeks
Elemen =";
for(i=0;i<n;i++)
{
cout<<setw(3)<<i;
}
cout<<"\n\nMasukan data Yang
Akan Anda Cari: ";
cin>>bilangan;
//Proses pencarian data
awal = 0;
akhir =n-1;
do
{
tengah =
(akhir+awal)/2;
if(bilangan <
nilai[tengah])
{
akhir = tengah -1;
}
else
{
awal = tengah +1;
}
}
while((akhir>=awal)&&(nilai[tengah] !=bilangan));
{
if
(nilai[tengah]==bilangan)
{
cout<<"\nData "<<bilangan<<" Ada dalam
Array";
cout<<"Pada posisi "<<tengah;
}
else
{
cout<<"\nData "<<bilangan<<" tidak ada dalam
array\n";
}
}
getch();
return 0;
