Kali ini saya akan membahas tentang Searching... Apa ya..yang pertama kali ada di kepala kita begitu mendengar kata searching? Yupz..”mencari” pasti kata itu yang akan kita pikirkan. Kalau dalam Alogoritma dan Struktur Data, Searching adalah pencarian data dengan cara menelusuri data-data tersebut. Biasanya tempat pencarian datanya berupa array dalam memori, bisa juga pada file pada external storage. Kali ini saya akan membahas 2 jenis searching yaitu Sequential Search dan Binary Search.
Sequential Search Sequential Search adalah teknik pencarian data dalam array dengan cara menelusuri elemen-elemen array tanpa mengurutkan data terlebih dahulu. Kalau menggunakan sequential search ada plus-minusnya atau lebih tepatnya ada enaknya ada gak enaknya. Misalnya enaknya, kalau data yang dicari berada dibaris terdepan maka waktu yang diperlukan sebentar tp yang gak enaknya toe kalau data yang di cari berada dibarisan belakang maka waktu yang diperlukan cukup lama. Biar lebih jelasnya tak kasih contoh sebagai berikut :
Dari array satu dimensi diatas dicari misalnya angka 10, jika ada maka akan muncul tulisan “ADA”, tapi jika tidak ada maka akan muncul tulisan ”TIDAK ADA”.
Binary Search Binary Search adalah teknik pencarian data dalam array dengan cara membagi array menjadi dua bagian setiap kali terjadi proses pengurutan. Prinsip pencariannya adalah: 1. Data diambil dari posisi 1 sampai posisi akhir N 2. Terus cari posisi data tengah dengan rumus seperti ini (posisi awal + posisi akhir) / 2 3. Kemudian data yang dicari dibandingkan dengan data yang di tengah, sama atau lebih kecil, atau lebih besar? 4. Kalau lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1 5. Kalau lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1 6. Jika data sama, berarti ketemu.
Saya kasih contoh biar lebih paham lagi, misalnya sebagai berikut : Contoh Data: Misalnya data yang dicari 18
0 1 2 3 4 5 6 7 8 3 9 11 12 15 18 23 31 35 A B C
Karena 17 > 15 (data tengah), maka: awal = tengah + 1
0 1 2 3 4 5 6 7 8 3 9 11 12 15 18 23 31 35 A B C
Karena 17 < 23 (data tengah), maka: akhir = tengah – 1
0 1 2 3 4 5 6 7 8 3 9 11 12 15 18 23 31 35 A=B=C
Karena 18 = 18 (data tengah), maka KETEMU!
Nah...sekian dulu nie penjelasan tentang searching, sebenarnya pengen ngejelasin yang lebih lengkap lagi tapi ada daya tangan ini sudah capek ngetik. he.... Terima kasih buat para pembaca.
Sorting adalah proses mengurutkan angka. Ada dua bentuk sorting yaitu secara ascending dan descending. Ascending adalah proses pengurutan angka atau data dari kecil kebesar, sedangkan Descending adalah kebalikan dari ascending yaitu proses pengurutan angka atau data dari besar kekecil. Berikut ini saya akan memberikan contohnya agar lebih jelas yaitu sebagai berikut : Data yang diacak : 3 1 5 11 9 Ascending : 1 3 5 9 11 Descending : 11 9 5 3 1 Deklarasi array untuk sorting Deklarasikan secara global : Int data [100] ; Int n; // untuk jumlah data
Prosedur Tukar 2 Buah Data : void tukar (in j, int k) { Int tmp; tmp = data [j]; data [j] = data [k]; data [k] = tmp; }
Bubble Sort
Bubble sort merupakan metode paling sederhana atau termudah dalam pengurutan data. Knp diberi nama bubble sort itu karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Cara kerjanya sbb: 1.Membandingkan sebuah bilangan dengan seluruh bilangan yang terletak setelah bilangan tersebut. 2.Penukaran terjadi apabila memenuhi kondisi tertentu.
Contoh :
Algoritma Bubble Sort
Dengan data diatas, maka data akan terurut naik (ascending), untuk urut turun ada bisa ubah pada bagian dibawah ini :
Ubah menjadi :
Exchange Sort
Exchange sort hampri mirip dengan Bubble sort yang berbeda adalah cara membandingkan elemen-elemennya. Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat.
Algoritma Exchange Sort
Selection Sort
Selection Sort adalah penggabungan antara Sorting dan Searching. Di Selection Sort setiap proses akan dicari elemen-elemen yang belum diurutkan misalnya mengurutkan data yang memiliki nilai dari yang terkecil atau terbesar yang akan diurutkan secara tepat di array.
Algoritma Selection Sort
Insertion Sort
Pengertian Insertion Sort itu bisa diibaratkan seperti mengurutkan kartu, ambil selemabar demi selembar kartu kemudian sisipkan ke tempat yang seharusnya. Pengurutan dalam dalam Insertion Sort dimulai dari data ke-2 sampai dengan data terakhir, jika ada nilai yang lebih kecil maka aka ditempatkan diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang. 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
Algoritma Insertion Sort
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 Quick Sort
Sumber : Andre Stafian, Rosihan Ari, Jeni-intro2 dll.
Sekian penjelasan saya untuk materi kali ini tentang Sorting. Kalau ada teman-teman yang pengen copy posting saya tentang sorting silahkan tapi jangan disamakan. Tidak lupa saya ucapkan terima kasih pada narasumber.
Linked list adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu komputer. Dengan menggunakan linked list maka programmer dapat menyimpan datanya kapanpun dibutuhkan. Linked list mirip dangan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).
Pada array, apabila programmer ingin menyimpan data, programmer diharuskan untuk mendefinisikan besar array terlebih dahulu, seringkali programmer mengalokasikan array yang sangat besar(misal 100). Hal ini tidak efektif karena seringkali yang dipakai tidak sebesar itu. Dan apabila programmer ingin menyimpan data lebih dari seratus data, maka hal itu tidak dapat dimungkinkan karena sifat array yang besarnya statik. Linked list adalah salah satu struktur data yang mampu menutupi kelemahan tersebut.
Secara umum linked list tersusun atas sejumlah bagian-bagian data yang lebih kecil yang terhubung (biasanya melalui pointer). Linked list dapat divisualisasikan seperti kereta, bagian kepala linked list adalah mesin kereta, data yang disimpan adalah gerbong, dan pengait antar gerbong adalah pointer.
Programmer membaca data menyerupai kondektur yang ingin memeriksa karcis penumpang. Programmer menyusuri linked list melalui kepalanya, dan kemudian berlanjut ke gerbong (data) berikutnya, dan seterusnya sampai gerbong terakhir (biasanya ditandai dengan pointer menunjukkan alamat kosong (NULL)). Penyusuran data dilakukan secara satu persatu sehingga penyusuran data bekerja dengan keefektifan On. Dibandingkan array, ini merupakan kelemahan terbesar linked list. Pada array, apabilan programmer ingin mengakses data ke-n (index n), maka programmer dapat langsung mengaksesnya. Sedangkan dengan linked list programmer harus menyusuri data sebanyak n terlebih dahulu.
Apabila kita menggunakan java, konsep linked list ini sudah terlingkupi dalam Java Collection Framework (JCF). Dengan Java, kita tidak perlu lagi membuat LinkedList. Kita tinggal menggunakan class yang sudah disediakan dalam JCF.
Berikut ini saya akan menjelaskan operasi-operasi yang ada pada Linked List yaitu sebagai berikut :
ØInsert Insert digunakan untuk menambahkan sebuah simpul baru ke dalam suatu linked list.
ØIsEmpty IsEmpty digunakan untuk mengetahui apakah linked list kosong atau tidak.
ØFineFirst Fine First digunakan untuk mencari elemen pertama dari linked lis
ØFine Next Fine Next digunakan untuk mencari elemen sesudah elemen yang ditunjuk oleh now.
ØRetrieve Retrieve digunakan untuk mengambil elemen yang ditunjuk oleh now. Kemudian elemen tersebut akan dikembalikan oleh fungsi.
ØUpdate Update digunkan untuk mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu.
ØDelete Now Delete Now digunakan untuk menghapus elemen yang ditunjuk oleh now.
ØDelete Head Delete Head digunakan untuk menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
ØClear Clear digunakan untuk 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.
Single Linked List Circular
Single Linked List Circular (SLLC) adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.
Pengertian:
Node : rangkaian beberapa simpul
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
LinkedList : artinya node-node tersebut saling terhubung satu sama lain.
Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar
DoubleLinkedList
Double Linked List (DLL) adalah suatu cara pengolahan data yang bekerja dengan record dalam jumlah besar, sehingga membutuhkan alokasi memori dinamis yang besar pula. DLL biasanya digunakan pada saat alokasi memori konvensional tidak lagi bisa diandalkan. Sedangkan bekerja dengan data yang besar tidak dapat dihindari lagi, karena tidak jarang pula, data besar tersebut memiliki hubungan yang erat.
Berikut ini saya akan memberikan contoh syntax dari linked list:
Single Linked List
#include <iostream.h>
#include <conio.h>
struct TNode
{
int data;
TNode *next;
};
TNode *head;
void init()
{
head = NULL;
}
int isEmpty()
{
if(head== NULL) return 1;
else return 0;
}
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;
}
cout<<endl;
cout<<"---> Data telah masuk...\n";
getch();
}
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;
}
cout<<d<<"data telah terhapus...\n"<<
} else cout<<"Masih kosong...\n";
getch();
}
void search(int caridata)
{
TNode *bantu;
bantu = head;
int ketemu = 0;
int index=0;
if(isEmpty()==0)
{
while(bantu!=NULL)
{
bantu->data;
if (caridata == bantu->data)
{
cout<<endl;
cout<<"Data Yang Ditemukan..."<<endl;
cout<<"Index Ke - "<
ketemu = 1;
break;
}
bantu=bantu->next;
index++;
}
cout<<endl;
if (ketemu == 0)
cout<<"Data Tidak Ditemukan...\n"<<endl;
cout<<endl;
} else
{
cout<<"Masih kosong..."<<endl;
cout<<"Anda belum memasukkan data...";
}
getch();
}
void tampil()
{
TNode *bantu;
bantu = head;
if(isEmpty()==0)
{
while(bantu!=NULL)
{
cout<<"-->"<<bantu->data<<" ";
bantu=bantu->next;
}
cout<<" --> NULL";
cout<< ;
}else
{
cout<<"Anda belum memasukkan data...\n"<<endl;
cout<<"Silahkan masukkan data terlebih dahulu...\n";
}
getch();
}
void main()
{
int pil,data_anda,cari;
init();
do
{
clrscr();
cout<<"--------Menu Pilihan------------"<<endl;
cout<<"#########################"<<endl;
cout<<"#1. Memasukkan List#"<
cout<<"#2. Menghapus Depan#"<<endl;
cout<<"#3. Menamplikan Data#"<
cout<<"#4. Mencari Data#"<
cout<<"#5. Keluar#"<<endl;
cout<<"#########################"<<endl;
cout<<endl;
cout<<"Pilihan anda = "; cin>>pil;
switch(pil)
{
case 1:
cout<<endl;
cout<<"Masukan data = "; cin>>data_anda;
insertDepan(data_anda);
break;
case 2:
hapusDepan();
break;
case 3:
cout<<endl;
cout<<endl;
tampil();
break;
case 4:
cout<<endl;
cout<<&l;"Data yg Dicari --> "; cin>>cari;
search(cari);
break;
};
}
while(pil!=5);
}
Sumber Dari Herison Subakti, Meike Prastiwi dan Wikipedia bahasa Indonesia, ensiklopedia bebas
Sekian artikel tentang Linked List dari saya, jika ada kekurangan atau kata yang kurang berkenan bagi para pembaca harap dimaklumi dan terima kasih kepda narasumber.
