Sorting & Searching
Sorting :
– Bubble sort
– Selection sort
– Insertion sort
– Quick sort
– Merge sort
Searching :
– Linear search
– Binary search
– interpolation search
Sorting adalah penyortiran atau memilih – milih, Pada struktur data sorting adalah sebuah metode untuk pengurutan data, misalnya dari yang terbesar ke data yang terkecil. Sorting di bagi menjadi dua tipe yaitu : Ascending dan Descending.
Sorting juga ada yang tipe sederhana dan menengah (sedikit rumit)
untuk yang sederhana : bubble sort, selection sort, insertion sort
untuk yang menengah (sedikit rumit) : Quick sort, merge sort.
1. Bubble sort :
void Bubble(int *DataArr, int n)
{
int i, j;
for(i=1; i<n; i++)
for(j=n-1; j>=i; j–)
if(DataArr[j-1] > DataArr[j])
Swap(&DataArr[j-1],&DataArr[j]);
}
2. Selection sort :
for(i=0; i<=N-2; i++){ /* N=number of data */
for(j=i; j<=N-1; j++){
Note the index of smallest value between A[j] s/d A[N-1],
Save it in variable k.
Swap A[i] with A[k].
}
}
3.Insertion sort
for(i=1; i<n; i++) {
x = A[i], insert x to its suitable place between A[0] and A[i-1].
}
4. Quick sort :
void QuickSort(int left, int right)
{
if(left < right){
//arrange elements R[left],…,R[right] that
//producing new sequence:
R[left],…,R[J-1] < R[J] and R[J+1],…,R[right] > R[J].
QuickSort(left, J-1);
QuickSort(J+1, right);
}
}
5. Merge sort :
Menyorting algoritma berdasarkan pada algoritma membagi dan mengatasi :
– Divide : membagi data masukan dalam dua himpunan penguraian
– Recur : memecah masalah yang terkait dengan subset
– Conquer : menggabungkan solusi untuk setiap bagiann dalam solusi
Searching adalah merupakan proses yang fundamental dalam pemograman, berguna menemukan data(nilai) tertentu di dalam sekumpulan data yang bertipe sama. Fungsi pencarian itu sendiri adalah untuk memvalidasi(mencocokan) data.
1. Linear search :
void main()
{
int ar[100],beg,mid,end,i,n,search;
clrscr();
cout<<“How many numbers in the array: “;
cin>>n;
cout<<“Enter “<<n<<” numbers in ascending order –> “;
for(i=0;i<n;i++)
cin>>ar[i];
beg=0;
end=n-1;
cout<<“Enter a number to search: “;
cin>>search;
while(beg<=end)
{
mid=(beg+end)/2;
if(ar[mid]==search)
{
cout<<“\nItem found at position “<<(mid+1);
getch();
}
if(search>ar[mid])
beg=mid+1;
else
end=mid-1;
}
cout<<“\nSorry! “<<search<<” doesnot found.”;
getch();
}
2. Binary search :
int data[10]={1,3,4,7,12,25,40,65,78,90};
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<<“masukan data yang ingin di cari= “;
cin>>cari;
hasil = binary_search(cari);
if(hasil==1)
{
cout<<“data ada!”<<endl;
}
else
if(hasil==0)
cout<<“data tidak ada!”<<endl;
getch();
}
3. Interpolation search :
int main(int argc, char *argv[]){
int tempFound = 0;
int kodeBarang[] = {101,102,201,301,401,402,501,601,602,701};
string namaBarang[] = {“Flashdisk Kingston”, “Flashdisk Data Traveler”, “RAM VGEN”,
“VGA ATI RADEON”, “Laptop Asus”, “Netbook HP”, “CD ROM”, “Mouse”,
“Keyboard”, “Monitor LG”};
int stokBarang[] = {5, 7, 8, 9, 2, 3, 4, 6, 4, 5};
string lokasiBarang[] = {“Rak 5B”, “Rak AA”, “Rak 12D”, “Rak B6”, “Rak VC7”, “Rak AB12”,
“Rak G23”, “Rak K9”, “Rak 5J”, “Rak D5”};
int kodeKunci;
cout << “\n\tMasukkan kode barang : “;
cin >> kodeKunci;
tempFound = interpolationSearch(kodeBarang, kodeKunci, (sizeof(kodeBarang)/4));
if(tempFound>=0){
cout << “\n\n\tBarang yang Anda cari ditemukan, berikut detailnya : ” <<endl;
cout << endl;
cout << “\tNama Barang : ” << namaBarang[tempFound] <<endl;
cout << “\tStok Barang : ” << stokBarang[tempFound] <<endl;
cout << “\tLokasi : ” << lokasiBarang[tempFound] <<endl <<endl;
cout << “\t”;
}else{
cout << “\n\n\tMohon maaf, barang yang Anda cari belum ada\n\t” <<endl;
}
system(“pause”);
return EXIT_SUCCESS;
}