Sortowanie przez Zliczanie (Counting Sort)

Istnieje kruczek. Kto powiedział, że musimy coś ze sobą porównywać, żeby posortować tablicę?

Jeśli wiesz, że np. sprawdzian oceniany był w skali 0-100 punktów, i masz do posortowania milion wyników maturzystów z całego kraju, nie użyjesz sortowania bąbelkowego. Zamiast tego używamy Sortowania przez Zliczanie.

Jak działa zliczanie?

Tworzymy ogromną pustą "tablicę pomocniczą" (tzw. kubelki / koszyki), która indeksami obejmuje każdą możliwą wartość ze zbioru wejściowego (od 0 do 100).

1. Czytamy pierwszego ucznia, dostał 53 punkty. Idziemy do indeksu 53 w tablicy pomocniczej i robimy tam +1.
2. Drugi uczeń ma 90 punktów. Cyk, indeks 90 dostaje +1.
3. Na sam koniec przechodzimy przez naszą pomocniczą tablicę indeks od zera do 100. Gdy znajdziemy tam wartość 5000 pod indeksem 20, to pięć tysięcy razy wypisujemy cyfrę "20". Zrobi nam się piękna posortowana lista w czasie liniowym!

Python

def counting_sort(arr, max_val):
    # Tablica pomocnicza o rozmiarze o 1 większym niż maksymalna dopuszczalna liczba
    koszyki = [0] * (max_val + 1)
    
    # 1. Zliczamy wystąpienia w oryginalnej tablicy
    for liczba in arr:
        koszyki[liczba] += 1
        
    posortowane = []
    
    # 2. Przechodzimy po wszystkich koszykach
    for i in range(len(koszyki)):
        # Jeśli liczba wystąpiła np. 3 razy, appendujemy 3 razy
        for powtorzenie in range(koszyki[i]):
            posortowane.append(i)
            
    return posortowane

test = [3, 1, 9, 7, 1, 2, 4, 3, 3, 8]
print(counting_sort(test, 9)) 

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> countingSort(vector<int>& arr, int max_val) {
    vector<int> koszyki(max_val + 1, 0);
    
    for (int liczba : arr) {
        koszyki[liczba]++;
    }
    
    vector<int> posortowane;
    for (int i = 0; i <= max_val; i++) {
        for (int powtorzenie = 0; powtorzenie < koszyki[i]; powtorzenie++) {
            posortowane.push_back(i);
        }
    }
    
    return posortowane;
}

int main() {
    vector<int> test = {3, 1, 9, 7, 1, 2, 4, 3, 3, 8};
    vector<int> wynik = countingSort(test, 9);
    for(int x : wynik) cout << x << " ";
    return 0;
}

[!WARNING] Ten genialny algorytm ma ogromną wadę pamięciową. Co zrobisz, kiedy ktoś każe Ci posortować tylko dwie liczby, ale jedna z nich to 1, a druga to 1 000 000 000? Rozstrzał jest miliardowy! Aby użyć tego sortowania, Twoja pusta początkowa tablica koszyków musiałaby zużyć ogromne ilości RAMu. W takich wypadkach wkraczają Quicksort i Mergesort.