Jawaban:

Algoritma Counting Sort

Counting Sort adalah algoritma pengurutan dengan kompleksitas waktu O(n+k), di mana n adalah jumlah elemen yang akan diurutkan dan k adalah rentang nilai yang diizinkan.

Berikut adalah langkah-langkah Counting Sort:

Buat array count berukuran k dan isi dengan 0.

Iterasi pada array yang akan diurutkan untuk menghitung kemunculan setiap elemen dan simpan dalam array count.

Hitung akumulasi count sehingga setiap elemen pada count[i] berisi jumlah elemen yang kurang dari atau sama dengan i.

Buat array hasil berukuran sama dengan array awal untuk menampung hasil pengurutan.

Iterasi pada array awal, dan letakkan setiap elemen pada posisi yang tepat dalam array hasil menggunakan count.

Tampilkan hasil pengurutan.

Berikut adalah implementasi Java dari algoritma Counting Sort menggunakan method main():

import java.util.Arrays;

public class CountingSort {

   public static void main(String[] args) {

       int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

       System.out.println("Array sebelum pengurutan: " + Arrays.toString(arr));

       int k = Arrays.stream(arr).max().getAsInt() + 1;

       int[] count = new int[k];

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

           count[arr[i]]++;

       }

       for (int i = 1; i < k; i++) {

           count[i] += count[i - 1];

       }

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

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

           hasil[--count[arr[i]]] = arr[i];

       }

       System.out.println("Array setelah pengurutan: " + Arrays.toString(hasil));

   }

}

OUTPUT

Array sebelum pengurutan: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Array setelah pengurutan: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]