1. Buatlah program untuk menginputkan sejumlah bilangan bulat misalnya N kemudian menampilkan bilangan yang sudah diinputkan tersebut dalam keadaan terurut secara ascending. Algoritma yang digunakan adalah Quick sort.
Coding:
#include <iostream.h>
inline void input(float *arr, int n)
{
for (int i=0; i<=n; i++)
{
cout<<“Masukkan bilangan ke-“<<i+1<<” : “;
cin>>arr[i];
}
}
inline void tampil(float *arr,int n)
{
cout<<“\nHasil Quick Sort adalah : “;
for (int i=0; i<=n; i++)
{ cout<<” “<<arr[i]; }
cout<<endl;
}
inline int partition(float *arr,int left,int right)
{
float pivot=arr[left];
int pindex=left;
for (int i=left+1; i<=right;i++)
{
if (arr[i]<pivot)
{
++pindex;
float temp=arr[i];
arr[i]=arr[pindex];
arr[pindex]=temp;
}
}
float temp=arr[left];
arr[left]=arr[pindex];
arr[pindex]=temp;
return pindex;
}
inline void quicksort(float *arr,int left,int right)
{
int pindex;
if (left<right)
{
pindex=partition(arr,left,right);
quicksort(arr,left,pindex-1);
quicksort(arr,pindex+1,right);
}
}
int main()
{
float arr[20];
int n;
cout<<“Jumlah bilangan yang akan di Quick Sort : “;
cin>>n;
input(arr,n-1);
quicksort(arr,0,n-1);
tampil(arr,n-1);
system(“pause”);
}
- 2. Simulasikan algoritma binary search terhadap kumpulan data ini
|
|
Sks | NIM | IPK | Semester |
|
[0] |
42 | 0800100001 | 3.23 | 2004 B |
|
[1] |
58 | 0800200002 | 2.25 | 2005 B |
|
[2] |
32 | 0800600006 | 3.17 | 2005 A |
|
[3] |
62 | 0800100001 | 2.90 | 2005 A |
|
[4] |
40 | 0800300003 | 3.34 | 2004 B |
|
[5] |
48 | 0800400004 | 2.54 | 2005 A |
|
[6] |
36 | 0800200002 | 2.47 | 2005 A |
|
[7] |
12 | 0800700007 | 1.78 | 2004 B |
|
[8] |
32 | 0800400004 | 2.72 | 2004 B |
|
[9] |
36 | 0800800008 | 2.23 | 2004 B |
|
[10] |
16 | 0800200002 | 2.89 | 2004 A |
|
[11] |
16 | 0800600006 | 3.34 | 2004 A |
|
[12] |
20 | 0800300003 | 3.16 | 2004 A |
|
[13] |
24 | 0800700007 | 1.87 | 2005 A |
|
[14] |
20 | 0800500005 | 3.57 | 2005 A |
|
[15] |
80 | 0800100001 | 3.04 | 2005 A |
|
[16] |
16 | 0800800008 | 2.45 | 2004 A |
|
[17] |
16 | 0800400004 | 2.93 | 2004 A |
|
[18] |
20 | 0800100001 | 2.78 | 2004 A |
untuk mencari data dengan key:
- 0800700007, 2005 B
- 0800500015, 2004 B
Jawab :
Data hasil urut
|
|
Sks | NIM | IPK | Semester |
|
1 |
20 | 800100001 | 2.78 | 2004 A |
|
2 |
16 | 800200002 | 2.89 | 2004 A |
|
3 |
20 | 800300003 | 3.16 | 2004 A |
|
4 |
16 | 800400004 | 2.93 | 2004 A |
|
5 |
16 | 800600006 | 3.34 | 2004 A |
|
6 |
16 | 800800008 | 2.45 | 2004 A |
|
7 |
42 | 800100001 | 3.23 | 2004 B |
|
8 |
40 | 800300003 | 3.34 | 2004 B |
|
9 |
32 | 800400004 | 2.72 | 2004 B |
|
10 |
12 | 800700007 | 1.78 | 2004 B |
|
11 |
36 | 800800008 | 2.23 | 2004 B |
|
12 |
62 | 800100001 | 2.9 | 2005 A |
|
13 |
80 | 800100001 | 3.04 | 2005 A |
|
14 |
36 | 800200002 | 2.47 | 2005 A |
|
15 |
48 | 800400004 | 2.54 | 2005 A |
|
16 |
20 | 800500005 | 3.57 | 2005 A |
|
17 |
32 | 800600006 | 3.17 | 2005 A |
|
18 |
24 | 800700007 | 1.87 | 2005 A |
|
19 |
58 | 800200002 | 2.25 | 2005 B |
- 0800700007, 2005 B
low=1 , high= 19
mid=(1+19)/ 2 = 10
data index 10 = 800700007, 2004 B
key > data index 10 maka low= 10+1 =11
mid=(11+19)/2 = 15
data index 15 = 800400004, 2005 B
key>data index 15 maka low=15+1=16
mid = (16+19)/2= 17,5=>17
data index 17 = 800600006, 2005 A
key>data index 17 maka low=17+1=18
mid=(18+19)/2=18,5=>18
data index 18 = 0800700007, 2005 B = key
data ada di urutan ke 18
- 0800500015, 2004 B
low=1 , high= 19
mid=(1+19)/ 2 = 10
data index 10 = 800700007, 2004 B
key < data index 10 maka hight= 10-1 =9
mid=(1+9)/2=5
data index 5 = 800600006, 2004 A
key<data index 5 maka height=5-1=4
mid=(1+4)/2=2,5=>2
data index 2 = 800200002, 2004 A
key > data index 2 maka low = 2+1=3
mid=(3+4)/2=3,5=>3
data index 3 = 800300003, 2004 A
key> data index 3 maka low = 3+1 =4
mid=(4+4)/2=4
data index 4 = 800400004,2004 A
key > data index 4 maka low = 4+1=5
low>=height maka stop
data key tidak ditemukan
- 3. Simulasikan binary search terhadap kumpulan data ini
|
|
Kode | Nama | Harga |
|
[0] |
PRN204 | HP Laserjet 1220 | 468 |
|
[1] |
MTB512 | ABIT KT7-A RAID | 102 |
|
[2] |
HDD630 | Maxtor 160 GB | 285 |
|
[3] |
PRN202 | HP Laserjet 4100N | 1456 |
|
[4] |
CDR054 | Lite On 52X | 24 |
|
[5] |
MNT308 | Viewsonic E70 | 192 |
|
[6] |
MTB348 | ASUS A7V266: | 140 |
|
[7] |
HDD720 | Seagate 18GB Barracuda | 181 |
|
[8] |
CDR045 | Aopen 48x | 71 |
|
[9] |
MNT700 | LG Flatron 775FT | 225 |
|
[10] |
RAM114 | Visipro 512 MB | 68 |
untuk mencari PRN204, HDD770, CDR045, MT007
jawab:
hasil sort
|
|
Kode | Nama | Harga |
|
1 |
CDR045 | Aopen 48x | 71 |
|
2 |
CDR054 | Lite On 52X | 24 |
|
3 |
HDD630 | Maxtor 160 GB | 285 |
|
4 |
HDD720 | Seagate 18GB Barracuda | 181 |
|
5 |
MNT308 | Viewsonic E70 | 192 |
|
6 |
MNT700 | LG Flatron 775FT | 225 |
|
7 |
MTB348 | ASUS A7V266: | 140 |
|
8 |
MTB512 | ABIT KT7-A RAID | 102 |
|
9 |
PRN202 | HP Laserjet 4100N | 1456 |
|
10 |
PRN204 | HP Laserjet 1220 | 468 |
|
11 |
RAM114 | Visipro 512 MB | 68 |
Key = PRN204
Low=1, height=11
Mid=(1+11)/2=6
Data ke 6= MNT700
Key > data ke 6 maka low = 6+1=7
Mid=(7+11)/2=9
Data ke 9 = PRN202
Key > data ke 9 maka low = 9+1=10
Mid=(10+11)/2=10,5=>10
Data ke 10 = PRN204
Data ditemukan
Key = HDD770
Low=1, height=11
Mid=(1+11)/2=6
Data ke 6= MNT700
Key < data ke 6 maka height = 6-1=5
Mid=(1+5)/2=3
Data ke 3 = HDD630
Key> data ke 3 maka low=3+1=4
Mid=(4+5)/2=4,5=>4
Data ke 3 = HDD720
Key> data ke 4 maka low=4+1=5
Low>=height maka data tidak ditemukan
Key = CDR045
Low=1, height=11
Mid=(1+11)/2=6
Data ke 6= MNT700
Key < data ke 6 maka height = 6-1=5
Mid=(1+5)/2=3
Data ke 3 = HDD630
Key< data ke 3 maka height=3-1=2
Mid=(1+2)/2=1,5=>1
Data ke 1 = CDR045 data ditemukan
Key = MT007
Low=1, height=11
Mid=(1+11)/2=6
Data ke 6= MNT700
Key > data ke 6 maka low = 6+1=7
Mid = (7+11)/2=9
Data ke 9 = PRN202
Key< data ke 9 maka height = 9-1=8
Mid =(7+8)/2=7,5=>7
Data ke 7 = MTB348
Key < data ke 7 maka height=8-1=7
Mid=(7+7)/2=7
Data Data ke 7 = MTB348
Key < data ke 7 maka height=7-1=6
Low>=height maka data tidak ditemukan
- 4. Buatlah program untuk mencari data dengan algoritma sequential search dengan data pada soal nomor 8 di atas.
Jawab:
Code:
#include <iostream.h>
#include <string>
#include <cstring>
inline int SequentialSearch(char kode[11][7], char key[7])
{
int idx=(-1);
for (int i=0; i<=10; i++)
{
if ( strcmp(key,kode[i])==0)
{ idx=i; }
}
return idx;
}
int main()
{
char key[7]=”123456″;
int val;
char kode[11][7]={“CDR045″,”CDR054″,”HDD630″,”HDD720″,”MNT308″,”MNT700″,”MTB348″,”MTB512″,”PRN202″,”PRN204″,”RAM114”};
char nama[11][23]={“Aopen 48x”,”Lite On 52X”,”Maxtor 160 GB”,”Seagate 18GB Barracuda”,”Viewsonic E70″,”LG Flatron 775FT”,”ASUS A7V266″,”ABIT KT7-A RAID”,”HP Laserjet 4100N”,”HP Laserjet 1220″,”Visipro 512 MB”};
float harga[11]={71,24,285,181,192,225,140,102,1456,468,68};
for (int i=0; i<=10;i++)
{ cout<<kode[i]<<” “<<nama[i]<<” “<<harga[i]<<endl; }
cout<<“\nMasukkan key : “;
cin>>key;
val=SequentialSearch(kode, key);
if (val==-1)
{ cout<<“\nData tidak ditemukan”; }
else
{
cout<<“\nData ditemukan : “;
cout<<“\nKode : “<<kode[val];
cout<<“\nNama : “<<nama[val];
cout<<“\nHarga : “<<harga[val]<<endl;
}
system(“pause”);
}
- 5. Buatlah program untuk mencari data dengan algoritma binary search dari soal nomor 7 di atas.
Coding:
#include <iostream.h>
#include <string>
#include <cstring>
#include <stdio.h>
#include <conio.h>
inline int BinarySearch(char nim[19][10],char semester[19][6], char key1[10],char key2[6], int low, int height)
{
int mid,idx=(-1);
while (low <= height)
{
char append1[16]=””;
char append2[16]=””;
mid = (int)(low + height)/2;
strcat(append1,nim[mid]);
strcat(append1,semester[mid]);
strcat(append2,key1);
strcat(append2,key2);
if (strcmp(append2,append1)==0)
{ idx=mid; return idx;}
if (strcmp(append2,append1)>0)
{ low = mid + 1; }
if (strcmp(append2,append1)<0)
{ height = mid – 1; }
}
return idx;
}
int main()
{
char key1[10]=”123456789″;
char key2[6]=”12345″;
int val;
char nim[19][10]={“800100001″,”800100001″,”800100001″,”800100001″,”800200002″,”800200002″,”800200002″,”800300003″,”800300003″,”800400004″,”800400004″,”800400004″,”800500005″,”800600006″,”800600006″,”800700007″,”800700007″,”800800008″,”800800008”};
char semester[19][6]={“2004A”,”2004B”,”2005A”,”2005A”,”2004A”,”2005A”,”2005B”,”2004A”,”2004B”,”2004A”,”2004B”,”2005A”,”2005A”,”2004A”,”2005A”,”2004B”,”2005A”,”2004A”,”2004B”};
float ipk[19]={2.78,3.23,2.9,3.04,2.89,2.47,2.25,3.16,3.34,2.93,2.72,2.54,3.57,3.34,3.17,1.78,1.87,2.45,2.23};
float sks[19]={20,42,62,80,16,36,58,20,40,16,32,48,20,16,32,12,24,16,36};
for (int i=0;i<=19;i++)
{ cout<<i<<” “<<nim[i]<<” “<<semester[i]<<” “<<ipk[i]<<” “<<sks[i]<<endl; }
cout<<“Masukkan NIM : “; cin>>key1;
cout<<“Masukkan semester : “; cin>>key2;
val=BinarySearch(nim,semester,key1,key2, 0, 18);
if (val== (-1))
{ cout<<“\nData tidak ada”; }
else
{
cout<<“NIM : “<<nim[val]<<endl;
cout<<“Semester : “<<semester[val]<<endl;
cout<<“IPK : “<<ipk[val]<<endl;
cout<<“SKS : “<<sks[val]<<endl;
}
system(“pause”);
}