Macam-Macam Bentuk Pensortiran Algoritma
Nama : Irfan Fadhil
NPM : 55414434
Kelas : 1IA17
Mata Kuliah : Algoritma & Pemrograman 1A
Dosen : Kunto Bayu A. ST.
Sorting / pengurutan biasanya dilakukan untuk tujuan mempermudah pencarian. Pengurutan data baik dari segi ascending (dari nilai terkecil ke terbesar) atau descending (dari nilai terbesar ke terkeci). Ketika akan melakukan sortir di komputer, maka hal-hal yang akan mempertimbangkan, meliputi :
1. Perlu tidaknya data disortir
2. Besarnya atau banyaknya data yang akan disortir
3. Kemampuan atau kapasitas computer atau media penyimpanan data
4. Metode sortir
Teknik sortir sangat erat kaitannya dengan proses perbandingan dan penukaran tempat antar elemen data. Waktu terbaik akan diperoleh ketika susunan elemen datanya sudah sama dengan susunan yang diinginkan melalui sortirnya. Waktu terburuk akan didapatkan ketika susunan elemen – elemen datanya terbalik dari susunan yang dikehendaki sortirnya. Waktu rata-rata diperoleh dengan memperhitungkan berbagai susunan bentuk elemen-elemen datanya.
1. Bubble Sort
Bubble Sort atau metode gelembung adalah metode pengurutan dengan cara melakukan penukaran data dengan tempat disebelahnya jika data sebelum lebih besar dari pada data sesudahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan, atau telah terurut dengan benar. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci atau data akan dengan lambat menggelembung atau membandingan data ke posisinya yang tepat.
Metode ini mudah dipahami dan diprogram, tetapi bila dibandingkan dengan metode lain yang kita pelajari, metode ini merupakan metode yang paling tidak efisien karena memiliki banyak pertukara sehingga memerlukan pengalokasian memori yang besar untuk menjalankan metode ini.
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 Cara Kerja Bubble Sort :
2. Selection Sort
Selection Sort adalah metode yang digunakan dengan cara
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 Cara Kerja Selection Sort :
3. Insertion Sort
Insertion Sort adalah 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 Cara Kerja Insertion Sort :
4. Quick Sort
Quick Sort adalah Metode yang 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 Cara Kerja Quick Sort :
4. Merge Sort
Merge Sort adalah metode yang digunakan untuk menyusun daftar dengan cara membagi
daftar menjadi dua bagian yang lebih kecil. Kemudian kedua daftar yang baru tersebut
disusun secara terpisah dan diurutkan masing-masing. Kemudian hasil sortir dari setiap
bagian tersebut digabungkan dan diurutkan lagi hingga menghasilkan urutan yang sudah
tersortir.
Intinya menggabungkan dua array
yang sudah tersortir yaitu array A dan array B
kemudian membuat array ketiga yaitu array
C yang berguna untuk menampung nilai-nilai elemen dari array
A dan array B. 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 Cara Kerja Merge Sort :
5. Heap Sort
Heap Sort adalah 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 Cara Kerja Heap Sort :
7. Bucket Sort
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 Cara Kerja Bucket Sort :
8. Shell Sort
Shell Sort adalah Metode yang 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 Cara Kerja Shell Sort :
9. Radix Sort
Radix Sort adalah 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 Cara Kerja Radix Sort :
Referensi :
http://includeryokom.blogspot.com/2012/04/jenis-jenis-penyortiran-beserta.html
http://firmanhidayat987.wordpress.com/2013/02/21/macam-macam-algoritma/
0 komentar:
Posting Komentar