sorting in linear time
선형시간 정렬 알고리즘
Last updated
선형시간 정렬 알고리즘
Last updated
n개의 정수를 정렬한다. 모든 정수는 0에서 k사이의 정수이다.
사전정보가 주어진다.
일반적으로 k의 값은 작은 숫자인 경우가 많다.
예) n명의 학생들의 시험점수를 정렬한다. 단, 모든 점수는 100이하의 양의 정수이다.
0부터 5까지의 값이 8개 있다고 가정해보자.
A배열과 같이 숫자가 입력되었다.
어차피 나올 숫자의 범위가 0 <= x <= 5 임을 알고 있기 때문에, 입력으로 들어올 때, 각 숫자가 몇 번 들어왔는지를 카운트 한다.
이를 위해 배열 C에 각 데이터의 입력 횟수를 카운트한다.
각 값을 이미 알고 있고, 그 값이 나온 횟수를 알기 때문에, 그대로 정렬하면 된다.
이렇게 진행해도 괜찮은가?
아니다. 대부분의 경우, 정렬할 key 값들은 key 만 달랑 정수형태로 존재하는 것이 아니라, 데이터 레코드의 일부분이기 때문에 이런 식으로 정렬을 하면 안된다.
레코드들의 정렬은 제대로 될 수 없다.
배열 C에 count 를 할 때, 해당 데이터에 해당하는 것만 세는 것이 아니라, 해당 값보다 같거나 작은 것의 누적 합으로 카운팅한다.
즉 배열 C에 있는 각 값은 해당 index 보다 같거나 작은 값들의 개수가 된다.
배열 C의 결과만 보고 정렬을 시작한다.
배열 A에서 제일 마지막 값인 3을 선택한다. 3의 경우, 카운팅 결과를 보면, 3보다 같거나 작은 값이 7개가 된다. 따라서 정렬된 배열인 B에서 7번째 값에 3을 두면, 안전하다. 3은 정렬 완료이다.
3의 개수가 하나 줄었으므로, 3에 대한 카운터 값을 1 감소시켜 6으로 만든다.
그 다음 마지막 값인 0을 뽑는다. 0은 2개가 존재하니, 2번째 자리에 두면 안전하다. 다시 0에 대한 카운터를 1 줄인다.
위의 과정을 반복하면 정렬 완성이다.
O(n+k) 혹은 O(n)
보통 n >= k이다.
k가 아주 크다면, 매우 비 실용적이게 된다.
stable 정렬 알고리즘이라고 부른다.
입력이 동일한 값이 있을 때, 입력에 먼저 나오는 값이 출력에서도 먼저 나온다.
즉, 입력 순서대로 정렬되며 출력된다.
counting 정렬은 stable 하다.
