Done is better than perfect

| O(n) 정렬 비교 정렬의 하한은 O(nlogn)이지만 입력된 자료의 원소가 제한적인 성질을 만족하는 경우 O(n) 정렬이 가능하다. 대표적인 O(n) 정렬의 알고리즘으로는 Counting Sort와 Radix Sort가 있다. | Radix Sort Radix Sort 또한 자료의 원소가 제한적인 성질을 만족하는 경우 사용 가능한 O(n) 정렬 방법이다. 원소의 자릿수가 d자리 이하인 N개의 수들로 이루어진 경우 O(d * N)의 시간 복잡도를 갖는 정렬방법이다. 소개할 Radix Sort 구현 방법은 Counting Sort를 활용하는 방법이다. 낮은 자리부터 정렬을 하고 정렬된 순서를 유지하면서 보다 높은 자리를 정렬하는 과정에서 Counting Sort가 활용된다. 따라서 개수를 셀(Count..

| O(n) 정렬 비교 정렬의 하한은 O(nlogn)이지만 입력된 자료의 원소가 제한적인 성질을 만족하는 경우 O(n) 정렬이 가능하다. 대표적인 O(n) 정렬의 알고리즘으로는 Counting Sort와 Radix Sort가 있다. | Counting Sort 일반적으로 정수 또는 문자를 정렬하는 경우 많이 사용되는 방법으로, 원소의 범위가 제한적일 때 원소의 개수를 세어 정렬하는 방법이다. 개수를 셀 배열과 정렬된 결과가 저장될 배열이 추가로 필요하다. 다양한 구현 방법이 있지만, Radix Sort와 연관된 버전으로 알아보자. 기본 구현 방법은 아래와 같다. 1. 각 원소의 개수를 저장할 count 배열을 준비한다. 2. 정렬한 배열에 대하여 각 원소의 개수를 세어 count 배열에 저장한다. int..