·
Algoritma Pengurutan
Pengurutan adalah proses mengatur sekumpulan objek menurut urutan dan
susunan tertentu.
Jenis Algoritma Pengurutan
1.
Buble Sort (Pengurutan Apung/Gelembung)
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;
1. Elemen pertama dibandingkan dengan elemen kedua. Apabila elemen kedua lebih
besar dari elemen pertama, maka kedua elemen tersebut ditukar.
2. 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.
3. 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 METODE BUBBLE SORT
a.
Metode Bubble Sort merupakan yang
paling simple.
b. Metode Bubble Sort muda di pahami algoritmanya
·
KELEMAHAN METODE BUBBLE SORT
a.
Meskipun simpel metode
Bubble Sort merupakan metode pengurutan
yang paling tidak efisien.
b.
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.
c.
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 100
int bubble(int n);
int i,j,A[N];
int main()
{
int jml;
printf("\t METODE BUBBLE SORT \n\n");
printf("Masukkan banyaknya data = ");
scanf("%d",&jml);
printf("\n");
//Data yang di input
for (i=0;i<jml;i++)
{
printf("Data 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 metode 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;
}
}
}
}
|
Output yang dihasilkan
dari syntax diatas;
2.
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 dari Metode Selection
Sort;
a.
Algoritma ini sangat rapat dan mudah untuk diimplementasikan.
b.
Operasi pertukarannya hanya dilakukan sekali saja.
c.
Waktu pengurutan dapat lebih ditekan.
d.
Mudah menggabungkannya kembali.
e.
Kompleksitas selection sort relatif lebih kecil.
·
Kekurangan dari Metode Selection
Sort;
Sulit untuk membagi masalah.
3.
Insertion Sort (Pengurutan Sisip)
Insertion sort adalah metode pengurutan dengan cara menyisipkan elemen
larik pada posisi yang tepat.
·
Metode yang bisa digunakan di Insertion Sort
yaitu;
a. Metode langsung (STRAIGHT INSERTION
SORT)
Ilustrasi dari langkah-langkah pengurutan dengan algoritma penyisipan
langsung (straight insertion sort) dapat dilihat pada tabel berikut :
|
Iterasi
Awal
|
Data[0]
|
Data[1]
|
Data[2]
|
Data[3]
|
Data[4]
|
Data[5]
|
Data[6]
|
Data[7]
|
Data[8]
|
Data[9]
|
|
i=1
i=2
i=3
i=4
i=5
i=6
|
12
12
12
9
9
3
3
|
35
35
35
12
11
9
9
|
9
9
9
35
12
11
11
|
11
11
11
11
35
12
12
|
3
3
3
3
3
35
17
|
17
17
17
17
17
17
35
|
23
23
23
23
23
23
23
|
15
15
15
15
15
15
15
|
31
31
31
31
31
31
31
|
20
20
20
20
20
20
20
|
a. 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.
·
Kelebihannya;
a. Sederhana dalam penerapannya.
b. Mangkus dalam data yang kecil.
c. Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan
lebih cepat dibandingkan dengan Quicksort.
d. Mangkus dalam data yang sebagian sudah terurut.
e. Lebih mangkus dibanding Bubble Sort dan Selection Sort.
f. Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu
algoritma pengurutan tercepat pada jumlah elemen yang sedikit.
g. Stabil.
·
Kekurangannya;
a. Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk
elemen larik.
b. Untuk larik yang jumlahnya besar ini tidak praktis.
c. Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus
memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.
d. Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok
dalam pengurutan elemen dalam jumlah besar.
1.
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.
·
Kelebihannya;
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.
·
Kekurangannya;
1.
Membutuhkan method tambahan.
2.
Sulit untuk membagi masalah.
|
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;
 |
ty gan
BalasHapus