NPM : 58414905
Kelas : 1IA17
Mata Kuliah : ALGORITMA DAN PEMROGAMAN 1 A
Dosen : Kunto Bayu A,ST.
1.Bubble Sort
Pengertian : Bubble Sort atau metode gelembung adalah metode pengurutan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai data terurut secara tepat dan sempurna.
Kelebihan Bubble sort :
- Metode Bubble sort adalah metode yang paling simpel
- Metode Bubble sort mudah dimengerti algoritmanya
Contoh Program Bubble Sort :
#include<iostream.h>
#include<conio.h>
void Selsort(int
X[], int SIZE)
{
int pos,small,temp;
for (int i=0;
i<SIZE-1; i++) {
small=X[i];
for (int j=i+1;
j<SIZE; j++)
{
if (X[j]<small)
{small=X[j];
pos=j;}
}
temp=X[i];
X[i]=X[pos];
X[pos]=temp;
} }
void main(void)
{ clrscr();
int A[10];
int size;
cout<<"\n Enter array size :";
cin>>size;
cout<<"\n Enter array elements :";
for (int i=0; i<size; i++)
{
cin>>A[i];
}
Selsort(A,size);
cout<<"\n The sorted array is as shown below :";
for (int l=0; l<size; l++)
{cout<<A[l];}
getch();
}
Contoh Gambar Bubble Sort :
2.Insertion Sort
Pengertian : Metode Literasi (pengulangan) yang menginsert atau menyisipkan setiap elemen ketempat yang sesuai(setelah dibandingkan dengan elemen kiri dan kanannya) atau kita bisa mengumpamakan metode ini seperti bermain kartu, yaitu satu demi satu akan menginsert ketempat yang sesuai.
Contoh Program Insertion Sort :
#include
<iostream.h>
#include
<conio.h>
#define ELEMENTS 6
void
insertion_sort(int x[], int length){
int key, i;
for(int j=0; j<length;j++){
key=x[j];
i=j-1;
while(x[i]>key&&i>=0){
x[i+1]=x[i];
i--;
}
x[i+1]=key;
}
}
int main(){
int A[ELEMENTS]={9,2,7,5,4,3};
int x;
cout<<"array yang belum di sort:";
for(x=0;x<ELEMENTS;x++){
cout<<A[x];
}
cout<<endl;
insertion_sort(A,ELEMENTS);
cout<<"Array yang sudah di sort:";
for(x=0;x<ELEMENTS;x++){
cout<<A[x];
}
getch();
return
0;
}
Contoh Gambar Insertion Sort :
3.Selection Sort
Pengertian : Yaitu memilih data yang akan diurutkan menjadi dua bagian, yang belum diurutkan, dan meja yang telah diurutkan. Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakan pada posisinya sesuai dengan bagian lain array yang telah di urutkan.Tahapan ini dilakukan secara berulang-ulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
Contoh Program Selection Sort :
#include
<conio.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<<"\n Hasil ketika Posawal = "<<posawal<<" : ";
tampilkan_larik(data,n);
}
}
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<<"\n masukkan data ke "<<a<<"
: ";
cin>>data[a];
}
selection_sort(data,n);
//hasil pengurutan
cout<<"\n\n hasil pengurutan : \n\n";
cout<<"
"; tampilkan_larik(data,n);
cout<<"\n
SORTING SELESAI...................";
getch();
clrscr();
cout<<"-----------------------";
cout<<"by: hamba Allah, 2014";
cout<<"-----------------------";
getch();
return 0;
}
Contoh Gambar Sction Sort :
4. Merge Sort
Pengertian : yaitu metode yang membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah.Setelah kedua buah list tersusun,maka akan dibentuk larik baru sebagai hasill penggabungan dari dua buah larik sebelumnya.Menurut keefektifannya, algoritma ini bekerja dengan tingkat keefektifan O(nlog(n)).
Contoh Program Merge Sort :
#include
<iostream.h>
#include
<stdio.h>
#include
<conio.h>
int data[100];
int d,e;
void mergeSort(int awal, int mid, int akhir)
{
cout<<endl;
int temp[100], tempAwal = awal, tempMid = mid, i = 0;
while(tempAwal < mid && tempMid < akhir)
{
if(data[tempAwal] < data[tempMid])
temp[i] = data[tempAwal],tempAwal++;
else
temp[i] = data[tempMid],tempMid++;
i++;
}
while(tempAwal < mid)
temp[i] = data[tempAwal],tempAwal++,i++;
while(tempMid < akhir)
temp[i] = data[tempMid],tempMid++,i++;
for(int j=0,k=awal;j<i,k<akhir;j++,k++)
cout<<data[k]<<' '<<temp[j]<<endl, data[k] = temp[j];
}
void merge(int awal, int akhir)
{
if(akhir-awal
!= 1)
{
int mid = (awal+akhir)/2;
merge(awal, mid);
merge(mid, akhir);
mergeSort(awal, mid, akhir);
}
}
int main()
{
int d,e;
int n;
cout<<"Masukan banya data = ";cin>>n;
cout<<"Masukan data yang akan di susun = ";
for(int i=0;i<n;i++)
cin>>data[i];
merge(0,n);
for(int i=0;i<n;i++)
cout<<data[i]<<' ';
getch();
return 0;
scanf("%d", d,e);
}
Contoh Gambar Merge Sort :
5. Heap Sort
Pengertian : Metode pengurutan data berdasarkan perbandingan.Walaupun metode ini lebih lambat daripada quick sort tapi heap sort memiliki keunggulan tersendiri yaitu pada kasus terburuknya adalah n log n.Heap Sort ini mengurutkan isi suatu larik masukan denganmemandang larik masukan sebagai suatu Complate Binary Tree(CBT).Lalu CBT ini dapat dikonversi menjadi suatu heap tree.Dan akhirnya CBT akan diubah menjadi suatu Priority Queue.
Contoh Program Heap Sort :
#include
<iostream.h>
#include
<stdio.h>
#include
<conio.h>
void read(int
a[10],int n)
{
cout<<"reading\n";
for(int i=0;i<n;i++)
cin>>a[i];
}
void display(int
a[10],int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<"\t";
}
void shellsort(int
a[10],int n)
{
int gap=n/2;
do
{
int swap;
do
{
swap=0;
for(int i=0;i<n-gap;i++)
if(a[i]>a[i+gap])
{
int t=a[i];
a[i]=a[i+gap];
a[i+gap]=t;
swap=1;
}
}
while(swap);
}
while(gap=gap/2);
}
void main()
{
int a[10];
int n;
clrscr();
cout<<"enter n\n";
cin>>n;
read(a,n);
cout<<"before sorting\n";
display(a,n);
shellsort(a,n);
cout<<"\nafter sorting\n";
display(a,n);
getch();
}
Contoh Gambar Heap Sort :
6. Quick Sort
Pengertian : Metode ini dimulai dengan menscan daftar yang disortir untuk nilai median.Nilai ini yang disebut tumpuan atau (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.
Contoh Program Quick Sort :
#include
<iostream.h>
#include
<conio.h>
#define max 20
void quick_sort(int darr[max], int lb, int ub)
{
int a;
int
up,down;
int
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);
}
void main()
{
int
arr[max];
int
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<<"\tdata ke- "<<i<<" : ";
cin>>arr[i];
}
quick_sort(arr,lb,ub);
cout<<"\nHasil pengurutan data: ";
for(i=0; i<n;i++)
cout<<" "<<arr[i];
cout<<"\n\nTekan sembarang tombol untuk keluar ";
getch();
}
Contoh Gambar Quick Sort :
7. Bucket Sort
Pengertian : Bucket sort adalah algoritma sorting yang bekerja dengan partisi array ke dalam jumlah terbatas sort.Setiap kotak ini kemudian diurutkan secara individual,baik menggunakan algoritma sorting yang berbeda ,atau dengan menerapkan algoritma bucket sort.Variasi dari metode ini disebut semacam hitungan tunggal buffered lebih cepat dan membutuhkan waktu sekitar yang sama untuk berjalan pada set data.
Contoh Program Bucket Sort :
#define NUMELTS 100
#include
<stdio.h>
#include
<iostream.h>
class element
{
public:
int value;
element *next;
element()
{
value=NULL;
next=NULL;
}
};
class bucket
{
public:
element
*firstElement;
bucket()
{
firstElement =
NULL;
}
};
void main()
{
int lowend=0;
int highend=100;
int interval=10;
const int noBuckets=(highend-lowend)/interval;
bucket
*buckets=new bucket[noBuckets];
bucket *temp;
for(int a=0;a<noBuckets;a++)
{
temp=new bucket;
buckets[a]=*temp;
}
cout<<"--------The Elements to be Sorted using Bucket sort are ------------------\n";
int array[]={12,2,22,33,44,55,66,77,85,87,81,83,89,82,88,86,84,88,99};
for(int j=0;j<19;j++)
{
cout<<array[j]<<endl;
element *temp,*pre;
temp=buckets[array[j]/interval].firstElement;
if(temp==NULL)
{
temp=new element;
buckets[array[j]/interval].firstElement=temp;
temp->value=array[j];
}
else
{
pre=NULL;
while(temp!=NULL)
{
if(temp->value>array[j])
break;
pre=temp;
temp=temp->next;
}
if(temp->value>array[j])
{
if(pre==NULL)
{
element *firstNode;
firstNode=new element();
firstNode->value=array[j];
firstNode->next=temp;
buckets[array[j]/interval].firstElement=firstNode;
}
else
{
element *firstNode;
firstNode=new element();
firstNode->value=array[j];
firstNode->next=temp;
pre->next=firstNode;
}
}
else
{
temp=new element;
pre->next=temp;
temp->value=array[j];
}
}
}
cout<<"------------------------The Sorted Elements Are---------------\n";
for(int jk=0;jk<10;jk++)
{
element *temp;
temp= buckets[jk].firstElement;
while(temp!=NULL)
{
cout<<"*"<<temp->value<<endl;
temp=temp->next;
}
}
cout<<"--------------------------------END--------------------------------\n";
}
Contoh Gambar Bucket Sort :
8.Radix Sort
Pengertian : Yaitu merupakan salah satu algoritma Non-Comparasion Sort (pengurutan tanpa pembandingan).Proses yang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu, dan tiap kategori dilakukan pengklasifikasian lagi,dan seterusnya sesuai kebutuhan, lalu subkategori tersebut digabungkan kembali. Metode ini pertama kalinya mengurutkan nilai-nilai input berdasarkan radix pertamanya,lalu pengurutan dilakukan bersarkan radix keduanya,dan begitu seterusnya. Pada sistem desimal radix adalah digit dalam angka desimal.
Contoh Program Radix Sort :
#include
<stdio.h>
#include
<conio.h>
#include
<stdlib.h>
kekosongan radix
(int a [], int n, int m){
typedef struct simpul
{
int data;
struct simpul *
berikutnya;
NODE};
Node * ptr, * awal, * prev;
Node * depan [10],
* belakang [10];
int k = 1, i, j, y,
p;;
/ * Membuat linked
list awal * /
mulai = NULL;
for (i = 0; i
<n; + + i)
{
ptr = (Node *)
malloc (sizeof (NODE));
ptr-> data = a
[i];
ptr-> next =
NULL;
if (mulai == NULL)
start = ptr;
lain
prev-> next =
ptr;
prev = ptr;
}
/ * Radix sort * /
for (i = 1; i <= m; + + i)
{
for (j = 0; j
<10; + + j)
depan [j] = NULL;
/ * Menempatkan elemen
ke antrian * /
ptr = mulai;
sementara (ptr! =
NULL)
{Y = ptr-> data
/ k% 10 ;/ * y adalah angka * /
jika (depan [y] ==
NULL)
{
depan [y] = ptr;
belakang [y] = ptr;
}
lain
{
belakang [y] ->
next = ptr;
belakang [y] = ptr;
}
ptr = ptr-> next;
}
mulai = NULL;
for (j = 0; j
<10; + + j)
jika (depan [j] =
NULL!)
{
if (mulai == NULL)
start = depan [j];
lain belakang [p]
-> next = depan [j];
p = j;
}
belakang [p] ->
next = NULL;
k = k * 10;
}
/ * Menyalin
kembali ke array * /
ptr = mulai;
for (i = 0; i
<n; + + i, ptr = ptr-> berikutnya)
a [i] = ptr->
data;
}
void main ()
{
int a [100], n, i,
m;
suhu arang;
melakukan
{
clrscr ();
printf
("=========================== RADIX SORT ==================
========================= \ n ");
printf ("ENTER
JUMLAH ANGKA DAN JUMLAH DIGIT \ n");
scanf ("% d%
d", & n, & m);
printf ("ENTER
UNSUR \ n");
for (i = 0; i
<n; + + i)
scanf ("%
d", & a [i]);
radix (a, n, m);
printf
("daftar diurutkan \ n");
for (i = 0; i
<n; + + i)
printf ("%
d", a [i]);
printf ("\
nAnda ingin melanjutkan [y / n]? \ n");
scanf ("%
c", & temp);
} Sementara (temp == 'y' | | temporer == 'Y');
printf ("\ n
---------------------------------------------
------------------------------------ \ n ");
getch ();
}
Contoh Gambar Radix Sort :
9.Shell Sort
Pengertian : shell sort mengacu pada algoritma sorting dimana data didistribusikan dari input untuk struktur peralihan beberapa yang kemudian dikumpulkan dan ditempelkan pada output.
Contoh Program Shell Sort :
#include<conio.h>
#include<iostream.h>
#define n 10
class shellsort{
static int A[n];
public:
void
InsSort(int start, int step);
void
ShellSort();
void
tampil();
};
int shellsort::A[n]={20,23,120,56,78,50,12,89,10,12};
void shellsort::InsSort(int start, int step)
{
int i,j,y;
bool ketemu;
i=start+step;
while(i<=n)
{
y=A[i];
j=i-step;
ketemu=false;
while((j>=0)&&(!ketemu))
{
if(y<A[j])
{
A[j+step]=A[j];
j=j-step;
}
else
ketemu=true;
}
A[j+step]=y;
i=i+step;
}
}
void shellsort::ShellSort()
{
int
step,start;
step=n;
while(step>1)
{
step=step/3+1;
for(start=1;start<=step;start++)
shellsort::InsSort(start,step);
}
}
void shellsort::tampil(){
for(int
a=0;a<10;a++)
{
cout<<A[a]<<" ";
}
cout<<endl<<endl;
}
void main()
{
shellsort x;
cout<<"PENGURUTAN SHELL"<<endl<<endl;
cout<<"Sebelum diurut : "<<endl<<"A = ";
x.tampil();
x.ShellSort();
cout<<"Setelah diurut : "<<endl<<"A = ";
x.tampil();
getch();
}
Contoh Gambar Shell Sort :
10. Shuffle Sort
Pengertian : shuffle sort memperkirakan distribusi barang yang akan di urutkan dengan memeriksa n/ 8item pertama. Semacam partisi distributif dengan mendekati median dan interpolasi linear dari minimum untuk median dan dari median untuk maksimal.
Contoh Program Shuffle Sort :
#include
<stdio.h>
#include
<stdlib.h>
#include
<time.h>
int main ()
{
int iSecret,
iGuess;
/* initialize random seed: */
srand (
time(NULL) );
/* generate secret number: */
iSecret =
rand() % 10 + 1;
do {
printf ("Guess the number (1 to 10): ");
scanf ("%d",&iGuess);
if (iSecret<iGuess) puts ("The secret number is lower");
else if (iSecret>iGuess) puts ("The secret number is higher");
} while
(iSecret!=iGuess);
puts ("Congratulations!");
return 0;
}
Contoh Gambar Shuffle Sort :
Referensi :
0 komentar:
Posting Komentar