Algoritma Pengurutan
& Pengurutan adalah proses mengatur sekumpulan objek
menurut urutan dan susunan tertentu.
Jenis Algoritma Pengurutan
} Buble Sort (Pengurutan Apung/Gelembung)
} Selection Sort (Pengurutan Seleksi)
} Insertion Sort (Pengurutan Sisip)
} Shell Sort (Pengurutan Shell)
& Buble Sort (Pengurutan
Apung/Gelembung)
Pengertian Bubble Sort
Bubble Sort (metode gelembung) adalah metode pengurutan 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.
Metode Bubble
Algoritma
beroperasi sebagai berikut;
ü
Elemen
pertama dibandingkan dengan elemen kedua.Bila elemen kedua, kedua elemen
tersebut ditukar.
ü
Elemen
kedua dan ketiga dibandingkan, bila elemen ketiga < kedua elemen ditukar, proses
terus berlangsung dengan elemen ketiga dan keempat, dan seterusnya. Sampai
akhir deretan data tercapai.
ü
Bila
tak ada lagi yang ditukarkan, algoritma berhenti.Bila terjadi pertukaran selama
berurutan, proses akan diulang. Sehingga akhirnya semua elemen tersusun, tidak
ada pertukaran lagi, dan algoritma berhenti.
KELEBIHAN DAN KELEMAHAN METODE BUBBLE SORT
Kelebihan
:
1. Metode Bubble
Sort merupakan yang paling simple
2. Metode Bubble Sort muda di pahami algoritmanya
Kelemahan
:
Ø Meskipun simpel metode Bubble Sort merupakan
metode pengurutan yang paling tidak efisien.
Kelemahan Bubble Sort adalah pada saat mengurutkan data yang sangat
besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja
memburuk cukup signifikan ketika data yang diolah jika data cukup banyak. Kelemahan lain adalah
jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah
cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data
yang lain untuk menentukan posisinya.
.
Contoh
program Bubble Sort
#include <stdio.h>
#define N 20
int bubble(int n);
int i,j,A[N];
main()
{
int jml;
printf("\t
METODE BUBBLE SORT \n\n");
printf("Masukkan
jumlah bilangan: ");
scanf("%d",&jml);
printf("\n");
// input data
for
(i=0;i<jml;i++)
{
printf("Bilangan
ke %d : ",i+1);
scanf("%d",&A[i]);
}
printf("\n");
//
mengurutkan data
bubble(jml);
//
menampilkan data
printf("Data
yang sudah terurut : \n");
for
(i=0;i<jml;i++)
{
printf("%d\n",A[i]);
}
}
//
fungsi bubble
int
bubble(int n)
{
int
temp;
for
(i=1;i<=n-1;i++)
{
for
(j=i;j<n;j++)
{
if
(A[i-1]>A[j])
{
temp
= A[i-1];
A[i-1]
= A[j];
A[j]
= temp;
}
}
}
Outputnya:
& Selection Sort
(Pengurutan Seleksi)
ü Selection sort merupakan perbaikan dari metode bubble sort dengan
mengurangi jumlah perbandingan.
ü Selection sort merupakan metode pengurutan
dengan mencari nilai data terkecil dan nilai data
terbesar dimulai dari data diposisi
0 hingga diposisi N-1.
ü Jika terdapat N data dan data terkoleksi dari urutan 0
sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort adalah
sebagai berikut :
ü Cari data terkecil dalam interval j = 0 sampai
dengan j = N-1
ü Jika pada posisi pos ditemukan
data yang terkecil, tukarkan data diposisi pos dengan
data di posisi i jika k.
ü Ulangi langkah 1 dan 2 dengan j = j + i sampai
dengan j = N-1, dan seterusnya sampai j = N
- 1.
& Kelebihan &
kekurangan Selection Sort:
Ø Kelebihan:
1.
Algoritma ini
sangat rapat dan mudah untuk diimplementasikan.
2.
Operasi
pertukarannya hanya dilakukan sekali saja.
3.
Waktu pengurutan
dapat lebih ditekan.
4.
Mudah
menggabungkannya kembali.
5.
Kompleksitas
selection sort relatif lebih kecil.
Ø Kekurangan:
1.
Sulit untuk
membagi masalah.
& Insertion Sort
(Pengurutan Sisip)
Insertion
sort adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi
yang tepat.
& Ada dua metode yang bisa digunakan di Insertion Sort
yaitu:
1.
Metode langsung (STRAIGHT
INSERTION SORT)
2.
Metode penyisipan biner (BINARY
INSERTION SORT)
1. Metode langsung
(STRAIGHT INSERTION SORT)
Ilustrasi
dari langkah-langkah pengurutan dengan algoritma penyisipan langsung (straight
insertion sort) dapat dilihat pada tabel
berikut :
|
IterasiData[0]Data[1]Data[2]Data[3]Data[4]Data[5]
Data[6]Data[7]Data[8]Data[9]
Awal 12 35 9 11 3 17 23 15 31 20
i=1 12 35 9 11 3 17 23 15 31 20
i=2 12 35 9 11 3 17 23 15 31 20
i=3 9 12 35 11 3 17 23 15 31 20
i=4 9 11 12 35 3 17 23 15 31 20
i=5 3 9 11 12 35 17 23 15 31 20
i=6 3 9 11 12 17 35 23 15 31 20
|
2. Metode penyisipan biner (BINARY
INSERTION SORT)
ü Metode
pengurutan dengan algoritma penyisipan biner (binary insertion sort)
memperbaiki metode pengurutan dengan algoritma penyisipan langsung dengan
melakukan proses perbandingan yang lebih sedikit sehingga proses pengurutan
lebih cepat.
ü Metode
penyisipan biner melakukan proses perbandingan dengan membagi dua bagian data
dari posisi 0 sampai dengan i-1 yang disebut dengan bagian kiri dan
kanan. Apabila data pada posisi ke i berada pada jangkauan kiri maka
proses perbandingan dilakukan hanya pada bagian kiri dan menggeser posisi
sampai i.
& Kelebihan dan kekurangan
Kelebihan
•
Sederhana
dalam penerapannya.
•
Mangkus
dalam data yang kecil.
•
Jika
list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat
dibandingkan dengan Quicksort.
•
Mangkus
dalam data yang sebagian sudah terurut.
•
Lebih
mangkus dibanding Bubble Sort dan Selection Sort.
•
Loop
dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma
pengurutan tercepat pada jumlah elemen yang sedikit.
•
Stabil.
Kekurangan
•
Banyaknya
operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.
•
Untuk
larik yang jumlahnya besar ini tidak praktis.
•
Jika
list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan
mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.
•
Membutuhkan
waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan
elemen dalam jumlah besar.
& Shell Sort (Pengurutan
Shell)
Penemu Algoritma Pengurutan shell adalah Donald
Shell tahun 1959. Algoritma pengurutan shell merupakan perbaikan terhadap
metode pengurutan sisip. Shell sort adalah salah satu sorting algoritma pada
sebuah deklarasi array ([]).
Pada pengurutan data kita terlebih dahulu harus
membuat sub list – sub list yang di dasarkan pada jarak antar data yang di
tentukan. Jarak yang telah ditetukan biasanya di lambangakan dengan k, biasanya
jarak yang paling di gunakan pada sortingsn ini saat melakukan pengurutan data
yaitu k5, k3. dan k1. Artinya, dari data yang akan ditentukan atau ditukar
dengan data yang lain berjarak 5, 3 atau 1 data saja.
& Kelebihan dan Kekurangan
Kelebihan :
1.
Algoritma ini sangat rapat dan mudah untuk
diimplementasikan.
2.
Operasi pertukarannya hanya dilakukan sekali saja.
3.
Waktu pengurutan dapat lebih ditekan.
4.
Mudah menggabungkannya kembali.
5.
Kompleksitas selection sort relatif lebih kecil.
Kekurangan :
1.
Membutuhkan method tambahan.
2.
Sulit untuk membagi masalah.
Metode
Shell
Contoh
Program Shell Sort
Ø #include
<stdio.h>
#include
<conio.h>
int
main()
{
int
n,m,i,j,range,jarak,simpan,data[50],dx[50];
printf("Masukkan banyak data
A:\t"),scanf("%d",&n);
printf("Masukkan banyak data
B:\t");scanf("%d",&m);
for(i=0;i<n;i++)
{
printf ("Data A ke
%d:\t",i+1);scanf("%d",&data[i]);
}
for(i=0;i<m;i++)
{
printf ("Data B ke
%d:\t",i+1);scanf ("%d",&dx[i]);
}
printf ("\nSEBELUM\n");
for (i=0;i<n;i++)
{
printf("\nDataA=%d",data[i]);
}
for (i=0;i<m;i++)
{
printf("\nDataB=%d",dx[i]);
}
jarak=n/2;
while (jarak>0)
{
for (i=jarak;i<n;i++)
{
j=i-jarak;
while(j>=0)
{
if(data[j+jarak]<data[j])
{
simpan=data[j];
data[j]=data[j+jarak];
data[j+jarak]=simpan;
printf
("\n");
for(int
j=0;j<n;j++)
{
printf("\n%d",data[j]);
}
}
j=j-jarak;
}
}
jarak=jarak/2;
}
range=m/2;
while (range>0)
{
for (i=range;i<m;i++)
{
j=i-range;
while(j>=0)
{
if(dx[j+range]>dx[j])
{
simpan=dx[j];
dx[j]=dx[j+range];
dx[j+range]=simpan;
printf
("\n");
for(int
j=0;j<n;j++)
{
printf("\n%d",dx[j]);
}
}
j=j-range;
}
}
range=range/2;
}
printf("\nSESUDAH data A\n");
for(i=0;i<n;i++)
{
printf("\n%d",data[i]);
}
printf("\nSESUDAH data B\n");
for(i=0;i<m;i++)
{
printf("\n%d",dx[i]);
}
getch ();
return 0;
}
Outputnya:
Ø #include <stdio.h>
#include <stdlib.h>
void shell_sort(char *chars, int c)
{
register
int i, j, space, k;
char
x, a[5];
a[0]=9;
a[1]=5; a[2]=3; a[3]=2; a[4]=1;
for(k=0;
k < 5; k++)
{
space
= a[k];
for(i=space;
i < c; ++i)
{
x
= chars[i];
for(j=i-space;
(x < chars[j]) && (j >= 0); j=j-space)
chars[j+space]
= chars[j];
chars[j+space]
= x;
}
}
}
int main()
{
char
string[3];
printf("Masukkan
Karakter:");
gets(string);
shell_sort(string,
strlen(string));
printf("Pengurutan
karakter: %s.\n", string);
return
0;
}
Outputnya:
0 komentar:
Posting Komentar