METODE SORTING
1. Bucket
Sort
Bucket sort
adalah algoritma sorting yang bekerja dengan partisi array ke dalam jumlah
terbatas sort. Setiap kotak ini kemudian diurutkan secara individual, baik
menggunakan algoritma sorting yang berbeda, atau dengan rekursif menerapkan
algoritma bucket sort. Sebuah variasi dari metode ini disebut semacam hitungan
tunggal buffered lebih cepat dari jenis cepat dan membutuhkan waktu sekitar
waktu yang sama untuk berjalan pada set data.
Contoh algoritma bucket sort dengan Dev-c++
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
#define INPUT 'i'
#define OUTPUT 'o'
#define _MY_DEBUG
#if defined(_MY_DEBUG)
#define
TRACE_LINE printf("\n\n- Program Statistics :\n1. File : %s\n2.
Date : %s\n3. Time : %s\n",__FILE__,__DATE__,__TIME__);
#else
#define
TRACE_LINE
#endif
void InputOutput(int*, const int,
const char);
void BucketSort(int*, const int);
void FreeBuffer(int*);
int main(int argc, char *argv[]) {
system("COLOR
5");
int
*buffer = NULL, max;
printf("Implementasi
Bucket Sort\nMasukkan jumlah data [MAX:100] : ");
scanf("%d",&max);
fflush(stdin);
if((max
> 0) && (max <= MAX)) {
buffer
= (int*)calloc(max,sizeof(int));
InputOutput(buffer,max,INPUT);
printf("\nData
yang anda masukkan : ");
InputOutput(buffer,max,OUTPUT);
BucketSort(buffer,max);
printf("\nData
setelah disorting : ");
InputOutput(buffer,max,OUTPUT);
FreeBuffer(buffer);
}
TRACE_LINE;
getch();
fflush(stdin);
return(EXIT_SUCCESS);
}
void InputOutput(int* buffer, const
int max, const char STAT) {
int
i;
if('i'
== STAT) {
for(i
= 0; i < max; ++i) {
printf("%d.
Data ke-%d : ",(i+1),(i+1));
scanf("%d",&buffer[i]);
fflush(stdin);
}
}
else if('o' == STAT) {
for(i
= 0; i < max; ++i) {
printf("%d
",buffer[i]);
}
}
}
void BucketSort(int* buffer, const
int max) {
int
i, j, *count = (int*)calloc(max,sizeof(int));
for(i
= 0; i < max; ++i) {
count[i]
= 0;
}
for(i = 0; i < max; ++i) {
++(count[buffer[i]]);
}
for(i = 0, j = 0; i < max; ++i) {
for(;
count[i] > 0; --(count[i])) {
buffer[j++]
= i;
}
}
FreeBuffer(count);
}
void FreeBuffer(int* buffer) {
free(buffer);
buffer
= NULL;
}
2. 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
Contoh
algoritma radix sort untuk mengurutkan bilangan bulat positif, dengan jumlah
digit maksimal 3 :
|
313
|
354
|
123
|
321
|
543
|
756
|
834
|
675
|
Ø Pertama kita
harus membagi-bagi data sesuai dengan urutan terkanan
Ø Lihat
terlebih dahulu digit yang paling besar untuk menentukan kategori berapa baris
data yang akan kita urutkan, dan dicontoh ini nilai digit paling besar yaitu
angka 8, sehingga kategori sebanyak 8 baris dan diawali dengan angka 0.
Supaya lebih
jelas lihat table dibawah :
|
Kategori digit 1
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
isi
|
-
|
321
|
-
|
313,123,
543
|
354,834
|
675
|
756
|
-
|
-
|
Hasil dari
kategori pertama tadi akan digabungkan kembali sesuai dengan penjelasan diatas
;
|
321
|
313
|
123
|
543
|
354
|
834
|
675
|
756
|
Kemdian
dilakukan pengkategorian kembali berdasarkan dengan digit yang ke-2
dengan berpatokan / melihat baris urutan dari pengkategorian yang pertama tadi
.
|
Kategori digit 2
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
isi
|
-
|
313
|
321,123
|
834
|
543
|
354,756
|
-
|
675
|
-
|
|
313
|
321
|
123
|
834
|
543
|
354
|
756
|
675
|
Selanjutnya
hasil dari pengkategorian ke-2 digabungkan kembali sehingga diperoleh :
Langkah terakhir yaitu pengkategorian ke-3 berdasar digit ke-3 dengan
berpatokan melihat baris urutan pengkategorian ke-2
|
Kategori digit 3
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
isi
|
-
|
123
|
-
|
313,321,
354
|
-
|
543
|
675
|
756
|
834
|
Jadi, hasil
akhirnya dapat dituliskan :
|
123
|
313
|
321,
|
354
|
543
|
675
|
756
|
834
|
Dari proses2 yang sudah kita kerjakan menggunakan Radix Sort, sangat jelas
Radix sort termasuk algoritma pengurutan tanpa pembanding yang bersifat melihat
digit2 angka sebagai pengontrolnya. Sebenarnya Radix Sort dapat
diimplementasikan dalam pengurutan bilangan Decimal dan bilangan bit. Namun
dalam penggunaannya Radix Sort bisa dimodifikasi untuk mengurutkan data2
negatif & pecahan.
Kelebihan :
Ø Merupakan
algoritma pengurutan yang cepat, mudah dan sangat efektif
Kekurangan :
Ø pengguaannya
terbatas pada kasus2 tertentu dan memerlukan memori tambahan yang besar dalam
prosesnya mengkategorikan sebuah data.
//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;
}
Tidak ada komentar:
Posting Komentar