1. BUBBLE SORT
Pengertian
“Bubble sort”
Bubble sort
(metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara
melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai
bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika
tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung
karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang
tepat.
Kelebihan
“Bubble sort”
* Metode Buble
Sort merupakan metode yang paling simpel
* Metode Buble
Sort mudah dipahami algoritmanya
ALGORTIMA BUBBLE SORT
1. Membandingkan data ke-i
dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data
ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak
sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan
ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan
sebaliknya untuk urutan descending (A-Z).
2. Membandingkan data
ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data
terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
3. Selesai satu iterasi,
adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah
selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan
aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.
4. Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.
Contoh program :
#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();
}
2. INSERTION SORT
insertion sort
ini memiliki waktu penyelesaian yang lebih cepat di bandingkan selection sort
dan buble sort
sedangkan cara
kerjanya adalah seperti metode sorting yang lain, yaitu melakukan literasi
(pengulangan) hingga hasil yang sesuai ditemukan, namun insertion sort ini akan
menginsert atau menyisipkan setiap elemen ketempat yang sesuai (setelah
dibandingkan dengan elemen kiri dan kanannya)
atau
simpelnya, kita bisa mengumpamakan metode ini seperti orang yang sedang
mengurutkan kartu, maka dia akan mengambilnya, satu demi satu dan akan
menginsertnya ketempat yang sesuai.
Contoh program :
#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;
}
3. SELECTION SORT
Pengertian
tentang selection sort adalah Algoritma insertion sort pada dasarnya memilah
data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja
pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil
dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya
sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini
dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian
array yang belum diurutkan.
Contoh program :
#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: adi
wazkitoe, 2010";
cout<<"-----------------------";
getch();
return 0;
}
4. MERGE SORT
Prinsip utama
yang diimplementasikan pada algoritma merge-sort seringkali disebut sebagai
pecah-belah dan taklukkan (bahasa Inggris: divide and conquer). Cara kerja
algoritma merge sort adalah 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 hasil penggabungan dari dua buah larik sebelumnya. Menurut
keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan O(nlog(n)). Dalam
bentuk pseudocode sederhana algoritma ini dapat dijabarkan sebagai berikut.
Contoh program :
#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);
}
5. HEAP SORT
HeapSort
adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk
golongan selection sort.
Walaupun lebih
lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai
keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n.
Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan
memandang larik masukan sebagai suatu Complete Binary Tree (CBT).
Setelah itu
Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree.
Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue.
Contoh program :
#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();
}
6. QUICK SORT
Algoritma
sortir yang efisien yang ditulis oleh C.A.R. Hoare pada 1962. Dasar strateginya
adalah “memecah dan menguasai”. Quicksort dimulai dengan menscan daftar yang
disortir untuk nilai median. Nilai ini, yang disebut tumpuan (pivot), kemudian
dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar
dari tumpuan di pindahkan ke sisi lain.
Contoh program :
#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();
}
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 rekursif menerapkan
algoritma bucket sort. Sebuah variasi dari metode ini disebut semacam hitungan
tunggal buffered lebih cepat dari jenis cepat dan membutuhkan waktu sekitar
waktu yang sama untuk berjalan pada set data.
Contoh program :
#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";
}
8. RADIX SORT
Radix Sort
merupakan salah satu algoritma Non-Comparasion Sort (pengurutan tanpa
pembandingan). Proses ynang 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-kategori tersebut digabungkan kembali.
Secara harfiah
Radix dapat diartikan sebagai posisi dalam angka, karena metode ini
pertamakalinya mengurutkan nilai-nilai input berdasarkan radix pertamanya, lalu
pengurutan dilakukan berdasarkan radix keduanya, dan begitu seterusnya. Pada
system decimal, radix adalah digit dalam angka decimal.
Berikut ini
adalah contoh penggunaan algoritma radix sort untuk pengurutan sebuah kumpulan
bilangan bulat positif.
Contoh program :
#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 ();
}
9. SHELL SORT
Distribusi
sort mengacu pada algoritma sorting dimana data didistribusikan dari input
untuk struktur peralihan beberapa yang kemudian dikumpulkan dan ditempatkan
pada output.
Contoh Source Codenya :
#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();
}
10.SHUFFLE SORT
Shuffle sort
dapat dianggap sebagai pembentukan pohon yang sangat luas, seperti B-tree
dengan m = n / 8, untuk memilah efisien dalam banyak kasus.
Shuffle sort memperkirakan distribusi barang yang akan diurutkan dengan
memeriksa n / 8 item pertama. Semacam partisi distributif memperkirakan
distribusi dengan mendekati median dan interpolasi linear dari minimum untuk
median dan dari median untuk maksimal.
Contoh Source Codenya :
#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;
}
