TUGAS ALGORITMA DAN STRUKTUR DATA 2

METODE SEARCHING (Sequential Search & Binary Search)

Searching adalah metode pencarian informasi dalam suatu aplikasi, dengan suatu kunci( key ). Pencarian
diperlukan untuk mencari informasi khusus dari table pada saat lokasi
yang pasti dari informasi tersebut sebelumnya tidak diketahui.
Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok
data yang tersimpan secara terorganisasi, kelompok data tersebut kita
sebut table.
Pada
metode searching (pencarian) ada 2 teknik yang digunakan yaitu :
Pencarian sekuensial (sequential search) dan Pencarian biner (Binary
search).

1. Pencarian sekuensial (sequential search)
Pencarian
sekuensial (sequential search) atau sering disebut pencarian linier
menggunakan prinsip sebagai berikut : data yang ada di bandingkan satu
persatu secara berurutan dengan yang dicari.
Pada
dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai
dengan jumlah data. Pada setiap perulangan , di bandingkan data ke-i
dengan yang dicari. Apabila sama , berarti data telah ditemukan .
Sebaliknya apabila sampai akhir pengulangan , tidak ada yang sama
berarti data tidak ada.
a. Sekuensial versi berdampingan dengan sintak C:
Contoh listing fungsi dalam bahasa C++ :
Int SequensialSearch(List_type list, Key_type target)
{ int location; // penempatan data
for (location=0;location
if (EQ(list.entry[location].key,target))
return location;
return –1
b. Sekuensial versi berangkai dengan sintak C:
Node_type* SequentialSearch (List_type list, Key_type target)
{ Node_type* location;
for (location=list.head;location!=NULL;locatioan->next)
if(EQ(location->info.key,target))
return location;
return NULL
}

Pengimplementasian sintak sekuensial search pada bahasa C :

#include
#include
void main()
{
clrscr();
int data[8] = {3,9,7,-3,11,5,2,18};
int cari,index;
int ketemu=0;
cout<<"Inputkan data yang ingin di cari = ";
cin>>cari;
for(int i=0;i<8;i++)
{
if(data == cari)
{
ketemu=1;
index=1;
break;
}
}
if(ketemu == 1)
{
cout<<"Data tersedia!"<
cout<<"Data Terletak di index ke - "<
}
else cout<<"Data tidak tersedia!"<
getch();
}

2. Pencarian Biner (Binary Search)
Salah
satu syarat pencarian biner (binary search) dapat dilakukan adalah data
sudah dalam keadaan terurut. Dengan kata lain, apabila data belum dalam
keadaan terurut , pencarian biner tidak dapat dilakukan . Dalam
kehidupan sehari-hari, sebenarnya kita juga serig menggunakan pencarian
biner. Misalnya saat kita ingin mencari suatu kata dalam kamus.
Langkah dalam pencarian biner adalah :
1. Mula-mula diambil dari posisi awal=1 dan posisi akhir = n
2. Kemudian kita cari posisi data tengah dengan rumus posisi tengah = (posisi awal + posisi akhir ) div 2
3. Kemudian data yang di cari dibandingkan dengan data tengah
a. Jika sama, data ditemukan, Proses selesai
b. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1,
c. Jika lebih besar , proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.
4. Ulangi langkah kedua hingga data ditemukan , atau tidak ditemukan.
5. Pencarian
biner ini akan berakhir jika data ditemukan posisi awal lebih besar
dari pada posisi akhir. Jika posisi awal sudah lebih besar dari posisis
akhir berarti data tidak diketemukan.

Contoh sintak Binary search pada bahasa C:

#include
#include

int data[10] = {1,4,6,8,18,23,35,49,60,75};

int binary_search(int cari)
{
int l,r,m;
int n = 10;
l = 0;
r = n-1;
int ketemu = 0;
while(l<=r && ketemu==0)
{
m = (l+r)/2;
if ( data[m] == cari )
ketemu = 1;
else
if (cari <>
r = m-1;
else l = m+1;
}
if(ketemu == 1) return 1; else return 0;
}

void main()
{
clrscr();
int cari,hasil;
cout<<"Masukan data yang ingin dicari = ";
cin>>cari;
hasil = binary_search(cari);
if(hasil == 1)
{
cout<<"Data tersedia!"<
}
else
if(hasil == 0)
cout<<"Data tidak tersedia!"<
getch();
}

· Pencarian Sekuensial :
a. Kelebihannya :
- Relatif lebih cepat dan efisien untuk data yang terbatas
- Algoritma sederhana
b. Kekuranganya :
- Kurang cepat untuk data dalam jumlah besar
- Beban komputasi cenderung lebih besar
· Pencarian Biner :
a. Kelebihannya :
- Untuk data dalam jumlah besar, waktu searching lebih cepat
- Beban komputasi lebih kecil
b. Kekuranganya :
- Data harus sudah di-sorting lebih dulu ( dalam keadaan terurut )
- Algoritma lebih rumit, tidak baik untuk data berangkai
Tinjauan Materi :
1. Antony, Pranata, 2000, [i]Algoritma dan Pemrograman, J&J Learning, Yogyakarta. 2.
http://74.125.153.132/search?q=cache:k-qZ0Kank5AJ:mti.ugm.ac.id/~yudhistira/ResourceMTI/Tutorial/Yudhistira/Modul%25202.doc+searching+(sequential-binary+search)&cd=10&hl=id&ct=clnk&gl=id


Sorting

Pengimplementasian metode Sorting (Algoritma & Struktur data) pada bahasa C

Sorting
/ pengurutan biasanya dilakukan untuk tujuan mempermudah pencarian.
Pengurutan data baik dari segi ascending (dari nilai terkecil ke
terbesar) atau descending (dari nilai terbesar ke terkeci).Ketika akan
melakukan sortir di computer , maka hal-hal yang akan dipertimbangkan
,meliputi :
1. Perlu tidaknya data disortir
2. Besarnya atau banyaknya data yang akan disortir
3. Kemampuan atau kapasitas computer atau media penyimpanan data
4. Metode sortir
Pada garis besarnya, ada tiga teknik sortir :
1. Insertion sort (sortir penyisipan)
2. Selection sort (sortit pemilihan)
3. Exchange short (sortir penukaran)
Teknik
sortir sangat erat kaitannya dengan proses perbandingan dan penukaran
tempat antarelemen data. Kita tidak dapat menentukan dengan pasti ,
mana dari ketiga teknik sortir tersebut yang merupakan teknik terbaik
(melakukan perbandingan dan penukaran tempat antarelemen dan yang
paling sedikit). Banyaknya proses perbandingan dan penukaran tempat
antar elemen data tersebut juga terkait dengan susunan elemen – elemen
datanya.
Sehingga , kecepatan dalam melakukan sortir juga ditentukan
atas tiga kondisi susunan elemen-elemen datanya. Waktu terbaik akan
diperoleh ketika susunan elemen datanya sudah sama dengan susunan yang
diinginkan melalui sortirnya. Waktu terburuk akan didapatkan ketika
susunan elemen – elemen datanya terbalik dari susunan yang dikehendaki
sortirnya. Waktu rata-rata diperoleh dengan memperhitungkan berbagai
susunan bentuk elemen-elemen datanya.
1. Insertion sort
Teknik
ini adalah dengan membandingkan elemen ke n (n mulai dari 2 hingga
elemen terakhir) dengan elemen – elemen sebelumnya. Bila elemen yang
dibandingkan bernilai lebih kecil , maka tukar posisinya.
Contoh : 8,3,7,4
Pada
langkah pertama, elemen kedua akan dibandingkan dengan elemen pertama,
3 dibandingkan dengan 8 , karena 3 lebih kecil dari 8, maka kedua
elemen tersebut saling ditukar tempatnya yang menghasilkan urutan
3,8,7,4 (dua elemen pertama sudah diurut). Pada langkah kedua , elemen
ketiga akan dibandingkan dengan 8 , terjadi penukaran tempat yang
menghasilkan urutan 3,7,8,4. Selanjutnya 7 tersebut dibandingkan dengan
elemen pertama, yaitu 3. Tidak terjadi penukaran tempat (3 elemen
pertama sudah diurut).
Pada langkah ketiga , elemen keempat yaitu 4
dibandingkan dengan elemen ketiga. Angka 4 lebih kecil dari 8, terjadi
penukaran tempat, hasil sementara adalah 3,7,4,8. Angka 4 tadi
dibandingkan dengan elemen kedua,4 lebih kecil dari 7, terjadi
penukaran tempat, hasil sementara adalah 3,4,7,8. Selanjutnya angka 4
tadi dibandingkan dengan elemen pertama, yaitu 3. Karena 4 lebih besar
dari 3, maka tidak terjadi penukaran tempat lagi (empat elemen pertama
sudah urut=hasil akhir).
Sub-sub langkahnya ketiganya : 3,7,8,4 (awal) -> 4 dibandingkan 8, ditukar
hasilnya : 3,7,4,8 -> 4 banding 7, tukar,
hasilnya : 3,4,7,8 -> 4 banding 3,tetap
hasilnya : 3,4,7,8 (akhir)
Sintak Implementasi insertion sort dalam bhs C adalah sbb:
void insertionsort(int arr[]) {
int i,j;
for (i = 1; i <>
int temp = arr[i];
int pos = i;
for (j = i; j > 0; j--) {
if (temp <>
arr[j] = arr[j-1];
pos--;
}
}
arr[pos]=temp;
}
}
void insertion_sort()
{
int temp, i, j;
for (i=1; i
{
temp = data[i];
j = i-1;
while (data[j] > temp && j>=0)
{
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
cout<<"insertion
sort selesai!"< } 2. Selection sort Teknik ini adalah mencari nilai
elemen terkecil kemudian letakkan dan tukar dengan posisi n (n mulai
dari 1 hingga elemen terakhir -1). Contoh : 8,3,7,4 Pada langkah
pertama, hasil sortirnya 3, 8,7,4 (mulai dari elemen pertama, elemen
terkecil = 3, letakkan dan tukarkan dengan elemen pertama). Pada
langkah kedua , hasil sortirnya 3,4,7,8 (mulai dari elemen kedua,
elemen terkecil = 4, letakkan dan tukarkan dengan elemen kedua). Pada
langkah ketiga , hasil sortirnya 3,4,7,8 (mulai dari elemen ketiga,
elemen terkecil =7, letakkan dan tukarkan dengan elemen ketiga,
hasilnya ternyata tetap). Sintak Implementasi selection sort dalam bhs
C adalah sbb: void selection_sort() { int pos, i, j; for (i=0; i { pos
= i; for (j=i+1; j { if (data[j] < pos =" j; } if (pos != i)
tukar(pos,i); } cout<<" i =" 0;">
int min = arr[i];
int pos = i;
for (j = i; j <>
/* Cari nilai yang terkecil */
if (arr[j] <>
min = arr[j];
pos = j;
}
}
/* Tukar nilai terkecil ke arr[i] jika pos tdk sama i */
if(i!=pos) {
int temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp;
}
}
}

3. Exchange sort
Contoh
sortir umum yang menggambarkan exchange sort adalah bubble sort.
Algoritma dari teknik ini adalah dengan melakukan proses perbandingan
sebanyaknya n elemen dimulai dari n=1 (selanjutnya disebut mulai=1).
Bandingkan seluruh elemen diawali dari elemen sebelah kanan hingga ke
n. Bila elemen tersebut < 1="n." i="0;" j="(i+1);"> data[j])
tukar(i,j);
}
}
cout<<"Exchange sort selesai!"< } Exchange sort->Bubble sort pada bahasa C :
void bubble_sort()
{
For (int i=1;i=i;j–)
{
If (data[j] < temp =" data[a];">
data[j-1]) //data descending

Tinjauan Materi :
1. Struktur Data 2, Author: Taufik Fuadi Abidin, M.Tech Ph.D
2. Bambang,Wahyudi,2003,PengantarStrukturDataDan Algoritma,Andi,Yogyakarta.
3. http://genduet.wordpress.com/2009/03/19/bubble-sort/

program sorting C++

#include
#include
#include
#include
using namespace std;

const long int NUMBER=50000; // # of integers to compare quick vs. bubble

// bubblesort function
void bubbleSort(int sortme[NUMBER], long int limit); // sort
void fillArray(int array[NUMBER], long int limit); // create the array
void displayArray(int array[NUMBER], long int limit); // display the first n items
void swap(int& x, int& y); // swap x and y

// teacher supplied quicksort
void quickSort(int sortme[NUMBER], long int limit); // sort
int compare(const void *arg1, const void *arg2); // compare function

int main()
{
// create the variables
int numbers[NUMBER+1]; // array to sort
long int limit; // current number to compare
long int stime; // start time

// seed the random # generator
srand(time(0));

// compare bubble times vs. quicksort times from 10,000 to NUMBER, inc by 10,000
for (limit=10000; limit <= NUMBER; limit=limit+10000) {
cout.precision(4); cout.setf(ios::fixed); cout <<
stime="clock();" stime="clock();" i="1" j="i"> array[j]
// swap(array[i],array[j]
// endif
// next j
// next i
// end


}


// fill array - fills an array with random numbers
// input - array to fill
// - number of items
// output - the array filled with random numbers
void fillArray(int array[NUMBER], long int limit)
{
int i;

for (i=1; i
{
array[i]=rand();
}
}

// displayArray - displays the first n items in an array
// input - the array
// - the number of items to display
// output - displays the first n items in an array
void displayArray(int array[NUMBER], long int limit)
{
int i;

for (i=1; i
{
cout << array[i] << " ";
}
cout << "\n";
}

// swap - swaps items x and y
// input - 2 items
// output - the 2 items swapped
void swap(int& x, int& y)
{
int temp;

temp=x;
x=y;
y=temp;
}


// quickSort - Quick Sort
// input - a array to sort
// - # of items to sort
// output - the sorted array
// NOTE: - For now disreguard the messy pointers (*)
void quickSort(int sortme[NUMBER], long int limit)
{
qsort( (void *)sortme, (size_t)limit, sizeof(int *), compare);
}

// compare - Compares two items
// - negative if item1 is less than item2
// - positive if item1 is greather than item2
// - 0 if item1 == item2
int compare(const void *arg1, const void *arg2)
{
int value = (*(char**)arg1)-(*(char**)arg2);
return value;
}

Quick sort

Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga
berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini
hanya mengikuti langkah – langkah sebagai berikut :

1. Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r]
dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q]
dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan
elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada
elemen q merupakan salah satu bagian dari prosedur pemisahan.

2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif
Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi
pengurutan elemen – elemen pada sub-array


algoritma:

void quickSort(Object array[], int leftIdx, int rightIdx) {
int pivotIdx;
/* Kondisi Terminasi */
if (rightIdx > leftIdx) {
pivotIdx = partition(array, leftIdx, rightIdx);
quickSort(array, leftIdx, pivotIdx-1);
quickSort(array, pivotIdx+1, rightIdx);
}
}


contoh sorting dgn quicksort,dari kecil ke besar :
#include


void quicksort (int *a, int lo, int hi)

{

int m = lo, n = hi, h;

int x = a[(lo + hi) / 2];



do {

while (a[m] <> x) {

--n;

}

if (m <= n) {

h = a[m];

a[m] = a[n];

a[n] = h;

++m;

--n;

}

} while (m <= n);



if (lo < n) {

quicksort(a, lo, n);

}

if (m < hi) {

quicksort(a, m, hi);

}

}



#define MAX 5



int main (void)

{

int data[MAX] = { -10, 0, -21, 35, 567 };

int x;



puts("sebelum disortir");

for (x = 0; x < MAX; ++x) {

printf("%d ", data[x]);

}

puts("");

quicksort(data, 0, MAX - 1);

puts("setelah disortir");

for (x = 0; x < MAX; ++x) {

printf("%d ", data[x]);

}

puts("");



return(0);

}


Shell sort

• Mengurutkan data dengan cara
membandingkan suatu data dengan data
lain yang memiliki jarak tertentu sehingga
dibentuk sub-list, kemudian dilakukan
pertukaran jika diperlukan

contoh program


Algoritma Shell Sort

$size=6;
//data awal
$data = array(0,1,2,3,4,5);
$data[0]=5; $data[3]=7;
$data[1]=2; $data[4]=6;
$data[2]=4; $data[5]=3;
echo(" Jumlah Data : 6");
echo(" Data Awal :");
tampildata();echo"";
$increment=$size/2;
while($increment>0)
{
echo"Increment Ke-$increment :";
for($i=$increment;$i<$size;$i++)
{
$j = $i;
$temp = $data[$i];
while(($j>=$increment)&&($data[$j-$increment]>$temp))
{
$data[$j]=$data[$j-$increment];
$j=$j-$increment;
}
$data[$j]=$temp;
echo"";tampildata();echo"";
}
if ($increment == 2)
$increment = 1;
else
$increment = round($increment/2.2);
}
echo"Hasil Akhir : ";
tampildata();echo"";
//fungsi menampilkan data
function tampildata()
{
global $data;
for($i=0;$i<=5;$i++)
{
echo"$data[$i] ";
}
}
//=======================
?>


Buble sort

Cara pengurutan data atau file dengan
cara saling menukar tempat dalam urutan, mirip dengan gelembung dalam
air. Metode ini adalah cara terbaik untuk mengurutkan data/file dengan
jumlah sedikit. Untuk file yang lebih besar terdapat metode lainnya.

Contoh Program :
Program Penggunaan_Array_Untuk_Sortir_Buble_Sort;
Uses Crt;
Var
nil1 : Array[1..100] of Integer;
n,i,j,dum : Integer;
Begin
ClrScr;
Write('mau isi berapa data acak (integer) ='); readln(n);
For i := 1 to n Do
Begin
Write('Data Ke ',i,':');Readln(nil1[i]);
End;
{* penyapuan proses}
for i:= 1 to n-1 do
begin
for j:= i to n do
begin
if nil1[j]
begin
dum:=nil1[j];
nil1[j]:=nil1[i];
nil1[i]:=dum;
end;
end;
end;
writeln;
writeln('Hasil Sortir');
for i := 1 to n do
write(nil1[i]:3);
readln;
end.


ASCII

ASCII (American Standard Code for
Information Interchange) dan EBCDIC (Extended Binary Coded Decimal
Interchange Code) merupakan cikal bakal dari set karakter lainnya.
ASCII merupakan set karakter yang paling umum digunakan hingga
sekarang. Set karakter ASCII terdiri dari 128 buah 1 yang masing-masing
memiliki lebar 7-bit atau tujuh angka 0 dan 1, dari 0000000 sampai
dengan karakter 111111. Mengapa 7-bit? Karena komputer pada awalnya
memiliki ukuran memori yang sangat terbatas, dan 128 karakter dianggap
memadai untuk menampung semua huruf Latin dengan tanda bacanya, dan
beberapa karakter kontrol.
ASCII telah dibakukan pada tahun oleh
ANSI (American National Standards Institute) menjadi standar ANSI
X3.4-1986. EBCDIC merupakan set karakter yang merupakan ciptaan dari
IBM. Salah satu penyebab IBM menggunakan set karakter di luar ASCII
sebagai standar pada komputer ciptaan IBM adalah karena EBCDIC lebih
mudah dikodekan pada punch card yang pada tahun 1960-an masih jamak
digunakan. Penggunaan EBCDIC pada mainframe IBM masih terbawa hingga
saat ini, walaupun punch card sudah tidak digunakan lagi.Seperti halnya
ASCII, EBCDIC juga terdiri dari 128 karakter yang masing-masing
berukuran 7-bit. Hampir semua karakter pada ASCII juga terdapat pada
set karakter EBCDIC. Kalau ASCII dan EBCDIC sudah mampu mengkodekan 128
karakter, lalu mengapa masih dianggap perlu untuk menciptakan set
karakter baru? Lebar set karakter yang cuma 128 karakter tidak
memungkinkan penulisan karakter-karakter di luar huruf Latin (basic
Latin), seperti misalnya huruf ü atau simbol-simbol matematika dalam
huruf Yunani. Maka lahirlah keluarga set karakter ISO-8859-x.

Tabel Karakter ASCII

Tabel
berikut berisi karakter-karakter ASCII . Dalam sistem operasi Windows
dan MS-DOS, pengguna dapat menggunakan karakter ASCII dengan menekan
tombol Alt+[nomor nilai ANSI (desimal)