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.
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;
}
}
}
Output :
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 :
|
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
|
|
i=7
|
3
|
9
|
11
|
12
|
17
|
23
|
35
|
15
|
31
|
20
|
|
i=8
|
3
|
9
|
11
|
12
|
15
|
17
|
23
|
35
|
31
|
20
|
|
i=9
|
3
|
9
|
11
|
12
|
15
|
17
|
23
|
31
|
35
|
20
|
|
Akhir
|
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
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;
}
Output :
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;
}
Output :
-
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;
}
Output :
