SORTING DALAM
BAHASA PEMPROGRAMAN C
A.
Pengertian
Sorting
Pengurutan
data dalam struktur data sangat penting terutama untuk data yang beripe data
numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut
naik) dan descending (urut turun). Pengurutan (Sorting) adalah proses
pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara
teratur menurut aturan tertentu. Beberapa jenis-jenis sorting dalam bahasa c
adalah:
1.
Heap
Sort
Heap Sort adalah sebuah algoritma pengurutan yang paling
lambat dari algoritma yang memiliki kompleksitas O(n log n). Tetapi tidak
seperti algoritma Merge Sort dan Quick Sort, algoritma Heap Sort tidak
memerlukan rekursif yang besar atau menggunakan banyak tabel (array). Oleh
karena itu, Heap Sort adalah pilihan yang baik untuk sebuah kumpulan data yang
besar.
Algoritma ini bekerja dengan menentukan elemen terbesar
(atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau
awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan
menggunakan struktur data yang disebut heap.
Gambar A.1.1 Heap
sort
Algoritma ini dimulai dengan membangun sebuah array heap
dengan membangun tumpukan dari kumpulan data, lalu memindahkan data terbesar ke
bagian belakang dari sebuah tabel hasil. Setelah itu, array heap dibangun
kembali, kemudian mengambil elemen terbesar untuk diletakkan di sebelah item
yang telah dipindahkan tadi. Hal ini diulang sampai array heap habis. Jadi
secara umum, algoritma ini memerlukan dua buah tabel; satu tabel untuk
menyimpan heap, dan satu tabel lainnya untuk menyimpan hasil. Walaupun lebih
lambat dari Merge Sort atau Quick Sort, algoritma ini cocok untuk digunakan
pada data yang berukuran besar.
2.
Shell Sort
Metode pertambahan menurun (diminishing
increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959,
sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data
dengan cara membandingkan suatu data dengan data lain yang memiliki jarak
tertentu, kemudian dilakukan penukaran bila diperlukan.
Shell Sort merupakan salah satu algoritma pengurutan yang lebih
handal dibandingkan Selection Sort dan Bubble Sort. Kehandalannya yaitu:
“Membagi deret data menjadi dua bagian. Masing-masing bagian diurutkan
menggunakan Bubble Sort. Tidak menggunakan iterasi melainkan increment.
Perulangan diakukan sesuai nilai increment”. Proses pengurutan dengan Shell
sort dapat disimulasikan sebagai berikut:
Gambar A.2.1 Shell Sort
Pertama menentukan jarak mula-mula dari data yang akan
dibandingkan, yaitu N/2. Data pertama dibandingkan dengan data dengan jarak
N/2. Apabila data pertama lebih besar dari data ke N/2 tersebut maka kedua data
tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu
N/2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data
ke-j selalu lebih kecil daripada data ke-(j + N/2).
Pada proses berikutnya, digunakan jarak (N/2) / 2 atau N/4. Data
pertama dibandingkan dengan data dengan jarak N/4. Apabila data pertama lebih
besar dari data ke N/4 tersebut maka kedua data tersebut ditukar. Kemudian data
kedua dibandingkan dengan jarak yang sama yaitu N/4. Demikianlah seterusnya
hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil dari data
ke-(j + N/4).
Pada proses berikutnya, digunakan jarak (N/4) / 2 atau N/8.
Demikian seterusnya sampai jarak yang digunakan adalah 1.
Algoritma metode Shell dapat dituliskan sebagai berikut :
1.
Jarak = N
2.
Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3.
Jarak = Jarak / 2. Sudah = false
4.
Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5.
Sudah = true
6.
j = 0
7.
Selama (j < N – Jarak) kerjakan baris 8 dan 9
8.
Jika (Data[j] > Data[j + Jarak] maka tukar
Data[j], Data[j + Jarak], Sudah = true
9.
j = j + 1
3.
Quick Sort
Quick Sort adalah algoritma sorting yang
berdasarkan pembanding dengan metode divide and conqueror, sangat berbeda
dengan Radix Sort yang tanpa pembanding.
Gambar A.3.1 Quick Sort
Disebut Quick Sort karena algoritma Quick Sort
mengurutkan dengan sangat cepat atau Quick Sort juga bias disebut dengan
exchange sort, karena konsepnya yang membuat partisi2 dan Sort yang dilakukan
tiap partisi.
Kelebihan :
·
Algoritma sederhana dan mudah diterapkan pada berbagai bahasa
pemrograman dan arsitektur mesin secara efisien.
·
Algoritma pengurutan yang lebih cepat dengan perbandingan
seperti Marge Sort dan Heap Sort.
·
Melakukan proses secara langsung pada input(in-place) dengan
sedikit tambahan memory.
·
Bias digunakan dgn baik untuk input angka daan karakter
Kekurangan :
·
Sedikit kesalahan saja didalam program bisa menyebablkan
program tidak beraturan atau outputan tidak benar bahkan eksekusi tidak akan
pernah selesai.
·
Memiliki ketergantungan terhadap data yang dimasukkan.
·
Sifatnya yg kurang stable karena input yang akan dirubah pada
hasil akhirnya(output) bernilai sama.
·
Memiliki katergantungan terhadap data yang dimasukkan.
Pada penerapan
rekursif(memanggil dirinya sendiri) bahkan dalam kasus terburuk bisa dapat
menghabiskan stack dan memacetkan rogram.
4.
Marge Sort
Merge sort adalah algoritma pengurutan data
dalam ilmu
komputer yang dibuat untuk kebutuhan pengurutan rangkaian data
yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya
yang terlalu besar.
Merge Sort berfungsi untuk mengurtkan nilai yang belum
terurut dengan menggunakan metode Merge Sort, untuk lebih jelasnya metode
pengurutan data menggunakan merge sort. Merge Sort adalah sebagi berikut.
Berikut penjelasan langkah kerja dari Merge sort. Langkah kerja merge sort terbagi
atas 3 bagian yaitu:
ü Divide: Jika array A yang
diberikan memiliki nilai nol atau satu elemen, langsung dikembalikan; itu sudah
diurutkan. Jika tidak, akan dilakukan pembagi A [p .. r] menjadi dua subarrays
A [p .. q] dan A [q + 1 .. r], masing-masing berisi sekitar setengah dari
elemen A [p .. r]. Artinya, q adalah titik tengah dari A [p .. r].
ü Conquer: dipencahkan menjadi dua
subarrays A [p .. q] dan A [q + 1 .. r]. Dan memberi solusi pada setiap bagian dengan memanggil prosedur merge sort.
ü Combine: Menggabungkan elemen A [p
.. r] dengan menggabungkan dua subarrays diurutkan A [p .. q] dan A [q + 1 ..
r] menjadi urutan yang berurut.
Gambar A.4.1 Merge Sort
5.
Radix Sort
Radix sort adalah algoritma non-comparation
sort atau pengurutan tanpa perbandingan . metode ini mengklarifikisi sebuah
data sesuai dengan kategori urutan tertentu. Dan setiap kategori diurutkan lagi
dan seterusnya sesuai dengan kebutuhan. Kemudian bagian2 dari kategori tersebut
akan digabungkan kembali.
Catatan : data yang diurutkan pertama kali yaitu
berupa input nilai2 yang dimasukkan pertama kali berdasarkan radix pertamanya,
lalu diteruskan atau diurutkan lagi berdasarkan radix keduanya, dst. Pada
system decimal radix adalah digit dalam angka decimal. Missal : angka 354
mempunyai 3 digit yaitu 3, 5 dan 4.
Gambar A.5.1 Radix Sort
6.
Tree Sort
Tree sort adalah teknik mengurutkan data dengan
menggunakan struktur data tree. Kelebihan: Data langsung urut begitu
dimasukkan, efektif untuk jumlah data yang kecil. Kekurangan: Tidak efektif
untuk jumlah data yang besar.
B.
Source Code
1.
Heap Sort
#include<stdio.h>
#include
<windows.h>
void
makeheap(int a[], int n)
{
int i, temp, k, j;
for (i = 1; i<n; i++)
{
temp = a[i];
k = (i - 1) / 2;
j = i;
while (j>0 && a[k] < temp)
{
a[j] = a[k];
j = k;
k = (j - 1) / 2;
}
a[j] = temp;
}
}
void
disp(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("%d,", a[i]);
}
printf("\b");
printf(" ");
}
void
sortheap(int a[], int n)
{
int temp, i, j;
for (i = n - 1; i >= 1; i--)
{
temp = a[i];
a[i] = a[0];
a[0] = temp;
makeheap(a, i);
printf("\n\t-->");
disp(a, n);
}
}
void
main()
{
int a[100], n, i;
system("cls");
printf("\n\tJumlah Element : ");
scanf("%d", &n);
system("cls");
printf("\n\tElemen Array \n");
for (i = 0; i < n; i++)
{
printf("\tElement %d := ", i +
1);
scanf("%d", &a[i]);
}
makeheap(a, n);
printf("\n\tHeap Created := ");
disp(a, n);
sortheap(a, n);
printf("\n\n\tSorted Elements :=
");
disp(a, n);
getch();
}
|
2.
Shell Sort
#include "stdio.h"
int main()
{
int
L[20],temp,i,j,n=6,m;
printf("pengurutan berdasarkan Shell sort \nmasukkan %d elements:
\n",n);
for(i=0;i<n;i++){
scanf("%d",&L[i]);}
printf("\nsebelum sorting: ");
for(i=0;i<n;i++){printf("%d ",L[i]);}
for(m =
n/2;m>0;m/=2){
/*6 7 2 1
===> 2 7 6 1, 2 1 6 7 // 1 2 6 7, 1 2 6 7, 1 2 6 7*/
for(j=m;j<n;j++){
for(i=j-m;i>=0;i-=m){
if(L[i+m]>=L[i]) break;
else{
temp = L[i];
L[i] = L[i+m];
L[i+m] = temp;
}
}
}
}
printf("\nsetelah sorting: ");
for(i=0;i<n;i++){printf("%d ",L[i]);}
printf("\n");
}
|
3.
Quick Sort
#include <stdio.h>
#include <stdlib.h>
void quickSort (int a[], int lo, int hi){
// lo adalah index
bawah, hi adalah index atas
// dari bagian
array yang akan di urutkan
int i=lo, j=hi,
h;
int pivot=a[lo];
// pembagian
do{
while
(a[i]<pivot) i++;
while
(a[j]>pivot) j--;
if (i<=j)
{
h=a[i];
a[i]=a[j]; a[j]=h;//tukar
i++;
j--;
}
} while
(i<=j);
// pengurutan
if (lo<j)
quickSort(a, lo, j);
if (i<hi)
quickSort(a, i, hi);
}
main(){
int
tabInt[10]={24,17,18,15,22,26, 13, 21, 16, 28};
int i,n=10;
for(i=0;i<n;i++){
printf("%d ",tabInt[i]);
}
printf("\n");
quickSort(tabInt,0,n-1);
for(i=0;i<n;i++){
printf("%d ",tabInt[i]);
}
}
|
4.
Merge Sort
#include
<stdio.h>
#define
MAX 10
int
Data[MAX];
int
temp[MAX];
//
Prosedur merge sort
void
merge(int Data[], int temp[], int kiri, int tengah, int kanan)
{
int i, left_end, num_elements,
tmp_pos;
left_end = tengah - 1;
tmp_pos = kiri;
num_elements = kanan - kiri + 1;
while ((kiri <= left_end)
&& (tengah <= kanan))
{
if (Data[kiri] <=
Data[tengah])
{
temp[tmp_pos] = Data[kiri];
tmp_pos =
tmp_pos + 1;
kiri =
kiri +1;
}
else
{
temp[tmp_pos] =
Data[tengah];
tmp_pos = tmp_pos +
1;
tengah = tengah + 1;
}
}
while (kiri <= left_end)
{
temp[tmp_pos] = Data[kiri];
kiri = kiri + 1;
tmp_pos = tmp_pos +
1;
}
while (tengah <= kanan)
{
temp[tmp_pos] =
Data[tengah];
tengah = tengah + 1;
tmp_pos = tmp_pos +
1;
}
for (i=0; i <= num_elements;
i++)
{
Data[kanan] =
temp[kanan];
kanan = kanan - 1;
}
}
//
Prosedur membuat kumpulan data
void
m_sort(int Data[], int temp[], int kiri, int kanan)
{
int tengah;
if (kanan > kiri)
{
tengah = (kanan +
kiri) / 2;
m_sort(Data, temp,
kiri, tengah);
m_sort(Data, temp,
tengah+1, kanan);
merge(Data, temp,
kiri, tengah+1, kanan);
}
}
void
mergeSort(int Data[], int temp[], int array_size)
{
m_sort(Data, temp, 0, array_size
- 1);
}
int
main()
{
int i;
printf("Masukkan DATA
SEBELUM TERURUT : \n");
for (i = 0; i < MAX; i++)
{
printf ("Data ke
%i : ", i+1);
scanf
("%d", &Data[i]);
}
mergeSort(Data, temp, MAX);
printf("\nDATA SETELAH
TERURUT : ");
for (i = 0; i < MAX; i++)
printf("%d ", Data[i]);
printf("\n");
//scanf("%d");
return(0);
}
|
5.
Radix Sort
#include
<stdio.h>
#define
MAX 20
#define
SHOWPASS
#define
BASE 10
void
print(int *a, int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d\t", a[i]);
}
void
radixsort(int *a, int n)
{
int i, b[MAX], m = a[0], exp = 1;
//Get the greatest value in the array a and
assign it to m
for (i = 1; i < n; i++)
{
if (a[i] > m)
m = a[i];
}
//Loop until exp is bigger than the largest
number
while (m / exp > 0)
{
int bucket[BASE] = { 0 };
//Count the number of keys that will go
into each bucket
for (i = 0; i < n; i++)
bucket[(a[i] / exp) % BASE]++;
//Add the count of the previous buckets
to acquire the indexes after the end of each bucket location in the array
for (i = 1; i < BASE; i++)
bucket[i] += bucket[i - 1]; //similar
to count sort algorithm i.e. c[i]=c[i]+c[i-1];
//Starting at the end of the list, get
the index corresponding to the a[i]'s key, decrement it, and use it to place
a[i] into array b.
for (i = n - 1; i >= 0; i--)
b[--bucket[(a[i] / exp) % BASE]] =
a[i];
//Copy array b to array a
for (i = 0; i < n; i++)
a[i] = b[i];
//Multiply exp by the BASE to get the
next group of keys
exp *= BASE;
#ifdef SHOWPASS
printf("\nPASS : ");
print(a, n);
#endif
}
}
int
main()
{
int arr[MAX];
int i, n;
printf("Enter total elements (n <=
%d) : ", MAX);
scanf("%d", &n);
n = n < MAX ? n : MAX;
printf("Enter %d Elements : ",
n);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("\nARRAY : ");
print(&arr[0], n);
radixsort(&arr[0], n);
printf("\nSORTED : ");
print(&arr[0], n);
printf("\n");
return 0;
}
|
6.
Tree Sort
#include <stdio.h>
#include <stdlib.h>
typedef struct _tree
{ int v;
struct _tree *p,
*l, *r;
} Tree;
void Ins(Tree **t, int val)
{ if(!(*t))
{ *t = (Tree*)malloc(sizeof(Tree));
(*t)->p =
(*t)->l = (*t)->r = NULL;
(*t)->v =
val;
}
else
if((*t)->v > val)
{ Ins(&(*t)->l, val);
(*t)->l->p = *t;
}
else
{ Ins(&(*t)->r, val);
(*t)->r->p = *t;
}
}
void Print(Tree *t)
{ if(t)
{ Print(t->l);
printf("%d ", t->v);
Print(t->r);
}
}
int main()
{
Tree *t = NULL;
int n;
while(scanf("%d", &n) && n != 0)
Ins(&t, n);
Print(t);
}
|
C.
Output
1.
Heap Sort
Gambar A.1.1 Hasil Pengurutan dengan Metode Heap
2.
Shell Sort
Gambar A.2.1 Hasil Pengurutan dengan Metode Shell
3.
Quick Sort
Gambar A.3.1 Hasil pengurutan dengan
Metode Quick
4.
Merge Sort
Gambar A.4.1 Hasil Pengurutan dengan
Metode Merge
5.
Radix Sort
Gambar A.5.1 Hasil Pengurutan dengan
Metode Radix
6.
Tree Sort
Gambar A.6.1 Hasil Pengurutan dengan
Metode Tree
Sumber:
Komentar
Posting Komentar