계수정렬 Counting sort 계수정렬 별도의 메모리공간을 만들어서 각 원소값 만큼의 index에 해당 원소의 갯수를 채운 뒤 기존 배열의 값을 재설정하는 방식이다. 예를들어, 특정 값이 10만이라고 하면 해당 원소는 index 100,000에 채워지므로 메모리공간의 최대 길이는 10만까지 늘어나서 비효율적이다. 하지만 최대값의 크기가 적당하다면 효율적으로 사용할 수 있겠다. 시간복잡도는 O(n + k)이다. 여기서 k는 위에서 말한 최대 원소값을 뜻한다. 하지만 메모리공간을 HashMap으로 할당함으로써 워스트케이스에 어느정도 대처할 수 있다. 정렬방식 이와같이 별도의 메모리공간을 만들고, 각 원소 크기에 해당하는 index를 찾아 해당 원소 갯수만큼 채워넣는다. 모든 값을 채워넣었다면 최종적으로 ..