Counting Sort

 

index table의 의미

현재 값이 들어가야할 sorted배열의 인덱스 값을 의미한다.

 

index table 구성 후 알고리즘

마지막 인덱스부터 왼쪽으로 이동하는 포인터를 이용하여

해당 값을 인덱스로 하여 index table에서 sorted 배열에 입력할 인덱스 위치를 가져온다.

그 후에 해당 index table의 값을 1 감소 시킨다.

 

 

 

#include <bits/stdc++.h>



void CountingSort(std::vector<int> & arr) {

    int max = INT_MIN;
    int min = INT_MAX;
    for (int e : arr) {
        max = std::max(max, e);
        min = std::min(min, e);
    }
    int k = max - min + 1;
    
    std::vector<int> sorted(arr.size());
    std::vector<int> count(k);
    std::vector<int> acc_count(k);
    std::vector<int> end_locs(k);

    for (int e : arr) {
        ++count[e- min];
    }
    int acc = 0;

    for (int i = 0; i < k; ++i) {
        acc += count[i];
        acc_count[i] = acc;
    }

    for (int i = 0; i < k; ++i) {
        end_locs[i] = acc_count[i] - 1;
    }
    
    for (int i = arr.size() - 1; i >= 0; --i) {
        int num = arr[i];
        int idx = num - min;
        int end_loc = end_locs[idx];
        sorted[end_loc] = num;
        --end_locs[idx];
    }

    for (int i = 0; i < arr.size(); ++i) {
        arr[i] = sorted[i];
    }
}




void printArr(std::vector<int> arr){
    for (auto ele : arr) {
        std::cout << ele << " ";
    }
    std::cout << "\n";
}



int main(int argc, char** argv) {

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::vector<int> arr = {3, 5, 7, 9, 4, 2};
    std::cout << "before : ";
    printArr(arr);
    
    CountingSort(arr);

    std::cout << "after  : ";
    printArr(arr);

    arr = {3, 0, 5, 1, 0, 5};
    std::cout << "\n";
    std::cout << "before : ";
    printArr(arr);
    
    CountingSort(arr);

    std::cout << "after  : ";
    printArr(arr);
	return 0;
}

 

 

정리

시간복잡도 O(n + k)   k = 최댓값 - 최솟값 + 1

공간복잡도 max(O(n), O(k))

Stable : O