Selasa, 23 Juni 2009
di
17.04
|
Struktur data dan algoritma adalah langkah detail yang ditunjukkan oleh komputer guna menyelesaikan suatu masalah.hal itu diperlukan untuk mengolah masalah. Atau disebut juga langkah-langkah penyelesaian suatu masalah yang disusun secara logis dan berurutan.
Pelajaran-pelajaran atau materi yang terdapat di algoritma II adalah
1. Pointer
2. Array
3. Sturcture
4. Linked list
5. Stack
6. Queue
7. Tree
Pointer merupakan tipe data berukuran 32 bit yang berisi satu nilai yang berpadanan dengan alamat memori tertentu.sebagai contoh,sebuah variabel P bertipe pointer bernilai 0x0041FF2A,berarti P menunjukan pada alamat memori 0041FF2A.
Array adalah sekelompok data sejenis yang disimpan ke dalam variabel dengan nama yang sama, dengan memberi indeks pada variabel untuk membedakan antara yang satu dengan yang lain. Array juga suatu struktur yang terdiri sejumlah elemen yang memiliki tipe data yang sama.elemen array tersusun secara sekuensial dalam memori komputer.array dapat berupa satu dimensi,dua dimensi,tiga dimensi ataupun banyak dimensi(multi dimensi).array dapat dibedakan menjadi 2 bagian diantaranya:
• Array satu dimensi
• Array dua dimensi
Array satu dimensi:
Array satu dimensi adalah kumpulan elemen identik yang tersusun dalam satu baris.elemen tersebut memiliki tipe data yang sama,tetapi isi dari elemen tersebut boleh berbeda.
Array dua dimensi:
Array dua dimensi sering digambarkan sebagai sebuah matrik,merupakan perluasan dari array satu dimensi.jika array satu dimensi hanya terdiri dari sebuah baris dan beberapa kolom elemen,maka array dua dimensi terdiri dari beberapa baris dan beberapa kolom elemen yang bertipe sama.
Dalam bahasa c++ terdapat tipe structure yang dapat dipakai untuk menghimpun sebuah datadengan tipe yang berbeda beda,data yang diletakkan dalam sebuah structure adalah data yang terkait.sebagai contoh dimungkinkan untuk membuat tipe structure yang nengandung data nomor pegawai(NIP),nama pegawai,dan gaji. Structure adalah kumpulan elemen data yang digabungkan menjadi satu kesatuan.masing-masing elemen data tersebut dikenal dengan satuan field.field data tersebut dapat memiliki tipe data yang sama ataupun berbeda.walaupun field tersebut berada dalam satu kesatuan,masing-masing field tersebut tetap dapat diakses secara individual.
Pada bab sebelumnya telah dijelaskan mengenai variable array yang bersifat statis(ukuran dan urutannya sudah pasti).selain itu ruang memori yang dipakai olehnya tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan.untuk memecahkan masalah diatas,kita dapat menggunakan variable pointer.tipe data pointer besifat dinamis,variable akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat direlokasikan kembali. Setiap ingin menambahakn data,anda selalu menggunakan variabel pointer yang baru,akibatnya anda akan banyak manggunakan banyak variebel pointer.oleh karena itu lebih baik anda banyak menyimpan data dengan menggunakan metode Linked List. Linked List adalah sekumpulan elemen bertipe sama.Linked List dibedakan menjadi 2 yaitu :
• Single Linked List
• Double Linked List
Single Linked List:
Tempat yang disediakan satu area memori untuk menyimpan data yang dikenal dengan sebutan Node atau simbol. Susunan berupa untaian semacam ini disebut Single Link List (NULL memiliki nilai kusus. Bisanya Linked List pada titik akhir menuju ke NULL.) Kelemahan Linked List adalah pointer hhanya dapat bergerak satu arah saja.
Double Linked List
Untuk mengatasi kelemahan yang terdapat pada Single Linked List ada beberapa cara salah satunya menggunakan double Linked List.
Stack adalah tumpukan dari sebuah benda. Konsep utama dari Stack menggunakan konsep Last In First Out benda yang terakhir masuk akan menjadi benda yang pertama keluar. Susunan. Pada umumnya kata ini digunakan untuk bahasa Pemrograman yang menampung data-data dalam variabel yang tersusun dengan nama yang sama. Two array dimensions = susunan dua dimensi.
Array ini identik dengan susunan suatu rak yang diberi nama dan nomor. misalnya rak tersebut diberi nama {Pegawai} lalu data dari masing-masing pegawai tersebut ditempatkan berdasarkan nomornya.Setidaknya Stack harus memiliki operasi sebagai berikut :
• Push
• Pop
• Clear
• IsEmpty
• IsFull
• Retreive
Secara sederhana stack bisa diartikan dengan
• sebagai tumpukan dari benda
• sekumpulan data yang seolah-olah diletakkan di atas data yang lain
• koleksi dari objek-objek homogen
Dalam suatu stack terdapat 2 operasi utama, yaitu operasi push (memasukkan node ke dalam stack), dan pop (mengambil node dari stack), data melalui ujung yang sama (TOS, Top Of Stack), ujung ini merupakan ujung atas stack.
Queue bisa disebut juga antrean. Queue adalah suatu contoh aplikasi yang sama cara pembuatannya dengan Double Linked List. Dalam suatu antrean datang lebih dahulu akan dilayani lebih dahulu disebut dengan Dequeue. Queue mempunyai operasi data sebagai berikut :
• EnQueue
• DeQueue
• Clear
• IsEmpty
• IsFull
Dalam pembuatan program istilah tree bisa disebut struktur kata. Tree merupakan salah satu bentuk struktur tidak linier. Tree bisa didefinisikan sebagai kumpulan simbol dengan elemen kusus disebut root. Istilah-istilah dalam tree sebagai berikut :
• Size
• Root
• Leaf
• Degree
• Height
• Child
• Successor
• Predecessor
Jenis-jenis Tree :
• Binary Tree
• Full Binary Tree
• Complete Binary Tree
• Skewed Binary Tree
• Implementasi Binary Tree
Kesimpulan yang saya dapat dari materi atau pelajaran algoritma II:
Cara mempermudah untuk membuat suatu program,algoritma membuat kita untuk selalu teliti dalam membuat suatu program,dalam membuat suatu program kita tidak boleh takut untuk salah,karena dalam membuat program belajar dari kesalahan.
Kesan dan pesan saya dalam mata kuliah ini adalah:
pertama” saya belum terlalu bisa membuat suatu program dan saat ini saya sudah mengerti dalam membuat suatu program.pak dody sangat asik dalam pelajaran dan saya cepak mengerti.
Diposting oleh
alit surya dinata
Selasa, 09 Juni 2009
di
16.48
|
di kutip dari:
I kt alit surya dinata_080010244_P081
Pointer C++ (lanjutan sebelumnya)
Karena ada yang request untuk ditambah pembahasan tentang pointer, saya coba untuk menambahkan penjelasan penggunaan pointer di C++. Jika kita menggunakan pointer hanya dalam satu fungsi,mungkin manfaatnya tidak terlihat karena tidak ada bedanya dengan penggunaan variabel kecuali kita ingin menggunakan memori dinamis. Namun akan terasa bedanya jika kita ingin melewatkan suatu variabel ke fungsi lain dimana kita ingin langsung mengubah isi variabel tersebut didalam fungsi tanpa menunggu return dari fungsi tersebut. Contoh:
void negasi(int x){
x = -(x);
}
void negasiP(int *x){
*x = -(*x);
}
int main(){
int a=5;
int *b = a;
cout << “nilai a awal: “ << a << endl;
negasi(a);
cout << “nilai a jika a yang dilewatkan ke fungsi: “ << a << endl;
negasiP(b);
cout << “nilai a jika b yang dilewatkan ke fungsi: “ << a << endl;
return 0;
}
coba compile (mudah2n bisa,hehe…)
Sekarang perhatikan bahwa pointer b menyimpan alamat a. Ketika a yang dilewatkan ke fungsi, isi variabel a akan disalin ke x yaitu 5. Dengan demikian, jika ada statement yang merubah nilai 5 di variabel x pada fungsi negasi, hanya pada variabel x itu nilai 5 berubah karena nilai itu merupakan salinan dari nilai 5 pada variabel a. Sehingga tidak ada perubahan nilai 5 pada variabel a. Lain halnya pada waktu variabel b yang dilewatkan pada fungsi. Isi variabel b adalah alamat dari variabel a, sehingga yang dilewatkan pada fungsi adalah alamat tersebut yang disalin pada variabel x. Jika ada perubahan nilai 5 di variabel x pada fungsi negasiP maka nilai 5 pada variabel a juga akan berubah. Jika kita terjemahkan dalam bahasa manusia ;p perintah *x = -(*x) dapat diterjemahkan bahwa nilai pada alamat yang tersimpan dalam variabel x dikali dengan -1 (yaitu pernyataan -(*x)) kemudian disimpan ke alamat yang disimpan pada variabel x (yaitu pernyataan *x=). Alamat yang nilainya dirubah tersebut tidak lain adalah alamat variabel a sehingga nilai variabel a lah yang berubah.
Gimana? Sekarang sudah tergambar maksud dari pointer? Untuk lebih detail tentang pointer saya sarankan untuk membaca buku-buku pemrograman C++. Dan jika mau saya akan kirimkan ebook tentang pointer ke email anda. Kirim saja email ke abeinoe@gmail.com. Yang saya jelaskan di blog adalah hal yang tidak dijelaskan di buku-buku pemrograman umumnya.
STRUKTUR DATA (6)
single linked list non circular
Oleh Antonius Rachmat C, S.Kom
History of Linked List
* Dikembangkan tahun 1955-1956 oleh Allen Newell, Cliff Shaw dan Herbert Simon di RAND Corporation sebagai struktur data utama untuk bahasa Information Processing Language (IPL).
o IPL dibuat untuk mengembangkan program artificial intelligence, seperti pembuatan Chess Solver.
* Victor Yngve di Massachusetts Institute of Technology (MIT) juga menggunakan linked list pada natural language processing dan machine transitions pada bahasa pemrograman COMMIT.
Linked List
* Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung-menyambung, dinamis dan terbatas.
* Linked List sering disebut juga Senarai Berantai
* Linked List saling terhubung dengan bantuan variabel pointer
* Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.
Array VS Linked List
Bentuk Node Single Linked List non Circular
Pengertian:
* Single : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL
* Linked List : artinya node-node tersebut saling terhubung satu sama lain.
* Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
* Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.
Pembuatan Single Linked List non Circular (1)
Deklarasi Node
typedef struct TNode{
int data;
TNode *next;
};
Penjelasan:
* Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode
* Setelah pembuatan struct, buat variabel head yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.
Pembuatan Single Linked List non Circular (2)
* Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL.
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
Cara lain alokasi pointer
* Menggunakan alokasi memori secara manual
* Menggunakan header stdlib.h atau malloc.h
* Menggunakan fungsi:
*malloc(int size);
SLLNC MENGGUNAKAN HEAD
* Dibutuhkan satu buah variabel pointer: head
* Head akan selalu menunjuk pada node pertama
Deklarasi Pointer Penunjuk Kepala Single Linked List
* Manipulasi linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer penunjuk ke node pertama dalam linked list (dalam hal ini adalah head). Deklarasinya sebagai berikut:
* TNode *head;
SLLNC menggunakan Head
Fungsi Inisialisasi Single LinkedList
void init(){
head = NULL;
}
Function untuk mengetahui kosong tidaknya Single
LinkedList
* Jika pointer head tidak menunjuk pada suatu node maka kosong
int isEmpty(){
if(head == NULL) return 1;
else return 0;
}
SLLNC dengan HEAD
Penambahan data di depan
* Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan dengan cara: node head ditunjukkan ke node baru tersebut.
* Pada prinsipnya adalah mengkaitkan node baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.
SLLNC dengan HEAD
void insertDepan(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
head->next = NULL;
}
else {
baru->next = head;
head = baru;
}
printf(”Data masuk\n”);
}
SLLNC dengan Head
Penambahan data di belakang
* Penambahan data dilakukan di belakang, namun pada saat pertama kali, node langsung ditunjuk oleh head.
* Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui node terbelakang, kemudian setelah itu, dikaitkan dengan node baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.
SLLNC dengan HEAD
void insertBelakang (int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
head->next = NULL;
}
else {
bantu=head;
while(bantu->next!=NULL){
bantu=bantu->next;
}
bantu->next = baru;
}
printf("Data masuk\n“);
}
SLLNC dengan HEAD
“Bagaimana dengan penambahan di tengah?”
SLLNC dengan HEAD
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=NULL){
cout<data<<" ";
bantu=bantu->next;
}
printf(“\n”);
} else printf(“Masih kosong\n“);
}
SLLNC dengan HEAD
* Function di atas digunakan untuk menampilkan semua isi list, di mana linked list ditelusuri satu-persatu dari awal node sampai akhir node. Penelusuran ini dilakukan dengan menggunakan suatu pointer bantu, karena pada prinsipnya pointer head yang menjadi tanda awal list tidak boleh berubah/berganti posisi.
* Penelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke nilai NULL. Jika tidak NULL, maka node bantu akan berpindah ke node selanjutnya dan membaca isi datanya dengan menggunakan field next sehingga dapat saling berkait.
* Jika head masih NULL berarti data masih kosong!
SLLNC dengan HEAD
Function untuk menghapus data terdepan
void hapusDepan (){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head->next != NULL){
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
} else {
d = head->data;
head = NULL;
}
printf(“%d terhapus\n“,d);
} else cout<<"Masih kosong\n";
}
SLLNC dengan HEAD
* Function di atas akan menghapus data teratas (pertama) yang ditunjuk oleh head pada linked list
* Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunakan suatu pointer lain yang digunakan untuk menunjuk node yang akan dihapus, misalnya pointer hapus dan barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete.
* Sebelum data terdepan dihapus, head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan menjadi head baru (data terdepan yang baru).
* Jika head masih NULL maka berarti data masih kosong!
SLLNC dengan HEAD
Hapus Belakang
void hapusBelakang(){
TNode *hapus,*bantu;
int d;
if (isEmpty()==0){
if(head->next != NULL){
bantu = head;
while(bantu->next->next!=NULL){
bantu = bantu->next;
}
hapus = bantu->next;
d = hapus->data;
bantu->next = NULL;
delete hapus;
} else {
d = head->data;
head = NULL;
}
printf(“%d terhapus\n“,d);
} else printf(“Masih kosong\n“);
}
SLLNC dengan HEAD
* Membutuhkan pointer bantu dan hapus.
* Pointer hapus digunakan untuk menunjuk node yang akan dihapus, dan pointer bantu digunakan untuk menunjuk node sebelum node yang dihapus yang kemudian selanjutnya akan menjadi node terakhir.
* Pointer bantu akan digunakan untuk menunjuk ke nilai NULL.
* Pointer bantu akan selalu bergerak sampai sebelum node yang akan dihapus, baru kemudian pointer hapus diletakkan setelah pointer bantu. Setelah itu pointer hapus akan dihapus, pointe bantu akan menunjuk ke NULL.
SLLNC dengan HEAD
Function untuk menghapus semua elemen Linked List
void clear(){
TNode *bantu,*hapus;
bantu = head;
while(bantu!=NULL){
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
}
SLLNC dengan HEAD & TAIL
* Dibutuhkan dua buah variabel pointer: head dan tail
* Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.
SLLNC dengan HEAD & TAIL
Inisialisasi LinkedList
TNode *head, *tail;
Fungsi Inisialisasi LinkedList
void init(){
head = NULL;
tail = NULL;
}
Function untuk mengetahui kosong tidaknya LinkedList
int isEmpty(){
if(tail == NULL) return 1;
else return 0;
}
SLLNC dengan HEAD & TAIL
Pengkaitan node baru ke linked list di depan
Penambahan data baru di depan akan selalu menjadi head.
void insertDepan(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=tail=baru;
tail->next=NULL;
}
else {
baru->next = head;
head = baru;
}
printf(”Data masuk\n”);
}
SLLNC dengan HEAD & TAIL
Penambahan Data di belakang
void tambahBelakang(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
if(isEmpty()==1){
head=baru;
tail=baru;
tail->next = NULL;
}
else {
tail->next = baru;
tail=baru;
}
printf("Data masuk\n“);
}
SLLNC dengan HEAD & TAIL
* Kelebihan dari Single Linked List dengan Head & Tail adalah pada penambahan data di belakang, hanya dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu.
Function untuk menampilkan isi linked list:
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=NULL){
printf(“%d\n”,bantu->data);
bantu=bantu->next;
}
printf(“\n”);
} else printf(“Masih kosong\n“);
}
SLLNC dengan HEAD & TAIL
* Function untuk menghapus data di depan
void hapusDepan(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head!=tail){
hapus = head;
d = hapus->data;
head = head->next;
delete hapus;
} else {
d = tail->data;
head=tail=NULL;
}
printf(“%d terhapus\n“,d);
} else printf("Masih kosong\n“);
}
SLLNC dengan HEAD & TAIL
* Function di atas akan menghapus data terdepan (pertama) yang ditunjuk oleh head pada linked list
* Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan pointer hapus pada head, kemudian dilakukan pergeseran head ke node berikutnya sehingga data setelah head menjadi head baru, kemudian menghapus pointer hapus dengan menggunakan perintah delete.
* Jika tail masih NULL maka berarti list masih kosong!
SLLNC dengan HEAD & TAIL
Function untuk menghapus data di belakang:
void hapusBelakang(){
TNode *bantu,*hapus;
int d;
if (isEmpty()==0){
bantu = head;
if(head!=tail){
while(bantu->next!=tail){
bantu = bantu->next;
}
hapus = tail;
tail=bantu;
d = hapus->data;
delete hapus;
tail->next = NULL;
}else {
d = tail->data;
head=tail=NULL;
}
cout<
} else cout<<"Masih kosong\n";
}
SLLNC dengan HEAD & TAIL
* Function di atas akan menghapus data terbelakang (terakhir) yang ditunjuk oleh tail pada linked list
* Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variabel hapus pada tail, kemudian dibutuhkan pointer bantu untuk membantu pergeseran dari head ke node berikutnya sampai sebelum tail, sehingga tail dapat ditunjukkan ke bantu tersebut, dan bantu tersebut akan menjadi tail yang baru. Setelah itu hapus pointer hapus dengan menggunakan perintah delete.
* Jika tail masih NULL maka berarti list masih kosong!
Function untuk menghapus semua elemen LinkedList
void clear(){
TNode *bantu,*hapus;
bantu = head;
while(bantu!=NULL){
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
tail = NULL;
}
sorting sourcecode
#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);
}
Sequential
#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();
}
Sequential yang di inputkan oleh 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();
}
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();
}
sorting
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
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.
Merge Sort
Sebelum mendalami algoritma merge sort, mari kita mengetahui garis besar dari
konsep divide and conquer karena merge sort mengadaptasi pola tersebut.
6.4.1Pola 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.
1. Divide
Memilah masalah menjadi sub masalah
2. Conquer
Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut
cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan
lebih efektif
3. Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju
penyelesaian atas permasalahan utama
6.4.2Memahami Merge Sort
Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan pola divide and
conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah
berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secara
rekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan
rangkaian data berurutan
Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian
yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen
tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
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
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. [2]
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.
Diposting oleh
alit surya dinata
|
MARVEL and SPIDER-MAN: TM & 2007 Marvel Characters, Inc. Motion Picture © 2007 Columbia Pictures Industries, Inc. All Rights Reserved. 2007 Sony Pictures Digital Inc. All rights reserved. blogger template by blog forum |
