Program Sorting, Searching dalam C++ dan Tugas Metode Greedy

Buat Program Sorting dan Searching dalam C++

* SORTING

1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Marge Sort

* SEARCHING

1. Linier/Sequential Search
2. Binary Search

* MaxMin

1. StraitMaxMin
2. Divide and Conquer ( D & C )

Jawab :

#Sorting :

1. Selection Sort

#include "conio.h"
#include "stdio.h"

int main()
{
int i, j, iMin;
int n, Urut;
int Tmp, code;
int Arr[100];

printf("\nInputkan banyak data yang akan diurutkan : ");
scanf("%i", &n);
Urut = 1;
for(i = 0; i < n; i++) {
printf("Masukan data ke %i : ", i + 1);
scanf("%i", &Arr[i]);
}
for(i = 0; i < n - 1; i++) {
iMin = i;
for(j = Urut; j < n; j++) {
if(Arr[j] < Arr[iMin]) {
iMin = j;
if(Arr[i] != Arr[iMin]) {
Tmp = Arr[i];
if(Arr[i] > Arr[iMin]) {
Arr[i] = Arr[iMin];
Arr[iMin] = Tmp;
}
}
}
}
Urut = Urut + 1;
}
printf("\nSetelah Pengurutan\n");
for(i = 0; i < n; i++) {
printf("Elemen ke %i : %i\n", i + 1, Arr[i]);
}
getch();
}

Saat di tampilkan :

2. Bubble Sort

#include<conio.h>
#include<stdio.h>

int main()
{
int i, j, iMin;
int n, Urut;
int Tmp, code;
int Arr[100];
printf("\nInputkan banyak data yang akan diurutkan : ");
scanf("%i", &n);
for(i = 0; i < n; i++) {
printf("Masukan data ke %i : ", i + 1);
scanf("%i", &Arr[i]);
}
for(i = 1; i < n; i++) {
for(j = 0; j < n - 1; j++) {
if(Arr[j] > Arr[j + 1]) {
Tmp = Arr[j];
Arr[j] = Arr[j + 1];
Arr[j + 1] = Tmp;
}
}
}
printf("\nSetelah Pengurutan\n");
for(i = 0; i < n; i++) {
printf("Elemen ke %i : %i\n", i + 1, Arr[i]);
}
getch();
}

Saat di tampilkan :

3. Insertion Sort

#include "conio.h"
#include "stdio.h"

int main()
{
int i, j, iMin;
int n, Urut;
int Tmp, code;
int Arr[100];
printf("\nInputkan banyak data yang akan diurutkan : ");
scanf("%i", &n);
for(i = 0; i < n; i++)
{
printf("Masukan data ke %i : ", i + 1);
scanf("%i", &Arr[i]);
}
for(i = 1; i < n; i++)
{
Tmp = Arr[i];
j = i - 1;
while(Arr[j] >= Tmp && j > 0) {
Arr[j + 1] = Arr[j];
j = j - 1;
}
if(Tmp >= Arr[j]) {
Arr[j + 1] = Tmp;
} else {
Arr[j + 1] = Arr[j];
Arr[j] = Tmp;
}
}
printf("\nSetelah Pengurutan\n");
for(i = 0; i < n; i++) {
printf("Elemen ke %i : %i\n", i + 1, Arr[i]);
}
getch( );
}

Saat di tampilkan :

4. Marge Sort

#include <stdio.h>

#include <conio.h>

#define MAX 10

int Data[MAX];

int temp[MAX];

// Prosedur merge sort

void merge(int Data[], int temp[], int kiri, int tengah, int kanan)

{

int i, left_end, num_elements, tmp_pos;

left_end = tengah - 1;

tmp_pos = kiri;

num_elements = kanan - kiri + 1;

while ((kiri <= left_end) && (tengah <= kanan))

{

if (Data[kiri] <= Data[tengah])

{

temp[tmp_pos] = Data[kiri];

tmp_pos = tmp_pos + 1;

kiri = kiri +1;

}

else

{

temp[tmp_pos] = Data[tengah];

tmp_pos = tmp_pos + 1;

tengah = tengah + 1;

}

}

while (kiri <= left_end)

{

temp[tmp_pos] = Data[kiri];

kiri = kiri + 1;

tmp_pos = tmp_pos + 1;

}

while (tengah <= kanan)

{

temp[tmp_pos] = Data[tengah];

tengah = tengah + 1;

tmp_pos = tmp_pos + 1;

}

for (i=0; i <= num_elements; i++)

{

Data[kanan] = temp[kanan];

kanan = kanan - 1;

}

}

// Prosedur membuat kumpulan data

void m_sort(int Data[], int temp[], int kiri, int kanan)

{

int tengah;

if (kanan > kiri)

{

tengah = (kanan + kiri) / 2;

m_sort(Data, temp, kiri, tengah);

m_sort(Data, temp, tengah+1, kanan);

merge(Data, temp, kiri, tengah+1, kanan);

}

}

void mergeSort(int Data[], int temp[], int array_size)

{

m_sort(Data, temp, 0, array_size - 1);

}

int main()

{

int i;

printf("Masukkan DATA SEBELUM TERURUT : \n");

for (i = 0; i < MAX; i++)

{

printf ("Data ke %i : ", i+1);

scanf ("%d", &Data[i]);

}

mergeSort(Data, temp, MAX);

printf("\nDATA SETELAH TERURUT : ");

for (i = 0; i < MAX; i++)

printf("%d  ", Data[i]);

printf("\n");

//scanf("%d");

getch();

return(0);

}

Saat di tampilkan : 

#Searching:

1. Linier/Sequential Search

#include <iostream.h>

#include <conio.h>

void main()

{

int i;

int cari,ketemu;

int A[100]  ;

cout<<"PROGRAM SEARCHING\n";

cout<<"masukkan 7 buah data : \n\n";

for (i=1;i<=7;i++)

{

cout<<"masukkan data ke-"<<i<<endl;

cin>>A[i] ;

}

cout<<endl;

cout<<"Input bilangan yang dicari : ";

cin>>cari;

ketemu=0;

for(i=0;i<=7;i++)

{

if (A[i]==cari)

{

ketemu=1;

cout<<"Data ditemukan pada indeks ke-"<<i;

}

}

if (ketemu==0){

cout<<"Data tidak ditemukan";

}

 getch();

}

Saat di tampilkan : 

2. Binary Search

#include <iostream.h>

#include <conio.h>

main ()

{

int jd, cari,no, kiri,kanan,tengah,data[50];

cout<<" Input Jumlah Data  : ";

cin>>jd;

cout<<endl;

for (no=0;no<jd;no++)

{

cout<<" Input Data Ke-"<<(no+1)<<"    : ";

cin>>data[no];

}

cout<<endl;

cout<<" Input Nilai Dicari : ";

cin>>cari;

kiri=0;

kanan=jd-1;

tengah=(kanan-kiri)/2;

while ((data[tengah]!=cari) && (kiri>=0)&& (kanan<jd) && (kanan>=kiri))

{

if (cari>data[tengah])

{

kiri=tengah+1;

}

else if (cari<data[tengah])

{

kanan=tengah-1;

}

tengah=kiri+(kanan-kiri)/2;

}

cout<<endl;

if (data[tengah]==cari)

{

cout<<" Keterangan         : Data Ditemukan";

}

else

{

cout<<" Keterangan         : Data Tidak Ditemukan";

}

getch();

}

Saat di tampilkan : 

#MaxMin :

1. StraitMaxMin

#include <conio.h>

#include <iostream.h>

main()

{

int N, i, A[100], max, min;

cout<<" Input ukuran array (max 100) : ";

cin>>N;

cout<<"\n Input elemen-elemen array.. \n ";

for(i=0;i<=N-1;i++)

{

cout<<" elemen ke-"<<(i+1)<<" = ";

cin>>A[i];

}

max=min=A[0];

for(i=1;i<=N-1;i++)

{

if(A[i]>max)

max=A[i];

else if(A[i]<min)

min=A[i];

}

cout<<"\n Elemen terbesarnya adalah "<<max;

cout<<"\n Elemen terkecilnya adalah "<<min;

getch();

}

Saat di tampilkan : 

2. Divide And Conquer ( D & C )

#include<stdio.h>

#include<conio.h>

#include<iostream.h>

int max, min;

int a[100];

void maxmin(int i, int j)

{

int max1, min1, mid;

if(i==j)

{

max = min = a[i];

}

else

{

if(i == j-1)

{

if(a[i] <a[j])

{

max = a[j];

min = a[i];

}

else

{

max = a[i];

min = a[j];

}

}

else

{

mid = (i+j)/2;

maxmin(i, mid);

max1 = max; min1 = min;

maxmin(mid+1, j);

if(max <max1)

max = max1;

if(min > min1)

min = min1;

}

}

}

void main ()

{

int i, num;

clrscr();

printf ("\n\t\t\tMAXIMUM & MINIMUM\n\n");

printf ("\nInput ukuran array  : ");

scanf ("%d",&num);

printf ("Input elemen-elemen array : \n");

for (i=1;i<=num;i++)

{

scanf ("%d",&a[i]);

}

max = a[0];

min = a[0];

maxmin(1, num);

printf ("Elemen terbesarnya adalah : %d\n", max);

printf ("Elemen terkecilnya adalah : %d\n", min);

getch();

}

Saat di tampilkan : 

TUGAS METODE GREEDY

Sebuah Truk dengan kapasitas 240 Kg akan memuat hasil laut yang terdiri dari :

1. 120 Kg Udang seharga Rp. 60 juta
2. 100 Kg Kerang seharga Rp. 80 Juta
3. 150 Kg Ikan Tuna seharga Rp. 50 Juta

Tentukan kemungkinan kombinasi hasil laut yang dapat dimuat sedemikian sehingga mendapat hasil optimal. Hitung juga profit Maksimal yang didapat dari kombinasi yang optimal tersebut.

Gunakan 2 metode : Pendekatan Matematika dan Kriteria Greedy!!

Jawab :

- Fasible Solution

1. Untuk X1=0, X2=1, X3=?

   120.X1+100.X2+150.X3≤240

   120.0+100.1+150X3≤240

   150X3≤240-100

   X3=140/150=14/15

2. Untuk X1=1, X2=0, X3=?

   120.X1+100.X2+150.X3≤240

   120.1+100.0+150X3≤240

   150X3≤240-120

   X3=120/150=8/10=4/5

3. Untuk X1=1, X3=0, X2=?

   120.X1+100.X2+150X3≤240

   120.1+100X2+150.0≤240

   100X2≤240-120

   X2=120/100=6/5

4. Untuk X1=0, X3=1, X2=?

   120.X1+100.X2+150.X3≤240

   120.0+100X2+150.1≤240

   100X2≤240-150

   X2=90/100=9/10

5. Untuk X2=1, X3=0, X1=?

   120.X1+100.X2+150.X3≤240

   120X1+100.1+150.0≤240

   120X1≤240-100

   X1=140/120=7/6

6. Untuk X2=0, X3=1, X1=?

   120.X1+100.X2+150.X3≤240

   120X1+100.0+150.1≤240

   120X1≤240-150

   X1=90/120=3/4

Tabel feasible solution Knapsack dengan pendekatan matematika

Solusi Ke -	(X1, X2, X3)	∑ Wi Xi	∑ Pi Xi
1	(0, 1, 14/15)	240	126.6
2	(1, 0 , 4/5)	240	100
3	(1, 6/5, 0)	240	156 -> Profit max
4	(0, 9/10, 1)	240	122
5	(7/6, 1, 0)	240	150
6	(3/4, 0, 1)	240	95

- Kesimpulan yang dapat diambil adalah : komposisi dari ketiga barang yang dapat termuat dalam ransel dengan profit maksimal 156 adalah :

- Barang jenis I tidak dimuat (X1=1)                          = 120 Kg.

- Barang jenis II dimuat seluruhnya (X2=6/5)            = 100 Kg.

- Barang jenis III dimuat sebagian (X3=0)                 = 0 Kg.

- Total Maksimal Kapasitas Knapsack adalah            = 240 Kg.

  Kriteria Greedy

Diketahui bahwa kapasita M = 240Kg,

Dengan jumlah barang n=3

- Berat Wi masing-masing barang

  (W1,W2,W3)=(120,100,150)

- Nilai Pi masing-masing barang

  (P1,P2,P3)=(60,80,50)

Barang dengan Nilai Profit Maksimal

- P1=60 -> X1=1

- P2=80 -> X2=0

- P3=50 -> X3=4/5

Barang dengan Berat Minimal

- W1=120 -> X1=3/4

- W2=100 -> X2=0

- W3=150 -> X3=1

barang dgn menghitung perbandingan yg terbesar drProfit dibagi Berat (Pi/Wi) yg diurut secara tidak naik,yaitu:

- P1/W1=60/120 -> karena terkecil maka X1=0

- P2/W2=80/100 -> karena terbesar maka X2=1

- P3/W3=50/150 -> denganFungsipembatas X3=6/5

Penyelesaian Kriteria Greedy

Solusi Ke	(X1,X2,X3)	∑ Wi Xi	∑ Pi Xi
Pi Max	(1, 0 , 4/5)	240	100
Wi Min	(3/4, 0, 1)	240	95
Pi/Wi Max	(1, 6/5, 0)	240	156

Nilai profit maksimal = 156 dengan komposisi yang sama.