SORTING
Pengertian
Sorting
Pengurutan (Sorting) merupakan 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 Pengurutan
1. BUBBLE
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 :
· 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 diposisi 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 Kedua ( 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 :
Tidak ada komentar:
Posting Komentar