Algoritma Sorting & Searching C++

4 July 2010 at 22:08 (Algoritma & Metode OOP (C++))

Week 5 – Tugas Individu 5 – 0454T

1. Simulasikan pengurutan data di bawah dengan algoritma bubble sort dan selection sort

23 13 45 67 54 98 28 33 56 75

Jawaban:

Buble sort
Pass 1    23 13 45 67 54 98 28 33 56 75
13 23 45 67 54 98 28 33 56 75
13 23 45 67 54 98 28 33 56 75
13 23 45 67 54 98 28 33 56 75
13 23 45 54 67 98 28 33 56 75
13 23 45 54 67 98 28 33 56 75
13 23 45 54 67 28 98 33 56 75
13 23 45 54 67 28 33 98 56 75
13 23 45 54 67 28 33 56 98 75
13 23 45 54 67 28 33 56 75 98

Pass 2    13 23 45 54 67 28 33 56 75 98
13 23 45 54 67 28 33 56 75 98
13 23 45 54 67 28 33 56 75 98
13 23 45 54 67 28 33 56 75 98
13 23 45 54 67 28 33 56 75 98
13 23 45 54 28 67 33 56 75 98
13 23 45 54 28 33 67 56 75 98
13 23 45 54 28 33 56 67 75 98
13 23 45 54 28 33 56 67 75 98

Pass 3    13 23 45 54 28 33 56 67 75 98
13 23 45 54 28 33 56 67 75 98
13 23 45 54 28 33 56 67 75 98
13 23 45 54 28 33 56 67 75 98
13 23 45 28 54 33 56 67 75 98
13 23 45 28 33 54 56 67 75 98
13 23 45 28 33 54 56 67 75 98
13 23 45 28 33 54 56 67 75 98

Pass 4    13 23 45 28 33 54 56 67 75 98
13 23 45 28 33 54 56 67 75 98
13 23 45 28 33 54 56 67 75 98
13 23 28 45 33 54 56 67 75 98
13 23 28 33 45 54 56 67 75 98
13 23 28 33 45 54 56 67 75 98
13 23 28 33 45 54 56 67 75 98

Pass 5    13 23 28 33 45 54 56 67 75 98
13 23 28 33 45 54 56 67 75 98
13 23 28 33 45 54 56 67 75 98
13 23 28 33 45 54 56 67 75 98
13 23 28 33 45 54 56 67 75 98
13 23 28 33 45 54 56 67 75 98

Pass 6 s/d 9 sama dengan pass 5 karena sudah berurutan.
Hasil buble sort = 13 23 28 33 45 54 56 67 75 98

Selection sort
Inisial        23 13 45 67 54 98 28 33 56 75
After swap 1    23 13 45 67 54 28 33 56 75 98
After swap 2    23 13 45 67 54 28 33 56 75 98
After swap 3    23 13 45 56 54 28 33 67 75 98
After swap 4    23 13 45 33 54 28 56 67 75 98
After swap 5    23 13 45 33 28 54 56 67 75 98
After swap 6    23 13 28 33 45 54 56 67 75 98
After swap 7    23 13 28 33 45 54 56 67 75 98
After swap 8    23 13 28 33 45 54 56 67 75 98
After swap 9    13 23 28 33 45 54 56 67 75 98

Hasil selection sort = 13 23 28 33 45 54 56 67 75 98

2. Hasil pengurutan pada putaran pertama dengan algoritma bubble sort secara ascending dengan data 23 13 45 67 54  adalah:

  1. 13  23  45  54  67
  2. 13  23  45  67  54
  3. 23  13  45  54  67
  4. 23  13  45  67  54

Jawaban

Inisial    23 13 45 67 54
Pass 1    23 13 45 67 54
13 23 45 67 54
13 23 45 67 54
13 23 45 67 54
13 23 45 54 67
Hasil pass 1 adalah = a. 13 23 45 54 67

3. Hasil pengurutan pada putaran pertama dengan algoritma selection sort secara ascending dengan data no.2 adalah:

  1. 13  23  45  54  67
  2. 13  23  45  67  54
  3. 23  13  45  54  67
  4. 23  13  45  67  54

Jawaban

Inisial        23 13 45 67 54
After swap 1    23 13 45 54 67
Hasil swap 1 adalah =  c. 23 13 45 54 67

4. Hasil pengurutan pada putaran pertama dengan algoritma Insertion sort secara ascending dengan data 23 13 45 67 54  adalah:

  1. 13  23  45  54  67
  2. 13  23  45  67  54
  3. 23  13  45  54  67
  4. 23  13  45  67  54

Jawaban

Inisial        23 13 45 67 54
13 23 45 67 54
Hasil swap 1 adalah = a. 13 23 45 67 54

5.  Simulasikan pengurutan data di bawah dengan algoritma Quick sort

23  3 45 67 54 98 28 33 56 75

Jawaban

Pivot => biru
x<p => hijau
x>=p => merah
233 45 67 54 98 28 33 56 75
Patition P1    45 67 54 98 28 33 56 75 233
45 67 54 98 28 33 56 75
Partition    28 33 45 67 54 98 56 75
P1.1= 28 33
P1.2= 67 54 98 56 75

Partition P1.1    28 33
Partition P1.2    67 54 98 56 75
54 56 67 98 75
P1.2.1 = 54 56
P1.2.2 = 98 75

Partition P1.2.1    54 56
Partition P1.2.2    75 98

Merge P1.2.1 & P1.2.2     = 54 56 67 75 98
Merge P1.1 & P1.2       = 28 33 54 56 67 75 98
Merge P1        = 28 33 54 56 67 75 98 233

6. 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.

Jawaban programnya:

#include <iostream>

using namespace std;

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<<“======================================\n”;

cout<<“Program Quick Sorting secara Ascending\n”;

cout<<“======================================\n\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”);

}

7. 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:

  1. 0800700007, 2005 B
  2. 0800500015, 2004 B

Jawaban

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

a.    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

b.    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

8. 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

Jawaban

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

9. Buatlah program untuk mencari data dengan algoritma sequential search  dengan data pada soal nomor 8 di atas.

Jawaban Program

#include <iostream>

#include <string>

#include <cstring>

#include <iomanip>

using namespace std;

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};

cout << “\n===========================================================”;

cout<<“\n|”<<setw(13)<<“KODE |”;

cout<<setw(32)<<“NAMA |”<<setw(13)<<“HARGA |”<<endl;

cout << “===========================================================\n”;

for (int i=0; i<=10;i++)

{ cout<<“|”<<setw(11)<<kode[i]<<” |”;

cout<<setw(30)<<nama[i]<<” |”;

cout<<setw(11)<<harga[i]<<” |”<<endl; }

cout << “===========================================================\n”;

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”);

}

10. Buatlah program untuk mencari data dengan algoritma binary search dari soal nomor 7 di atas.

Jawaban Programnya:

#include <iostream>

#include <string>

#include <cstring>

#include <stdio.h>

#include <conio.h>

#include <iomanip>

using namespace std;

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};

cout << “\n    =======================================================”;

cout<<setw(4)<<“\n    “<<“|”<<setw(8)<<“SKS |”;

cout<<setw(20)<<“NIM |”;

cout<<setw(13)<<“IPK |”;

cout<<setw(13)<<“SEMESTER |”<<endl;

cout << ”    =======================================================\n”;

for (int i=0;i<=18;i++)

{ cout<<setw(4)<<i<<“|”<<setw(7)<<sks[i]<<“|”;//<<nim[i];

cout<<setw(19)<<nim[i]<<“|”;

cout<<setw(12)<<ipk[i]<<“|”;

cout<<setw(12)<<semester[i]<<“|”<<endl; }

cout << ”    =======================================================\n”;

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”);

}

Save to PDF

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: