Algoritma Pengurutan
Þ Pengurutan adalah proses mengatur
sekumpulan objek menurut urutan dan susunan tertentu
Jenis Algoritma Pengurutan
Ø Buble Sort (Pengurutan Apung)
Ø Selection Sort (Pengurutan Seleksi)
Ø Insertion Sort (Pengurutan Sisip)
Ø Shell Sort (Pengurutan Shell)
·
Algoritma Pengurutan Apung (bubble
sort)
Þ
Algoritma
pengurutan apung diinspirasi oleh gelembung sabun yang berada diatas air.
Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka
gelembung sabun selalu terapung ke atas permukaan. Secara umum, benda-benda
yang berat akan terbenam dan benda-benda yang ringan akan terapung ke atas
permukaan
Algoritma Dari Bubble Sort
Ø 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).
Ø 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.
Contoh Program
#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;
}}
}}
Output :
·
Algoritma Pengurutan Seleksi
Þ
Algoritma pengurutan ini disebut pengurutan
seleksi karena gagasan dasarnya adalah memilih elemen maksimum/minimun dari larik,
lalu menempatkan elemen maksimum.minimum itu pada awal atau akhir larik (elemen
terujung). Selanjutnya elemen terujung tersebut “diisolasi” dan tidak
disertakan pada proses selanjutnya. Proses yang sama diulang untuk elemen larik
yang tersisa, yaitu memiliki elemen maksimum/minimum berikutnya dan
mempertukarkannya dengan elemen terujung larik sisa.
Pengurutan Seleksi
|
Belum Terurut
|
|
Belum Terurut
|
n
|
Þ
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.
Þ
Bila
diketahui data awal berupa: 44 55 12 42 94 18 6 67, maka langkah per langkah
pengurutan dengan metode selection sort adalah sebagai berikut:
·
Algoritma Pengurutan Sisip
Þ Metode Pengurutan dengan cara
menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi yang tepat
dilakukan dengan menyisir larik. Selama penyisiran dilakukan pergeseran elemen
larik. Metode pengurutan sisip cocok untuk persoalan menyisipkan elemen baru ke
dalam sekumpulan elemen yang sudah terurut.
Þ Dan ada dua metode yang bisa
digunakan di Insertion Sort yaitu:
— Metode langsung (STRAIGHT
INSERTION SORT)
Illistrasi dari langkah – langkah pengurutan dengan algoritma Penyisipan
langsung (straight insertion sort) dapat di lihat di bawah ini :
Iterasi Data[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
— 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.
·
Algoritma Pengurutan Shell
Þ Algoritma pengurutan shell dibuat
dengan pertama-tama memodifikasi algoritma pengurutan sisip sedemikian sehingga
kita dapat menspesifikasikan titik awal pengurutan dan ukuran step (pada
algoritma pengurutan sisip yang asli, titik awal pengurutan adalah elemen pertama
dan ukuran step=1)
Penggabungan Dua Buah Larik Terurut
Þ
Misal
kita memiliki dua buah larik, L1 dan L2 yang masing masing sudah terurut. Kita
ingin membentuk sebuah larik baru, L3 yang merupakan gabungan dari dua buah
larik tersebut sedemikian sehingga L3 juga sudah terurut .
Contoh Program :
#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;
}
Output :
No comments:
Post a Comment