일반화해놔서 대부분의 컨테이너에 사용 가능.
정수만 사용 가능.
| 1234567891011121314151617181920212223242526272829303132 | #include //자연수만 받을 수 있는 버전입니다.template <class Container, class IntT>void counting_sort(Container& con, IntT max_num){ //카운팅용 배열 std::vector counting_array(max_num + 1, 0); //0까지 포함 //셉니다. for (const auto& e : con) counting_array[e]++; //도로 넣습니다. IntT i = 0; for (auto& e : con) { bool pushed = false; //넣었는지 확인하는 플래그입니다. while (!pushed) //하나 넣을때까지 돕니다. if (counting_array[i] == 0) //0이면 지나갑니다. i++; else //있으면 넣습니다. { e = i; //넣고 counting_array[i]--; //넣었으니까 빼고 pushed = true; //됐으니까 나갑니다. continue; } }} Colored by Color Scripter | cs |
| 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 | #include //-max ~ +max 양수 음수 둘다 받습니다.template <class Container, class IntT>void counting_sort(Container& con, IntT max_num){ //카운팅용 배열 std::vector counting_positive(max_num+1,0); //0까지 포함 std::vector counting_negative(max_num, 0); //0 제외 //셉니다. for (const auto& e : con) { if (e<0) //음수일 경우 counting_negative[-e]++; else //0이나 자연수일 경우 counting_positive[e]++; } //도로 넣습니다. IntT i = 0; //자연수 전용 반복자입니다. IntT neg_i = max_num - 1; //음수 전용 반복자입니다. for (auto& e : con) { bool pushed = false; //넣었는지 확인하는 플래그입니다. while (!pushed) //하나 넣을때까지 돕니다. if (neg_i>0) //음수 먼저 처리합니다. if (counting_negative[neg_i] == 0) //0이면 지나갑니다. neg_i--; else { e = -(neg_i + 1); //인덱스 고려해서 넣고 counting_negative[neg_i]--; //넣었으니까 빼고 pushed = true; //됐으니까 나갑니다. } else //음수 다 처리하고 양수를 처리합니다. if (counting_positive[i] == 0) //0이면 지나갑니다. i++; else //있으면 넣습니다. { e = i; //넣고 counting_positive[i]--; //넣었으니까 빼고 pushed = true; //됐으니까 나갑니다. } }} Colored by Color Scripter | cs |
가장 빠르다는 std::sort와 비교를 했다.
코드는 이렇고, 환경은 릴리즈모드에 x86이다.
단위는 나노초다.
케이스가 커질수록 빨라짐을 알 수 있다.