1. Jelaskan pengertian Device and Conquer serta tujuannya?
Jawabannya:
Algoritma Divide and Conquer merupakan algoritma yang sangat popular di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.
Divide : membagi masalah menjadi beberapa masalah yang memiliki kemiripan dengan
masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
Conquer : memecahkan (menyelesaikan) masing-masing masalah (secara rekursif), dan
Combine : mengabungkan solusi masing-masing masalah sehingga membentuk solusi masalah
semula.
2. Sebutkan algoritma metode sorting!
a. Selection Sort
b. Bubble Sort
c. Merge Sort
d. Quick Sort
e. Insertion Sort
Jawabannya:
a. #include<constrea.h>
#include<stdio.h>
void tampilkan_larik(int data[],int n)
{
int i;
for(i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<endl<<endl;
}
void selection_sort(int data[],int n)
{
int posmin,posawal,j,tmp;
for(posawal=0;posawal<n-1;posawal++)
{
posmin=posawal;
for(j=posawal+1;j<n;j++)
if(data[posmin]>data[j])
posmin=j;
//tukarkan
tmp=data[posawal];
data[posawal]=data[posmin];
data [posmin]=tmp;
cout<<"\nHasil Ketika Posawal = "<<posawal<<":";
tampilkan_larik(data,n);
}
}
//global
int main()
{
int data[50],i,n;
cout<<"\n@Simulasi Selection Sort@\n\n\n";
cout<<"==================================\n";
cout<<" Masukkan Banyak Data : ";cin>>n;
clrscr();
for(int a=0;a<n;a++)
{cout<<"\nMasukkan Data Ke "<<a<<":";cin>>data[a];}
selection_sort(data,n);
//hasil pengurutan
cout<<"\n\nHasil Pengurutan : \n\n";
cout<<" ";tampilkan_larik(data,n);
cout<<"\nSorting Selesai....";
getch();
}
b. #include<constrea.h>
#include<stdio.h>
int data[10],data2[10];
int n;
void tukar(int a,int b)
{
int t;
t=data[b];
data[b]=data[a];
data[a]=t;
}
void bubble_sort()
{
for(int i=1;i<n;i++)
{
for(int j=n;j>=i;j--)
{
if(data[j]<data[j-i])tukar(j,j-i);
}
}
}
void main()
{
cout<<"===Program Bubble Sort==="<<endl;
//input data
cout<<"Masukkan Jumlah Data : ";cin>>n;
for(int i=1;i<n;i++)
{
cout<<"\nMasukkan Data Ke "<<i<<":";cin>>data[i];
data2[i]=data[i];
}
bubble_sort();
cout<<"\n\n";
//tampilkan data
cout<<"Data setelah di sort : ";
for(int i=1;i<=n;i++)
{
cout<<" "<<data[i];
}
cout<<"\nSorting Selesai....";
getch();
}
c. #include<constrea.h>
//using namespace std
void merge(int low,int id,int up);
void mergeSort(int low,int up);
int a[50];
int main()
{
int jumlahBil,i;
cout<<"Masukkan Jumlah Elemen Array"<<endl;cin>>jumlahBil;
for(int i=0;i<jumlahBil;i++)
{
cout<<"Bilangan Ke - "<<i+1<<endl;cin>>a[i];
}
mergeSort(1,jumlahBil);
for(i=1;i<=jumlahBil;i++)
cout<<a[i]<<" ";
cout<<endl;
getch();
}
void merge(int low,int mid,int up)
{
int h,i,j,k;
int b[50];
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=up))
{
if(a[h]<a[j])
{
b[i]=a[h];h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=up;k++)
{b[i]=a[k];i++;}
}
else
{for(k=h;k<=mid;k++)
{b[i]=a[k];i++;}
}
for(k=low;k<=up;k++)a[k]=b[k];
}
void mergeSort(int low,int up)
{
int mid;
if(low<up)
{
mid=(low+up)/2;
mergeSort(low,mid);
mergeSort(mid+1,up);
merge(low,mid,up);
}
}
d. #include<constrea>
#define max 30
void quick_sort(int darr[max],int lb,int ub)
{
int a,up,down,temp;
if(lb>=ub)
return;
a=darr[lb];
up=ub;
down=lb;
while(down<up)
{
while(darr[down]<=a)
down++;
while(darr[up]>a)
up--;
if(down<up)
{
temp=darr[down];
darr[down]=darr[up];
darr[up]=temp;
}}
darr[lb]=darr[up];
darr[up]=a;
quick_sort(darr,lb,up-1);
quick_sort(darr,up+1,ub);
}
main()
{
int arr[max],i,n,lb,ub;
lb=0;
cout<<"masukkan banyak data yang ingin diurut = ";cin>>n;
ub=n;
cout<<"masukkan data-datanya :\n\n";
for(i=1;i<=n;i++)
{
cout<<"data ke-"<<i<<" : ";cin>>arr[i];
}
quick_sort(arr,lb,ub);
cout<<"\nhasil pengurutan data :";
for(i=1;i<=n;i++)
cout<<" "<<arr[i];
getch();
}
e. #include<constrea.h>
int data[10],data2[10];
int n;
void insertion_sort()
{
int temp,i,j;
for(i=1;i<n;i++)
{
temp=data[i];
j=i-1;
while(data[j]>temp&&j>=0)
{
data[j+1]=data[j];
j--;
}
data[j+1]=temp;
}
}
void main()
{
cout<<"===Program Insertion Sort==="<<endl;
//input data
cout<<"Masukkan jumlah data : ";cin>>n;
for(int i=1;i<n;i++)
{
cout<<"Masukkan data ke "<<i<<":";cin>>data[i];
data2[i]=data[i];
}
insertion_sort();
cout<<"\n\n";
//tampilkan data
cout<<"\nData setelah di sort : ";
{
for(int i=1;i<=n;i++)
cout<<" "<<data[i];
}
cout<<"\n\nsorting selesai";
getch();
}
3. Terdapat deret angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.
Urutkan dengan seluruh teknik sorting yang ada!
Jawaban:
a. Selection sort
b. Bubble Sort
c. Merge Sort
a. Quick Sort
b. Insertion sort
4. Terdapat deret angka : 12, 45, 10, 55, 32, 81, 59, 21, 16, 71, 40, 90
Urutkan dengan seluruh teknik sorting yang ada!
Jawaban:
a. Selection Sort
b. Bubble Sort
c. Merge Sort
d. Quick Sort
e. Insertion Sort
