Counting Sorting

Counting Sorting, belirli bir aralıktaki tam sayıların sıralanması için kullanılan, karşılaştırma tabanlı olmayan bir sıralama algoritmasıdır. Algoritma, her sayının kaç kez geçtiğini sayarak çalışır ve bu sayımlara dayanarak sıralama işlemi gerçekleştirilir. Counting Sort, lineer zaman karmaşıklığına sahip olabilir, ancak yalnızca belirli bir aralıktaki sayılar üzerinde etkili çalışır. En iyi durum, en kötü durum ve ortalama durum: O(n + k), burada n dizi eleman sayısı, k ise elemanların alabileceği değerlerin aralığıdır (en büyük değere kadar). Java dili ile yazılmış bubble sorting algoritma örneğini aşağıda görebilirsiniz.

public static void countingSorting(int[] arr) {
        int n = arr.length;
        int max = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[max + 1];
        Arrays.fill(count, 0);
        for (int i = 0; i < n; i++) {
            count[arr[i]]++;
        }
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }
        int[] output = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }

public static void main(String [] args) {
        int[] array = { 24, 16, 35, 34, 10 };
        countingSorting(array);
}

Resim Referansı: https://gabrielghe.github.io/university/2016/03/09/counting-sort