Jawaban:

Algoritma Radix Sort digunakan untuk mengurutkan bilangan integer dengan membandingkan digit-digit pada setiap posisi angka. Berikut adalah algoritma dan langkah-langkah manual untuk Radix Sort:

Algoritma Radix Sort:

Tentukan jumlah digit maksimal pada bilangan yang akan diurutkan

Untuk setiap digit dari digit terendah hingga digit tertinggi, lakukan:

a. Buat 10 buah bucket (antrian) kosong

b. Letakkan setiap bilangan pada bucket yang sesuai dengan digit yang sedang diperiksa, mulai dari digit terendah

c. Kumpulkan kembali bilangan dari bucket sesuai dengan urutan bucket-nya (dari 0 hingga 9)

d. Ulangi proses ini hingga semua digit telah diperiksa

Bilangan telah terurutkan

Langkah-langkah manual Radix Sort:

Misalnya kita ingin mengurutkan bilangan {170, 45, 75, 90, 802, 24, 2, 66} menggunakan Radix Sort.

Tentukan digit maksimal pada bilangan, dalam kasus ini adalah 3 digit.

Urutkan bilangan berdasarkan digit terendah (satuan):

a. Masukkan setiap bilangan ke bucket sesuai dengan digit satuan-nya. Contoh: 170, 90, dan 2 dimasukkan ke bucket 0; 802 dimasukkan ke bucket 2; 24 dan 75 dimasukkan ke bucket 5; 45 dimasukkan ke bucket 6; 66 dimasukkan ke bucket 6.

b. Kumpulkan bilangan dari bucket secara berurutan, mulai dari bucket 0 hingga 9. Bilangan yang telah terkumpul adalah {170, 90, 2, 802, 24, 75, 45, 66}.

Urutkan bilangan berdasarkan digit pada posisi puluhan:

a. Masukkan setiap bilangan ke bucket sesuai dengan digit puluhan-nya. Contoh: 170, 90, dan 802 dimasukkan ke bucket 0; 2 dan 24 dimasukkan ke bucket 2; 45 dimasukkan ke bucket 4; 66 dimasukkan ke bucket 6; 75 dimasukkan ke bucket 7.

b. Kumpulkan bilangan dari bucket secara berurutan, mulai dari bucket 0 hingga 9. Bilangan yang telah terkumpul adalah {2, 24, 45, 66, 75, 90, 170, 802}.

Urutkan bilangan berdasarkan digit pada posisi ratusan:

a. Masukkan setiap bilangan ke bucket sesuai dengan digit ratusan-nya. Contoh: 2 dan 24 dimasukkan ke bucket 0; 45 dimasukkan ke bucket 4; 66 dimasukkan ke bucket 6; 75 dimasukkan ke bucket 7; 90 dimasukkan ke bucket 9; 170 dimasukkan ke bucket 1; 802 dimasukkan ke bucket 8.

b. Kumpulkan bilangan dari bucket secara berurutan, mulai dari bucket 0 hingga 9. Bilangan yang telah terkumpul adalah {2, 24, 45, 66, 75, 90, 170, 802}.

Berikut adalah program Java untuk algoritma Radix Sort menggunakan method main():

import java.util.Arrays;

public class RadixSort {

   public static void radixSort(int[] arr) {

       int maxDigit = getMaxDigit(arr);

       int exp = 1;

       for (int i = 0; i < maxDigit; i++) {

           int[] bucket = new int[10];

           for (int j = 0; j < arr.length; j++) {

               int digit = (arr[j] / exp) % 10;

               bucket[digit]++;

           }

           for (int j = 1; j < 10; j++) {

               bucket[j] += bucket[j - 1];

           }

           int[] output = new int[arr.length];

           for (int j = arr.length - 1; j >= 0; j--) {

               int digit = (arr[j] / exp) % 10;

               output[bucket[digit] - 1] = arr[j];

               bucket[digit]--;

           }

           for (int j = 0; j < arr.length; j++) {

               arr[j] = output[j];

           }

           exp *= 10;

       }

   }

   public static int getMaxDigit(int[] arr) {

       int maxDigit = 1;

       int base = 10;

       for (int num : arr) {

           int digit = 1;

           while (num >= base) {

               digit++;

               num /= base;

           }

           if (digit > maxDigit) {

               maxDigit = digit;

           }

       }

       return maxDigit;

   }

   public static void main(String[] args) {

       int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

       System.out.println("Before sorting: " + Arrays.toString(arr));

       radixSort(arr);

       System.out.println("After sorting: " + Arrays.toString(arr));

   }

}

Program ini mengandung 3 method, yaitu:

radixSort: method utama untuk melakukan Radix Sort. Method ini mengambil sebuah array integer sebagai parameter dan mengurutkan elemen-elemennya menggunakan algoritma Radix Sort.

getMaxDigit: method untuk mencari digit maksimal pada bilangan yang akan diurutkan. Method ini mengambil sebuah array integer sebagai parameter dan mengembalikan digit maksimal pada bilangan tersebut.

main: method utama untuk menjalankan program. Method ini menginisialisasi sebuah array integer, memanggil method radixSort untuk mengurutkan array tersebut, dan menampilkan hasil sebelum dan sesudah diurutkan.