Struktur Data - Searching

Materi ini merupakan kelanjutan dari materi saya sebelumnya, tentang sorting, karena konsep sorting akan digunakan pada searching ini (algoritma binary search)

Searching atau proses pencarian data, memudahkan kita dalam mencari data yang kita butuhkan. Algoritma searching sebenarnya cukup banyak, namun disini saya hanya membahas 2 buah algoritma, yaitu Sequential Search dan Binary Search.

a.       Sequential Search

Merupakan metode searching yang paling sederhana, karena metode ini bekerja dengan cara mencocokan tiap elemen didalam array. Hal ini tentunya sangat membuang waktu, terutama jika data yang ingin dicari ternyata tidak ada ataupun terletak pada indeks terakhir didalam array.

Studi kasus: buatlah program pencarian data menggunakan algoritma sequential search!

#include<iostream.h> #include<conio.h> void main() { int data[5],query; bool tanda=false; for(int i=0;i<5;i++) { cout << "Inputkan data pada indeks ke-" << i << " : "; cin >> data[i]; } cout<< "Inputkan data yang ingin dicari : " ; cin >> query; for(int i=0;i<5;i++) { if(data[i]==query) { tanda=true; cout << "Data ditemukan pada indeks ke -" << i << endl; } } if(tanda==false) cout << "Data tidak ditemukan !\n"; getch(); }

b.       Binary search

Merupakan metode searching yang jauh lebih baik dibandingkan dengan sequential search, namun binary search memiliki kelemahan, antara lain data harus diurutkan terlebih dahulu. Metode binary search ini bekerja seperti bilangan biner, yang mana membagi-bagi bilangan yang ingin dicari menjadi 2, berdasarkan rentang nilainya. Kemudian membagi lagi bilangan tersebut,dan mencari terus hingga data yang dicari ditemukan. Pencarian dengan metode binary search ini lebih efisien dibandingkan dengan sequential search, karena pada algoritma ini, data yang tidak ada hubungannya (range-nya) jauh dari data yang dicari akan dipisahkan dengan data yang ingin dicari.

Studi kasus: buatlah program pencarian data menggunakan algoritma binary search!

#include<stdio.h> #include<conio.h> #include<iostream.h> void main() { //deklarasi variabel int A[10],n, i,j,k,swap,kanan,kiri,center,tm; //proses penginputan data cout<<"Input jumlah data (maks 10) = "; cin>>n; for(i=0;i<n;i++) { cout<<"Masukkkan data ke - "<<(i+1)<<" = "; cin>>A[i]; } cout<<"Input query pencarian :"; cin>>k; //proses pengurutan data for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { if (A[i]>A[j]) { swap=A[i]; A[i]=A[j]; A[j]=swap; } } } //proses pencarian data tm=0; kanan=n; kiri=0; while(kanan>=kiri) { center=(kanan+kiri)/2; if(A[center]==k) { tm++; } if(A[center]<k) { kiri=center+1; } else { kanan=center-1; } } if (tm>0) { cout<<"Data " << k << " ditemukan didalam daftar!"<<endl; } //jika tidak ditemukan else { cout<<"Data tidak ditemukan :("<<endl; } getch(); }
Terimakasih, Sumber Materi : Dosen Praktikum Struktur Data STMIK STIKOM BALI, Ida Bagus Surya Arnawa

Struktur Data - Sorting

Artikel ini merupakan lanjutan dari artikel yang saya tulis sebelumnya, yaitu Queue

Sorting merupakan proses pengurutan data, baik dari kecil ke besar (ascending) maupun besar ke kecil (descending). Ada banyak algoritma proses pengurutan data ini, namun disini saya hanya membahas proses pengurutan data menggunakan algoritma insertion sort dan selection sort.

a.       Selection Sort

Selection sort dilakukan dengan cara mencari data terkecil kemudian dikumpulkan pada indeks teratas (pada model ascending) atau mencari data terbesar kemudian dikumpulkan pada indeks teratas ( pada model descending)

Skema Selection Sort

Data awal

                5 8 4 3

o   Fase 1

Temp = 5

Cek 5 kurang dari 8 ? dilewati

Cek 5 kurang dari 4 ? diswap , sehingga temp = 4

Cek 4 kurang dari 3 ? diswap, sehingga temp=3

Mengisi nilai temp ke indeks teratas, sehingga data pada fase 1 menjadi 3 8 5 4

o   Fase 2

Temp = 8

Cek 8 kurang dari 5 ? diswap, sehingga temp=5

Cek 4 kurang dari 5 ? diswap, sehingga temp=4

Mengisi nilai temp ke indeks ke 1 sehingga data pada fase 2 menjadi 3 4 8 5

o   Fase 3

Temp = 8

Cek 8 kurang dari 5 ? diswap, sehingga temp=5

Mengisi nilai temp ke indeks ke 3 sehingga data menjadi 3 4 8 5

Studi kasus : Buatlah Program untuk mengurutkan data menggunakan algoritma selection sort!

#include<iostream.h> #include<conio.h> int data[5],temp; void tukar(int a, int b) { int t; t=data[b]; data[b]=data[a]; data[a]=t; } void main() { for(int i=0;i<5;i++) { cout << "Inputkan data yang ingin diurutkan pada indeks ke-" << i << " : "; cin >> data[i]; } int pos,i,j; for(i=0;i<5;i++) { pos=i; for(j=i+1;j<5;j++) { if(data[j]<data[pos])pos=j; } if(pos!=i) tukar(pos,i); } cout<<"selection sort selesai !"<<endl; cout<<"Data : "<<endl; for(int i=0;i<5;i++) { cout<<data[i]<<" "; } cout<<endl; getch(); }

b.       Insertion Sort

Insertion Sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pososinya dengan cara melakukan perbandingan dengan data – data yang ada. Insertion sort ini bekerja seperti kita melakukan pengurutan kartu. Yaitu dengan cara menggeser geser kartu tersebut. Dan menyisipkan kartu dengan nilai tertentu.

Cara kerja algoritma ini :

Contoh  data Awal = 5 2 6 4
Maka :

• Temp=5
• Proses 1 = 2 5 6 4
• Proses 2 = 2 5 6 4
• Proses 3 = 2 4 5 6
• Selesai !

Studi kasus : Buatlah program pengurutan data insertion sort!

#include<iostream.h> #include<conio.h> int data[5],temp; void tukar(int a, int b) { int t; t=data[b]; data[b]=data[a]; data[a]=t; } void main() { for(int i=0;i<5;i++) { cout << "Inputkan data yang ingin diurutkan pada indeks ke-" << i << " : "; cin >> data[i]; } int temp,i,j; for(i=1;i<5;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; cout<<"Data : "<<endl; for(int i=0;i<5;i++) { cout<<data[i]<<" "; } cout<<endl; getch(); }

Terimakasih. Sumber : Materi Slide Power Point dan script C++ Dosen Matakuliah Praktikum Struktur Data STMIK STIKOM BALI, Ida Bagus Surya Arnawa