Count Sort

Sort는 보통 가장 빠른게 nlogn 이라는 것은 들어봤을 것이다.

그러나 특정 조건에 한해서는 더 줄여질 수 있는데, Count Sort를 활용하면 n으로 줄일 수 있다.

 

Count Sort에서 조건이라면, data의 범위가 될 것이다.

Count Sort에 대해 자세히 알아보려면 아래 동영상을 참고하면 된다.

 

www.youtube.com/watch?v=7zuGmKfUt7s

먼저 해당 data가 가능한 범위의 크기 만큼 array를 만들고,

한번 쭉 data를 훑으면서, 어떤 값이 나오면 그 값을 index로 보고 list[index]의 값을 +1 해준다.

이렇게 되면 어떤 값이 몇번 나왔는지 알게되고

나중에 리스트를 처음부터 훑으면서 순서대로 다시 쭉 써주면 된다.

 

n + 데이터의 범위가 time 관련 값이므로, n이 되고

여기서 단점은 데이터의 범위가 넓어질수록 메모리를 차지하는 게 커질 수 있다는 점이다.

 

참고

<백준 10989번>

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3