1.Struktur Data dan Algoritma.
Algoritma adalah urutan langkah logis untuk memecahkan masalah. Dan Struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna.
2. Materi yang Dipelajari dalam Mata Kuliah Algoritma dan Struktur Data II, antara lain :
Array
Array adalah suatu struktur yang terdiri dari sejumlah elemen yang memiliki tipe data yang sama. Elemen-elemen array tersusun secara sekuensial dalam memori computer. Terdapat beberapa jenis array, yaitu : Array satu dimensi, array dua dimensi, tiga dimensi ataupun multi dimensi.
- Array Satu Dimensi
Array satu dimensi adalah kumpulan elemen-elemen identik yang tersusun dalam satu baris. Elemen-elemen tersebut memiliki tipe data yang sama, tapi isi dari elemen tersebut boleh berbeda.
Bentuk umumnya :
<tipe data>NamaArray[n] = {elemen0,elemen1,elemen2,....n}
n = jumlah elemen.
- Array Dua Dimensi
Array dua dimensi adalah array yang terdiri dari beberapa baris dan beberapa kolom elemen yang bertipe sama. Array dua dimensi sering digambarkan sebagai sebuah matriks.
Bentuk umum :
<tipe data>NamaArray[m][n];
Atau
<tipe data>NamaArray[m][n]={{a,b...z},{1,2,...n-1}
Pointer
Terdapat beberapa definisi Pointer, antara lain :
- Penunjuk
- Biasanya digunakan dalam mengakses elemen array
- Pengiriman argument pada fungsi(struct).
- Pengiriman array dan string pada fungsi.
- Manipulasi memory (alamat dimana data tersimpan).
- Untuk membuat Linked List.
Bentuk Umum :
<tipe data>namaVariabel;
Contoh :
Int*px;
Variabel px merupakan pointer. Tipe data int berarti alamat memori yang ditunjuk oleh px dimaksudkan untuk berisi data bertipe int.
Structure
Structure adalah kumpulan elemen-elemen data yang digabungkan menjadi satu kesatuan. Masing-masing elemen data tersebut dikenal dengan sebutan field. Field data tersebut dapat memiliki tipe data yang sama ataupun berbeda, tetapi tetap berada dalam satu kesatuan dan dapat diakses secara individual.
Bentuk umum :
Struct namastruct
{
<tipe data> field1;
<tipe data> field2;
<tipe data> field3;
};
Contoh :
Struct mahasiswa
{
char nim[12];
char nama[25];
char alamat[45];
float ipk;
};
Linked List
Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemenya terdiri dari dua bagian.
Bentuk umum :
Typedef struct telmlist
{
Infotype info;
Address next;
}elmtlist;
Infotype: sebuah tipe terdefinisi yang menyimpan onformasi sebuah elemen list.
Next : address dari elemen berikutnya.
Linked List dapat dibagi menjadi dua jenis,yaitu :
- Single Linked List, adalah susunan berupa untaian yang berisi sebuah variable pointer, dan bersifat satu arah.
Pembuatan single linked list menggunakan dua metode :
- LIFO (Last IN First Out), aplikasinya : Stack.
- FIFO (First IN First Out), aplikasinya : Queue.
- Double Linked List, adalah linked list yang berpointer ganda dan bersifat mullti arah.
Stack
Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO, benda terakhir yang masuk dalam stack akan menjadi benda yang pertama dikeluarkan dari stack. Operasi-operasi yang terdapat dalam stack, antara lain :
Push Untuk menambahkan item pada tumpukan paling atas.
Pop Untuk mengambil item teratas.
Clear Untuk mengosongkan stack
IsEmpty Untuk memeriksa apakah stack kosong.
IsFull Untuk memeriksa apakah stack sudah penuh
Retrieve Untuk mendapatkan nilai dari item teratas.
Queue
Queue berarti antrian. Queue merupakan salah satu contoh aplikasi pembuatan double linked list. Operasi-operasi yang terdapat dalam Queue, sebagai berikut :
- EnQueue Memasukkan data ke dalam antrian.
- DeQueue Mengeluarkan data terdepan dari antrian.
- Clear Menghapus seluruh antrian.
- IsEmpty Memeriksa apakah antrian kosong.
- IsFull Memeriksa apakah antrian penuh.
Tree
Tree merupakan kumpulan node/simpul dengan elemen khusus yang disebut Root. Node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lain (disebut subtree ). Istilah-istilah umum dalam Tree :
- Jenis-Jenis Tree :
• Binary Tree.
• Full Binary Tree.
• Complete Binary Tree.
• Skewed Binary tree.
3. Kesimpulan
Algoritma adalah urutan langkah logis untuk memecahkan masalah. Dan Struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna.
Materi yang terdapat dalam mata kuliah algoritma dan struktur data II meliputi : Array, Pointer, Structure, Linked list,stack, Queue, dan Tree.
Array adalah Struktur data yang memiliki banyak elemen di dalamnya, dengan masing-masing elemen memiliki tipe data yang sama.
Pointer adalah type data khusus yang berfungsi menampung bilangan tertentu yang menunjuk pada lokasi memori tertentu. Structure adalah kumpulan elemen-elemen data yang digabungkan menjadi satu kesatuan. Linked list adalah list yang didesain dengan cara mendefinisikan sebuah elemen yang memiliki hubungan atau link dengan elemen lain yang dihubungkan dengan elemen yang lain lagi. Stack adalah list yang besifat LIFO. Queue adalah struktur list dengan sifat FIFO, cara kerjanya seperti antrian manusia. Tree : suatu struktur data yang setiap elemen terhubung sedemikian rupa sehingga berbentuk seperti pohon.
4. Kesan dan Pesan Kepada Pengajar
Kesan : materi yang disampaikan jelas dan mudah dimengerti ditambah dengan cerita-cerita lucu dari Pak Dody membuat suasana kelas menjadi lebih hidup dan membuat rasa ngantuk hilang seketika.
Pesan : -
Selasa, 23 Juni 2009
Kamis, 04 Juni 2009
Tugas Praktek Algo
I Made Wira Dharma
080010243
P081
POINTER
Dikutip dari :mas-devid.blogspot.com
Pengertian Pointer
Pointer (variabel penunjuk) adalah suatu variabel yang berisi alamat memori dari suatu variabel lain. Alamat ini merupakan lokasi dari obyek lain (biasanya variabel lain) di dalam memori. Contoh, jika sebuah variabel berisi alamat dari variabel lain, variabel pertama dikatakan menunjuk ke variabel kedua.
Operator Pointer
Ada 2 operator pointer yang dikenal secara luas, yaitu operator & dan operator *.
Operator &
Operator & merupakan operator alamat. Pada saat pendeklarasian variable, user tidak diharuskan menentukan lokasi sesungguhnya pada memory, hal ini akan dilakukan secara otomatis oleh kompiler dan operating sysem pada saat run-time. Jika ingin mengetahui dimana suatu variable akan disimpan, dapat dilakukan dengan memberikan tanda ampersand (&) didepan variable , yang berarti "address of". Contoh :
ted = &andy;
Penulisan tersebut berarti akan memberikan variable ted alamat dari variable andy. Karena variabel andy diberi awalan karakter ampersand (&), maka yang menjadi pokok disini adalah alamat dalam memory, bukan isi variable. Misalkan andy diletakkan pada alamat 1776 kemudian dituliskan instruksi sbb :
andy = 25;
fred = andy;
ted = &andy;
Operator *
Operator * merupakan operator reference. Dengan menggunakan pointer, kita dapat mengakses nilai yang tersimpan secara langsung dengan memberikan awalan operator asterisk (*) pada identifier pointer, yang berarti "value pointed by". Contoh :
beth = *ted;
(dapat dikatakan:"beth sama dengan nilai yang ditunjuk oleh ted") beth = 25, karena ted dialamat 1776, dan nilai yang berada pada alamat 1776 adalah 25.
Ekspresi dibawah ini semuanya benar, perhatikan :
andy = 25;
&andy = 1776;
ted = 1776;
*ted = 25;
Ekspresi pertama merupakan assignation bahwa andy = 25;. Kedua, menggunakan operator alamat (address/derefence operator (&)), sehingga akan mengembalikan alamat dari variabel andy. Ketiga bernilai benar karena assignation untuk ted adalah ted = &andy;. Keempat menggunakan reference operator (*) yang berarti nilai yang ada pada alamat yang ditunjuk oleh ted, yaitu 25. Maka ekspresi dibawah ini pun akan bernilai benar :
*ted = andy;
Deklarasi Pointer
Seperti halnya variabel lain, variabel pointer juga harus dideklarasikan terlebih dahulu sebelum digunakan. Bentuk umum deklarasi pointer adalah :
\
Dimana Tipe_data
merupakan tipe dari data yang ditunjuk, bukan tipe dari pointer-nya. Contoh :
1. Mensubstitusikan address sebuah variabel ke pointer dengan memakai address operator &
int x;
int *ptr;
ptr = &x;
2. Mensubstitusikan address awal sebuah array ke pointer
char t[5];
char *ptr;
ptr = t;
3. Mensubstitusikan address salah satu elemen array dengan address operator
char t[5] ;
char *ptr;
ptr = &t[3];
4. Mensubstitusikan address awal character string ke pointer char
char *ptr;
ptr = "jakarta"
5. Mensubstitusikan NULL pada pointer. NULL ada pointer kosong, menunjukkan suatu status dimana pointer itu belum diinisialisasikan dengan sebuah address tertentu.
6. Memakai fungsi MALLOC.
LINKED LIST
Dikutip dari : http://hatma.info/download/struktur_data/
linked%20list%20VS%20array.doc.
Pengertian Linked list :
• sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian
• struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori.
X
Y
Null
Bentuk Umum :
Infotype sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list
Next address dari elemen berikutnya (suksesor)
Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu dengan notasi :
Sebelum digunakan harus dideklarasikan terlebih dahulu :
Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :
Beberapa Definisi :
1. List l adalah list kosong, jika First(L) = Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena
Next(Last) = Nil
Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null
Single Linked List
Pada gambar di atas tampak bahwa sebuah data terletak pada sebuah lokasi memori area. Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).
Pembuatan Single Linked List dapat menggunakan 2 metode:
• LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
• FIFO (First In First Out), aplikasinya : Queue (Antrean)
Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.
Circular Double Linked List
Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.
Operasi-Operasi yang ada pada Linked List
• Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
• IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
• Find First
Fungsi ini mencari elemen pertama dari linked list
• Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
• Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
• Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
• Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
• Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
• Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.
A. STACK DENGAN SINGLE LINKED LIST
Selain implementasi stack dengan array seperti telah dijelaskan sebelumnya, stack daat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori.
Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack.
Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.
Operasi-operasi untuk Stack dengan Linked List
• IsEmpty
Fungsi memeriksa apakah stack yang adamasih kosong.
• Push
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.
• Pop
Fungsi ini mengeluarkan elemen teratas dari stack.
• Clear
Fungsi ini akan menghapus stack yang ada.
B. QUEUE DENGAN DOUBLE LINKED LIST
Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list.
Operasi-operasi Queue dengan Double Linked List
• IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.
• IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
• EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
• DeQueue
Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).
Stack Dengan Linked List Stack Dengan Array operasi : create() procedure create;
begin
top := nil ;
end;
procedure create;
begin
top := 0;
end;
operasi : empty() function empty : boolean;
begin
empty := false ;
if top = nil then empty := true ;
end;
function empty : boolean;
begin
empty := false ;
if top = 0 then empty := true ;
end;
operasi : full() tidak ada istilah full pada stack.
program tidak menentukan jumlah elemen stack yang mungkin ada. kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. tempat akan sesuai dengan banyaknya elemen yang mengisi stack.
function full : boolean;
begin
full := false ;
if top = max then full := true ;
end;
operasi : push() procedure push (elemen : typedata) ;
var now:point ;
begin
now(now) ;
now^.isi := elemen ;
if empty then
now^.next := nil ;
else
now^.next := top ;
top := now ;
end;
procedure push (elemen : typedata) ;
begin
if not full then
begin
top := top + 1 ;
stack [top] := elemen ;
end;
end;
operasi : pop() procedure pop (var elemen : typedata) ;
var now:point ;
begin
if not empty then
begin
elemen := now^.isi ;
now := top ;
top := top^.next ;
dispose(now) ;
end;
end;
procedure pop (elemen : typedata) ;
begin
if not empty then
begin
elemen := stack [top] ;
top := top – 1 ;
end;
end;
operasi : clear procedure clear ;
var trash : typedata ;
begin
while not empty do pop(trash) ;
end;
procedure clear ;
begin
top := 0 ;
end;
__Sorting Source Code__
#include <iostream.h>
#include <conio.h>
int data[100],data2[100];
int n;
void tukar(int a,int b)
{
int t;
t = data[b];
data[b] = data[a];
data[a] = t;
}
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);
}
}
cout<<"bubble sort selesai!"<<endl;
}
void exchange_sort()
{
for (int i=0; i<n-1; i++)
{
for(int j = (i+1); j<n; j++)
{
if (data [i] > data[j]) tukar(i,j);
}
}
cout<<"exchange sort selesai!"<<endl;
}
void selection_sort()
{
int pos,i,j;
for(i=0;i<n-1;i++)
{
pos = i;
for(j = i+1;j<n;j++)
{
if(data[j] < data[pos]) pos = j;
}
if(pos != i) tukar(pos,i);
}
cout<<"selection sort selesai!"<<endl;
}
void insertion_sort()
{
int temp,i,j;
for(i=1;i<n;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!"<<endl;
}
void QuickSort(int L, int R) //the best sort i've ever had :)
{
int i, j;
int mid;
i = L;
j = R;
mid = data[(L+R) / 2];
do
{
while (data[i] < mid) i++;
while (data[j] > mid) j--;
if (i <= j)
{
tukar(i,j);
i++;
j--;
};
} while (i < j);
if (L < j) QuickSort(L, j);
if (i < R) QuickSort(i, R);
}
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];
}
}
void Tampil()
{
cout<<"Data : "<<endl;
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
}
void AcakLagi()
{
for(int i=0;i<n;i++)
{
data[i] = data2[i];
}
cout<<"Data sudah teracak!"<<endl;
}
void main()
{
int pil;
clrscr();
do
{
clrscr();
cout<<"Program Sorting Komplit!!!"<<endl;
cout<<"*********************************************"<<endl;
cout<<" 1. Input Data"<<endl;
cout<<" 2. Bubble Sort"<<endl;
cout<<" 3. Exchange Sort"<<endl;
cout<<" 4. Selection Sort"<<endl;
cout<<" 5. Insertion Sort"<<endl;
cout<<" 6. Quick Sort"<<endl;
cout<<" 7. Tampilkan Data"<<endl;
cout<<" 8. Acak Data"<<endl;
cout<<" 9. Exit"<<endl;
cout<<" Pilihan Anda = "; cin>>pil;
switch(pil)
{
case 1:Input(); break;
case 2:bubble_sort(); break;
case 3:exchange_sort(); break;
case 4:selection_sort(); break;
case 5:insertion_sort(); break;
case 6:QuickSort(0,n-1);
cout<<"quick sort selesai!"<<endl;
break;
case 7:Tampil(); break;
case 8:AcakLagi(); break;
}
getch();
}while(pil!=9);
}
source code program Sequential
Yang datanya telah diinputkan di source code.
#include <iostream.h>
#include <conio.h>
void main()
{
clrscr();
int data[8] = {8,10,6,-2,10,7,1,100};
int cari,index;
int ketemu=0;
cout<<"masukkan data yang ingin dicari = ";
cin>>cari;
for(int i=0;i<8;i++)
{
if(data[i] == cari)
{
ketemu=1;
index = i;
break;
}
}
if(ketemu == 1)
{
cout<<"Data ada!"<<endl;
cout<<"Data terletak di index ke - "<<index;
}
else cout<<"Data Tidak ada!"<<endl;
getch();
}
source code program Sequential
Yang datanya telah diinputkan dari user.
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int data[100],n;
int cari,index;
int ketemu=0;
cout<<"Masukkan jumlah data : "; cin>>n;
for(int i=0;i<n;i++)
{
cout<<"Masukkan data ke-"<<(i+1)<<" = "; cin>>data[i];
}
cout<<"Masukkan data yang ingin di cari = ";
cin>>cari;
for(int i=1;i<=100;i++)
{
if(data[i]==cari)
{
ketemu=1;
index=i;
break;
}
}
if(ketemu==1)
{
cout<<"Data ada !"<<endl;
cout<<"Data terletak di index ke-"<<index;
}
else cout<<"Data Tidak ada !"<<endl;
getch();
}
source code program Binary Searching
#include<iostream.h>
#include<conio.h>
int data[10] = {1,3,4,7,12,25,40,65,78,90}; //variabel global
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 < data[m])
r = m-1;
else l = m+1;
}
if(ketemu == 1) return 1; else return 0;
}
void main()
{
clrscr();
int cari,hasil;
cout<<"masukkan data yang ingin dicari = ";
cin>>cari;
hasil = binary_search(cari);
if(hasil == 1)
{
cout<<"Data ada!"<<endl;
}
else
if(hasil == 0)
cout<<"Data Tidak ada!"<<endl;
getch();
}
Algoritma Sorting
ada beberapa Algoritma Sorting, yaitu :
1.Insertion Sort
Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu.
Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling
kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja,sebutlah meja
ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian
kita mempunyai meja yang lain,meja kedua, dimana kartu yang diurutkan akan diletakkan.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.
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi
dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja
kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan
kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah
diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang
tersisa pada bagian array yang belum diurutkan.
2.Selection Sort
Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan
menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion
sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan. Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah–langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan dapat digeser dengan kartu yang bernilai lebih rendah.Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi
3.Merge Sort
Sebelum mendalami algoritma merge sort, mari kita mengetahui garis besar dari
konsep divide and conquer karena merge sort mengadaptasi pola tersebut.
Pola Divide and Conquer
Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan
permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah,
kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan
utama.
Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.
- Divide
Memilah masalah menjadi sub masalah
- Conquer
Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut
cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan
lebih efektif
- Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju
penyelesaian atas permasalahan utama
4.Quicksort
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 Binary Search
Binary Search adalah algoritma pencarian yang lebih efisien daripada algorima Sequential Search. Hal ini dikarenakan algoritma ini tidak perlu menjelajahi setiap elemen dari tabel. Kerugiannya adalah algoritma ini hanya bisa digunakan pada tabel
yang elemennya sudah terurut baik menaik maupun menurun.Pada intinya, algoritma ini menggunakan prinsip divide and conquer, dimana sebuah masalah atau tujuan diselesaikan dengan cara mempartisi masalah menjadi bagian yang lebih kecil. Algoritma ini membagi sebuah tabel menjadi dua dan memproses satu bagian dari tabel itu saja.
Algoritma ini bekerja dengan cara memilih record dengan indeks tengah dari tabel
dan membandingkannya dengan record yang hendak dicari. Jika record tersebut lebih rendah atau lebih tinggi, maka tabel tersebut dibagi dua dan bagian tabel yang bersesuaian akan diproses kembali secara
rekursif.
080010243
P081
POINTER
Dikutip dari :mas-devid.blogspot.com
Pengertian Pointer
Pointer (variabel penunjuk) adalah suatu variabel yang berisi alamat memori dari suatu variabel lain. Alamat ini merupakan lokasi dari obyek lain (biasanya variabel lain) di dalam memori. Contoh, jika sebuah variabel berisi alamat dari variabel lain, variabel pertama dikatakan menunjuk ke variabel kedua.
Operator Pointer
Ada 2 operator pointer yang dikenal secara luas, yaitu operator & dan operator *.
Operator &
Operator & merupakan operator alamat. Pada saat pendeklarasian variable, user tidak diharuskan menentukan lokasi sesungguhnya pada memory, hal ini akan dilakukan secara otomatis oleh kompiler dan operating sysem pada saat run-time. Jika ingin mengetahui dimana suatu variable akan disimpan, dapat dilakukan dengan memberikan tanda ampersand (&) didepan variable , yang berarti "address of". Contoh :
ted = &andy;
Penulisan tersebut berarti akan memberikan variable ted alamat dari variable andy. Karena variabel andy diberi awalan karakter ampersand (&), maka yang menjadi pokok disini adalah alamat dalam memory, bukan isi variable. Misalkan andy diletakkan pada alamat 1776 kemudian dituliskan instruksi sbb :
andy = 25;
fred = andy;
ted = &andy;
Operator *
Operator * merupakan operator reference. Dengan menggunakan pointer, kita dapat mengakses nilai yang tersimpan secara langsung dengan memberikan awalan operator asterisk (*) pada identifier pointer, yang berarti "value pointed by". Contoh :
beth = *ted;
(dapat dikatakan:"beth sama dengan nilai yang ditunjuk oleh ted") beth = 25, karena ted dialamat 1776, dan nilai yang berada pada alamat 1776 adalah 25.
Ekspresi dibawah ini semuanya benar, perhatikan :
andy = 25;
&andy = 1776;
ted = 1776;
*ted = 25;
Ekspresi pertama merupakan assignation bahwa andy = 25;. Kedua, menggunakan operator alamat (address/derefence operator (&)), sehingga akan mengembalikan alamat dari variabel andy. Ketiga bernilai benar karena assignation untuk ted adalah ted = &andy;. Keempat menggunakan reference operator (*) yang berarti nilai yang ada pada alamat yang ditunjuk oleh ted, yaitu 25. Maka ekspresi dibawah ini pun akan bernilai benar :
*ted = andy;
Deklarasi Pointer
Seperti halnya variabel lain, variabel pointer juga harus dideklarasikan terlebih dahulu sebelum digunakan. Bentuk umum deklarasi pointer adalah :
\
Dimana Tipe_data
merupakan tipe dari data yang ditunjuk, bukan tipe dari pointer-nya. Contoh :
1. Mensubstitusikan address sebuah variabel ke pointer dengan memakai address operator &
int x;
int *ptr;
ptr = &x;
2. Mensubstitusikan address awal sebuah array ke pointer
char t[5];
char *ptr;
ptr = t;
3. Mensubstitusikan address salah satu elemen array dengan address operator
char t[5] ;
char *ptr;
ptr = &t[3];
4. Mensubstitusikan address awal character string ke pointer char
char *ptr;
ptr = "jakarta"
5. Mensubstitusikan NULL pada pointer. NULL ada pointer kosong, menunjukkan suatu status dimana pointer itu belum diinisialisasikan dengan sebuah address tertentu.
6. Memakai fungsi MALLOC.
LINKED LIST
Dikutip dari : http://hatma.info/download/struktur_data/
linked%20list%20VS%20array.doc.
Pengertian Linked list :
• sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian
• struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori.
X
Y
Null
Bentuk Umum :
Infotype sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list
Next address dari elemen berikutnya (suksesor)
Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu dengan notasi :
Sebelum digunakan harus dideklarasikan terlebih dahulu :
Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :
Beberapa Definisi :
1. List l adalah list kosong, jika First(L) = Nil
2. Elemen terakhir dikenali, dengan salah satu cara adalah karena
Next(Last) = Nil
Nil adalah pengganti Null, perubahan ini dituliskan dengan #define Nil Null
Single Linked List
Pada gambar di atas tampak bahwa sebuah data terletak pada sebuah lokasi memori area. Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).
Pembuatan Single Linked List dapat menggunakan 2 metode:
• LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
• FIFO (First In First Out), aplikasinya : Queue (Antrean)
Double Linked List
Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.
Circular Double Linked List
Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.
Operasi-Operasi yang ada pada Linked List
• Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
• IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
• Find First
Fungsi ini mencari elemen pertama dari linked list
• Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
• Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
• Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
• Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
• Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
• Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.
A. STACK DENGAN SINGLE LINKED LIST
Selain implementasi stack dengan array seperti telah dijelaskan sebelumnya, stack daat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori.
Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack.
Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.
Operasi-operasi untuk Stack dengan Linked List
• IsEmpty
Fungsi memeriksa apakah stack yang adamasih kosong.
• Push
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.
• Pop
Fungsi ini mengeluarkan elemen teratas dari stack.
• Clear
Fungsi ini akan menghapus stack yang ada.
B. QUEUE DENGAN DOUBLE LINKED LIST
Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list.
Operasi-operasi Queue dengan Double Linked List
• IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.
• IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
• EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
• DeQueue
Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).
Stack Dengan Linked List Stack Dengan Array operasi : create() procedure create;
begin
top := nil ;
end;
procedure create;
begin
top := 0;
end;
operasi : empty() function empty : boolean;
begin
empty := false ;
if top = nil then empty := true ;
end;
function empty : boolean;
begin
empty := false ;
if top = 0 then empty := true ;
end;
operasi : full() tidak ada istilah full pada stack.
program tidak menentukan jumlah elemen stack yang mungkin ada. kecuali dibatasi oleh pembuat program dan jumlah memory yang tersedia. tempat akan sesuai dengan banyaknya elemen yang mengisi stack.
function full : boolean;
begin
full := false ;
if top = max then full := true ;
end;
operasi : push() procedure push (elemen : typedata) ;
var now:point ;
begin
now(now) ;
now^.isi := elemen ;
if empty then
now^.next := nil ;
else
now^.next := top ;
top := now ;
end;
procedure push (elemen : typedata) ;
begin
if not full then
begin
top := top + 1 ;
stack [top] := elemen ;
end;
end;
operasi : pop() procedure pop (var elemen : typedata) ;
var now:point ;
begin
if not empty then
begin
elemen := now^.isi ;
now := top ;
top := top^.next ;
dispose(now) ;
end;
end;
procedure pop (elemen : typedata) ;
begin
if not empty then
begin
elemen := stack [top] ;
top := top – 1 ;
end;
end;
operasi : clear procedure clear ;
var trash : typedata ;
begin
while not empty do pop(trash) ;
end;
procedure clear ;
begin
top := 0 ;
end;
__Sorting Source Code__
#include <iostream.h>
#include <conio.h>
int data[100],data2[100];
int n;
void tukar(int a,int b)
{
int t;
t = data[b];
data[b] = data[a];
data[a] = t;
}
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);
}
}
cout<<"bubble sort selesai!"<<endl;
}
void exchange_sort()
{
for (int i=0; i<n-1; i++)
{
for(int j = (i+1); j<n; j++)
{
if (data [i] > data[j]) tukar(i,j);
}
}
cout<<"exchange sort selesai!"<<endl;
}
void selection_sort()
{
int pos,i,j;
for(i=0;i<n-1;i++)
{
pos = i;
for(j = i+1;j<n;j++)
{
if(data[j] < data[pos]) pos = j;
}
if(pos != i) tukar(pos,i);
}
cout<<"selection sort selesai!"<<endl;
}
void insertion_sort()
{
int temp,i,j;
for(i=1;i<n;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!"<<endl;
}
void QuickSort(int L, int R) //the best sort i've ever had :)
{
int i, j;
int mid;
i = L;
j = R;
mid = data[(L+R) / 2];
do
{
while (data[i] < mid) i++;
while (data[j] > mid) j--;
if (i <= j)
{
tukar(i,j);
i++;
j--;
};
} while (i < j);
if (L < j) QuickSort(L, j);
if (i < R) QuickSort(i, R);
}
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];
}
}
void Tampil()
{
cout<<"Data : "<<endl;
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
}
void AcakLagi()
{
for(int i=0;i<n;i++)
{
data[i] = data2[i];
}
cout<<"Data sudah teracak!"<<endl;
}
void main()
{
int pil;
clrscr();
do
{
clrscr();
cout<<"Program Sorting Komplit!!!"<<endl;
cout<<"*********************************************"<<endl;
cout<<" 1. Input Data"<<endl;
cout<<" 2. Bubble Sort"<<endl;
cout<<" 3. Exchange Sort"<<endl;
cout<<" 4. Selection Sort"<<endl;
cout<<" 5. Insertion Sort"<<endl;
cout<<" 6. Quick Sort"<<endl;
cout<<" 7. Tampilkan Data"<<endl;
cout<<" 8. Acak Data"<<endl;
cout<<" 9. Exit"<<endl;
cout<<" Pilihan Anda = "; cin>>pil;
switch(pil)
{
case 1:Input(); break;
case 2:bubble_sort(); break;
case 3:exchange_sort(); break;
case 4:selection_sort(); break;
case 5:insertion_sort(); break;
case 6:QuickSort(0,n-1);
cout<<"quick sort selesai!"<<endl;
break;
case 7:Tampil(); break;
case 8:AcakLagi(); break;
}
getch();
}while(pil!=9);
}
source code program Sequential
Yang datanya telah diinputkan di source code.
#include <iostream.h>
#include <conio.h>
void main()
{
clrscr();
int data[8] = {8,10,6,-2,10,7,1,100};
int cari,index;
int ketemu=0;
cout<<"masukkan data yang ingin dicari = ";
cin>>cari;
for(int i=0;i<8;i++)
{
if(data[i] == cari)
{
ketemu=1;
index = i;
break;
}
}
if(ketemu == 1)
{
cout<<"Data ada!"<<endl;
cout<<"Data terletak di index ke - "<<index;
}
else cout<<"Data Tidak ada!"<<endl;
getch();
}
source code program Sequential
Yang datanya telah diinputkan dari user.
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int data[100],n;
int cari,index;
int ketemu=0;
cout<<"Masukkan jumlah data : "; cin>>n;
for(int i=0;i<n;i++)
{
cout<<"Masukkan data ke-"<<(i+1)<<" = "; cin>>data[i];
}
cout<<"Masukkan data yang ingin di cari = ";
cin>>cari;
for(int i=1;i<=100;i++)
{
if(data[i]==cari)
{
ketemu=1;
index=i;
break;
}
}
if(ketemu==1)
{
cout<<"Data ada !"<<endl;
cout<<"Data terletak di index ke-"<<index;
}
else cout<<"Data Tidak ada !"<<endl;
getch();
}
source code program Binary Searching
#include<iostream.h>
#include<conio.h>
int data[10] = {1,3,4,7,12,25,40,65,78,90}; //variabel global
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 < data[m])
r = m-1;
else l = m+1;
}
if(ketemu == 1) return 1; else return 0;
}
void main()
{
clrscr();
int cari,hasil;
cout<<"masukkan data yang ingin dicari = ";
cin>>cari;
hasil = binary_search(cari);
if(hasil == 1)
{
cout<<"Data ada!"<<endl;
}
else
if(hasil == 0)
cout<<"Data Tidak ada!"<<endl;
getch();
}
Algoritma Sorting
ada beberapa Algoritma Sorting, yaitu :
1.Insertion Sort
Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu.
Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling
kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja,sebutlah meja
ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian
kita mempunyai meja yang lain,meja kedua, dimana kartu yang diurutkan akan diletakkan.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.
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi
dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja
kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan
kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah
diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang
tersisa pada bagian array yang belum diurutkan.
2.Selection Sort
Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan
menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion
sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan. Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah–langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan dapat digeser dengan kartu yang bernilai lebih rendah.Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi
3.Merge Sort
Sebelum mendalami algoritma merge sort, mari kita mengetahui garis besar dari
konsep divide and conquer karena merge sort mengadaptasi pola tersebut.
Pola Divide and Conquer
Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan
permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah,
kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan
utama.
Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.
- Divide
Memilah masalah menjadi sub masalah
- Conquer
Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut
cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan
lebih efektif
- Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju
penyelesaian atas permasalahan utama
4.Quicksort
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 Binary Search
Binary Search adalah algoritma pencarian yang lebih efisien daripada algorima Sequential Search. Hal ini dikarenakan algoritma ini tidak perlu menjelajahi setiap elemen dari tabel. Kerugiannya adalah algoritma ini hanya bisa digunakan pada tabel
yang elemennya sudah terurut baik menaik maupun menurun.Pada intinya, algoritma ini menggunakan prinsip divide and conquer, dimana sebuah masalah atau tujuan diselesaikan dengan cara mempartisi masalah menjadi bagian yang lebih kecil. Algoritma ini membagi sebuah tabel menjadi dua dan memproses satu bagian dari tabel itu saja.
Algoritma ini bekerja dengan cara memilih record dengan indeks tengah dari tabel
dan membandingkannya dengan record yang hendak dicari. Jika record tersebut lebih rendah atau lebih tinggi, maka tabel tersebut dibagi dua dan bagian tabel yang bersesuaian akan diproses kembali secara
rekursif.
Langganan:
Postingan (Atom)