DEFINISI
Pengurutan adalah
proses pengurutan sekumpulan data dalam suatu urutan tertentu.
Sorting dipakai untuk:
1.Membantu proses pencarian (searching)
2.Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.
1.Membantu proses pencarian (searching)
2.Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.
JENIS
– JENIS ALGORITMA PENGURUTAN
1. BUBLE SORT
·
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.
·
Kelebihan dan Kekurangan 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.
·
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.
•
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, dan seterusnya.
•
Proses akan berhenti jika tidak ada pertukaran
dalam satu iterasi
·
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;
}
}
}
2. SELECTION SORT
·
Pengertian Selection Sort
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.
·
Metode Selection Sort
Jika
terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka
algoritma
pengurutan dengan metode selection sort adalah sebagai berikut:
1. Cari data
terkecil dalam interval j = 0 sampai dengan j = N-1
2. Jika pada
posisi pos ditemukan data yang terkecil, tukarkan data diposisi pos
dengan data
di posisi i jika k.
3. Ulangi
langkah 1 dan 2 dengan j = j+i sampai dengan j = N-1, dan
seterusnya
sampai j
= N - 1.
4. 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:
|
44 55 12
42 94 18 06 67 Data Awal
|
|
06 55 12 42 94 18 44 67 Tukarkan
data ke 1 dengan data ke 7
|
|
06 12 55 42 94 18 44 67 Tukarkan
data ke 2 dengan data ke 3
|
|
06 12 18 42 94 55 44 67 Tukarkan
data ke 3 dengan data ke 6
|
|
06 12 18 42 94 55 44 67 Data ke 4
tidak ditukarkan
|
|
06 12 18 42 44 55 94 67 Data ke 5
ditukarkan dengan data ke 7
|
|
06 12 18 42 44 55 94 67 Data ke 6
tidak ditukarkan
|
|
06 12 18 42 44 55 67 94 Data ke 7
ditukarkan dengan data ke 8
|
|
06 12 18 42 44 55 67 94 Data setelah terurut
|
Tabel 2. Langkah demi langkah pengurutan dengan metode
selection sort.
·
Kelebihan dan 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.
3. INSERTION SORT
·
Pengertian Insertion Sort
Insertion
sort adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi
yang tepat.
·
Macam- macam metode insertion sort
1
Langsung (straight insertion sort)
Ilustrasi
dari langkah-langkah pengurutan dengan algoritma penyisipan langsung (straight
insertion sort) dapat dilihat pada tabel berikut :
|
44 55 12 42 94 18 06 67 Data Awal
|
|
06 55 12 42 94 18 44 67 Tukarkan data ke 1 dengan
data ke 7
|
|
06 12 55 42 94 18 44 67 Tukarkan data ke 2 dengan
data ke 3
|
|
06 12 18 42 94 55 44 67 Tukarkan data ke 3 dengan
data ke 6
|
|
06 12 18 42 94 55 44 67 Data ke 4 tidak ditukarkan
|
|
06 12 18 42 44 55 94 67 Data ke 5 ditukarkan dengan
data ke 7
|
|
06 12 18 42 44 55 94 67 Data ke 6 tidak ditukarkan
|
|
06 12 18 42 44 55 67 94 Data ke 7 ditukarkan dengan
data ke 8
|
|
06 12 18 42
44 55 67 94 Data setelah terurut
|
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 insertion
sort
-
Kelebihan
1.
Sederhana
dalam penerapannya.
2.
Mangkus
dalam data yang kecil.
3.
Jika list
sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat
dibandingkan dengan Quicksort.
4.
Mangkus
dalam data yang sebagian sudah terurut.
5.
Lebih
mangkus dibanding Bubble Sort dan Selection Sort.
6.
Loop dalam
pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma
pengurutan tercepat pada jumlah elemen yang sedikit.
7.
Stabil.
-
Kekurangan
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.
·
Contoh Program
#include <stdio.h>
int main()
{
int n,
array[1000], c, d, t;
printf("Masukkan Banyak Elemen ");
scanf("%d", &n);
printf("Masukkan %d Bilangan\n", n);
for (c = 0; c
< n; c++) {
scanf("%d", &array[c]);
}
for (c = 1 ; c
<= n - 1; c++) {
d = c;
while ( d
> 0 && array[d] < array[d-1]) {
t = array[d];
array[d] = array[d-1];
array[d-1]
= t;
d--;
}
}
printf("Data Yang Sudah Terurut :\n");
for (c = 0; c
<= n - 1; c++) {
printf("%d\n", array[c]);
}
return 0;
}
4. SHELL SORT
·
Pengertian Shell Sort
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.
·
Metode Shell Sort
·
Kelebihan dan Kekurangan Shell 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
Membutuhkan method tambahan.
2
Sulit untuk membagi masalah.
·
Contoh Program
-
Contoh Program
Pertama ( Mengurutkan Data Tipe Angka )
#include<stdio.h>
#include<conio.h>
int main()
{
int arr[30];
int
i,j,k,tmp,num;
printf("Masukan Banyaknya Elemen
:");
scanf("%d", &num);
for(k=0;
k<num; k++)
{
printf("\nMasukkan %d Nilai : ",k+1);
scanf("%d",&arr[k]);
}
for(i=num/2; i>0; i=i/2)
{
for(j=i;
j<num; j++)
{
for(k=j-i;
k>=0; k=k-i)
{
if(arr[k+i]>=arr[k])
{
break;
}
else
{
tmp=arr[k];
arr[k]=arr[k+i];
arr[k+i]=tmp;
}
}
}
}
printf("\n**** Hasil Shell Sort
****\n");
for(k=0;
k<num; k++)
printf("%d\t",arr[k]);
getch();
return 0;
}
Output :
-
Contoh
Program Kedua ( Mengurutkan Data Tipe
Angka dengan Dua Array )
#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("\n");
printf("\nSESUDAH
data A\n");
for(i=0;i<n;i++)
{
printf("\n%d",data[i]);
}
printf("\n");
printf("\nSESUDAH
data B\n");
for(i=0;i<m;i++)
{
printf("\n%d",dx[i]);
}
getch
();
return
0;
}
-
Contoh
Program Ketiga ( Mengurutkan Data Tipe
Char )
#include <string.h>
#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;
}
Tidak ada komentar:
Posting Komentar