1

Pertemuan 23

Radix Sort

Matakuliah : T0456 ~ Algoritma dan Metode Object Oriented Programming

Tahun : 2005

Versi : 5

2

Learning Outcomes

Pada akhir pertemuan ini, diharapkan:

Mahasiswa dapat Menjelaskan kembali algoritma Radix sort

3

Outline Materi

• Algoritma Radix Sort

• Penerapan Radix Sort

4

Sorting

Sorting merupakan proses mengurutkan data sesuai aturan tertentu:

Ascending: dari terkecil sampai terbesar

Descending: dari terbesar sampai terkecil

Tujuan sorting adalah untuk mempercepat proses pencarian (searching) data

5

Sorting

Teknik pengurutan sederhana:

Bubble sort

Selection sort

Insertion sort

Teknik pengurutan lanjut:

Quick sort

Merge sort

Radix sort

6

RadixSort

Radix sort mengurutkan data berdasarkan posisi digit dalam angka atau karakter dalam string.

Pengurutan bisa dilakukan dari posisi digit terakhir/terkanan (LSD-least significant digit) atau digit awal/terkiri (MSD-Most significant digit).

Radix sort digunakan untuk mengurutkan data sebagai kelompok karakter atau string.

7

RadixSort

Sebagai gambaran radix sort dapat digunakan untuk mengurutkan string sebagai berikut: ABC, XYZ, BWZ, AAC, RLT, JBX, RDT, KLT, AEO, TLJ

Untuk mengurutkannya pertama diurutkan berdasarkan karakter terakhir pada string dan dikelompokkan berdasarkan karakter tersebut.(ABC, AAC) (TLJ) (AEO) (RLT, RDT, KLT) (JBX) (XYZ, BWZ)

Kombinasikan hasil pengelompokan:ABC, AAC, TLJ, AEO, RLT, RDT, KLT, JBX, XYZ, BWZ

8

RadixSort

Selanjutnya kelompokkan berdasarkan urutan abjad karater yang tengah(AAC) (ABC, JBX) (RDT) (AEO) (TLJ, RLT, KLT) (BWZ) (XYZ)

Kombinasikan kembali hasilnya:AAC, ABC, JBX, RDT, AEO, TLJ, RLT, KLT, BWZ, XYZ

Kemudian kelompokan berdasarkan abjad pertama dari string, diperoleh:(AAC, ABC, AEO) (BWZ) (JBX) (KLT) (RLT, RDT) (TLJ) (XYZ)

Terakhir gabungkan hasil pengelompokan sehingga diperoleh:AAC, ABC, AEO, BWZ, JBX, KLT, RLT, RDT, TLJ, XYZ

9

RadixSort

Disamping itu radix sort dapat juga digunakan untuk mengurutkan bilangan.

Contoh, Radix sort pada array suatu bilangan 4 digit bilangan interger:

Data awal:0123, 2154, 0222, 0004, 0283, 1560, 1061, 2150

10

RadixSort

Sort berdasarkan digit terakhir:[0] – (1560, 2150)[1] – (1061)[2] – (0222)[3] – (0123, 0283)[4] – (2154, 0004)[5] – ( )[6] – ( )[7] – ( )[8] – ( )[9] – ( )

Kombinasikan hasilnya dan tulis ke penampung awal:1560, 2150, 1061, 0222, 0123, 0283, 2154, 0004

11

RadixSort

Sort berdasarkan digit kedua dari kanan:[0] – (0004)[1] – ( )[2] – (0222, 0123)[3] – ( )[4] – ( )[5] – (2150, 2154)[6] – (1560, 1061)[7] – ( )[8] – (0283)[9] – ( )

Kombinasikan hasilnya dan tulis ke penampung awal:0004, 0222, 0123, 2150, 2154, 1560, 1061, 0283

12

RadixSort

Sort berdasarkan digit ketiga dari kanan:[0] – (0004, 1061)[1] – (0123, 2150, 2154)[2] – (0222, 0283)[3] – ( )[4] – ( )[5] – (1560)[6] – ( )[7] – ( )[8] – ( )[9] – ( )

Kombinasikan hasilnya dan tulis ke penampung awal:0004, 1061, 0123, 2150, 2154, 0222, 0283, 1560

13

RadixSort

Sort berdasarkan digit ke empat dari kanan:[0] – (0004, 0123, 0222, 0283)[1] – (1061, 1560)[2] – (2150, 2154)[3] – ( )[4] – ( )[5] – ( )[6] – ( )[7] – ( )[8] – ( )[9] – ( )

Kombinasikan hasilnya dan tulis ke penampung awal:0004, 0123, 0222, 0283, 1061, 1560, 2150, 2154

14

Pseudocode RadixSort dari N bilangan dengan d digit:

RadixSort(A, N, d){ // sort N d-digit integer in the array A for (J = d down to 1){ Initialise 10 groups to empty Initialize a counter for each group to 0 for (I = 0; through N-1){ K = Jth digit of A[I] Place A[I] at the end of group K Increase Kth counter by 1 } replace the items in A with all the items in group 0, followed by all the items in group 1, and so on. }}

15

Fungsi radix sort untuk bilangan bulat

void RadixSort(int *data, int N) {

int ember[10][N], cacah[10];

int max=data[0], sisa, idx;

// Hitung jumlah putaran

for (int j=1; j<N; j++)

if (data[j]>max) max = data[j];

int ronde = 0;

for ( ; max>0; max /= 10)

ronde++;

for (int k=0; k<ronde; k++) {

for(int m=0; m<10;m++)

cacah[m] = 0;

unsigned long pembagi = pow(10, k);

16

// masukan data ke ember

for (int j=0; j<N; j++) {

sisa = (data[j]/pembagi)%10;

for (int t=0; t<10; t++)

if (sisa == t)

ember[t][cacah[t]++] = data[j];

}

//copy data hsl pengelompokan ke array awal

idx=0;

for (int m=0; m<10; m++) {

if (cacah[m] != 0)

for (int t=0; t<cacah[m]; t++)

data[idx++] = ember[m][t];

}

}

}

17

Latihan

1. Mengapa jumlah penampung yang digunakan pada radixsort untuk mengurutkan bilangan bulat berjumlah 10?

2. Simulasikan radixsort dari digit terkanan terhadap data sebagai berikut: 295, 94, 411, 81, 535, 312, 64, 617, 756, 89, 75.

3. Simulasikan pengurutan data berikut dengan radixsort dari karakter paling kanan: saya, suka, gemas, karena, tau, ayam, kamu, miring, dan, gemar, tahu, kecap.

18

Penutup

• Untuk dapat Menjelaskan kembali algoritma radix sort, mahasiswa membahas tugas pertemuan 23 no 1, 2, dan 3.

(diskusikan dalam kelompok)