게시글

강좌8 - Algorithm - 4년 전 등록

계수 정렬(counting sort)

안녕하세요! 이번 시간에는 계수 정렬에 대해 알아보겠습니다.

계수 정렬은 놀랍게도 작은 숫자에서는 복잡도가 O(n + k)입니다. n+k는 처음 보죠? k가 정렬할 수들 중에 가장 큰 값을 의미하는데요. 만약 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있습니다. 예를 들어 10개의 숫자를 정렬하는 데, 가장 큰 숫자가 100일 경우, O(n^2)이 됩니다. 100(k)은 10(n)의 제곱이니까요. 1000이면 O(n^3)이 되죠. 즉 정렬할 수들의 최대값에 영향을 받는 알고리즘이라고 볼 수 있습니다.

방법은 매우 간단합니다. 모든 숫자의 개수를 센 후, 누적 합을 구하고, 다시 숫자를 넣어주면 됩니다.

[3,4,0,1,2,4,2,4], [개수를 저장할 공간], [결과]
개수를 저장할 공간을 정렬할 제일 큰 수의 갯수만큼 0으로 만들어줍니다.
[3,4,0,1,2,4,2,4], [0,0,0,0,0], [결과]
처음부터 개수를 세어 저장합니다. 0은 1개, 1은 1개, 2는 2개, 3은 1개, 4는 3개네요.
[3,4,0,1,2,4,2,4], [1,1,2,1,3], [결과]
개수를 저장한 것을 누적합으로 바꿔줍니다. 순서대로 1, 2, 4, 5, 8이 됩니다.
[3,4,0,1,2,4,2,4], [1,2,4,5,8], [결과]
누적합을 바탕으로 숫자를 결과에 넣어줍니다. 0은 1에, 1은 2에, 2는 3~4에 3은 5에, 4는 6~8에 넣어주면 됩니다.
[3,4,0,1,2,4,2,4], [1,2,4,5,8], [0,1,2,2,3,4,4,4]

정말 간단하죠? 누적합이 바로 숫자들의 인덱스 역할을 합니다. 1,3,4,7이 있으면 1은 0~1 사이에, 2는 1~3 사이에, 3은 3~4 사이에, 4는 4~7 사이에 넣으라는 뜻입니다. 코드로 볼까요?

var countingSort = function(array, k) {
  var count = [], result = [];
  for (var i = 0; i <= k; i++) { // 모든 숫자의 개수를 일단 0으로 초기화합니다.
    count[i] = 0;
  }
  console.log(count, result, array.length);
  for (var j = 0; j < array.length; j++) { // 숫자의 개수를 세어 저장합니다.
    count[array[j]] += 1;
  }
  console.log(count, result, k);
  for (i = 0; i < k ; i++) { // 누적합을 구합니다.
    count[i + 1] += count[i];
  }
  console.log(count, result);
  for (j = 0; j < array.length; j++) { // 누적합이 가리키는 인덱스를 바탕으로 결과에 숫자를  집어넣습니다.
    console.log(array[j], count[array[j]] - 1);
    result[count[array[j]] - 1] = array[j];
    count[array[j]] -= 1;
  }
  console.log(count, result);
  return result;
};
// 배열에 큰 수가 들어갈 수록 메모리를 많이 잡아먹기 때문에 좋지 않습니다.
countingSort([3,4,0,1,2,4,2,4], 4); // [0,1,2,2,3,4,4,4]

계수 정렬은 우리가 배운 알고리즘 중에 처음으로 비교 정렬이 아닙니다. 이전까지는 두 수를 비교하여 정렬했다면 이 방법은 단 하나의 비교도 일어나지 않았습니다. 그리고 같은 숫자라도 정렬할 때 순서가 섞이지 않는 안정 정렬입니다.

단, 정렬할 때 추가적인 메모리(숫자 개수를 저장할 공간, 결과를 저장할 공간)가 필요하다는 점과, 가장 큰 숫자에 영향을 받는다는 점은 단점입니다. 그래도 적은 개수의 숫자를 정렬할 때는 계수 정렬을 사용하세요.

다음 시간에는 기수 정렬에 대해 알아보겠습니다!

조회수:
0
목록
투표로 게시글에 관해 피드백을 해주시면 게시글 수정 시 반영됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright 2016- . 무단 전재 및 재배포 금지. 출처 표기 시 인용 가능.

댓글

4개의 댓글이 있습니다.
3년 전
언제나 양질의 강의 잘 보고 있습니다 이런글 쓰는거도 쉽지 않을텐데 정말 감사드려요
이번 정렬알고리즘은 400,401,404같이 각각의 최대값은 큰데 값의 범위는 작은 배열의 경우
최소값도 따로 구해서 카운팅배열의 크기를 최대값에서 최소값을 뺀만큼의 숫자로 만들어도 좋을 것 같네요
3년 전
좋은 아이디어입니다! 짝짝짝
3년 전
개수를 저장할 공간을 정렬할 제일 큰 수의 갯수만큼 0으로 만들어줍니다.
-> 제일 큰수가 4인데 그 갯수만큼이면 4개아닌가요..? 혹시 0~4까지 5개인가요??
저처럼 처음보는 사람들은 혹시나 이해못할까봐 질문드렸습니다 ㅎ
3년 전
0~4까지 5개입니다!
4년 전

var countingSort = function (array, k) {
var count = [], result = [];
for (var i = 0; i <= k; i++) { // 모든 숫자의 개수를 일단 0으로 초기화합니다.
count[i] = 0;
}
for (var j = 0; j < array.length; j++) { // 숫자의 개수를 세어 저장합니다.
count[array[j]] += 1;
}
for (i = 0; i <= k; i++) { // 누적합을 구합니다.
count[i + 1] += count[i];
}
for (j = 0; j < array.length; j++) {
if(!result[count[array[j]]]&&count[array[j]>0]){
result[count[array[j]]--] = array[j];
}else{
result[--count[array[j]]] = array[j];
}
}
return result;
};

//배열에 큰 수가 들어갈 수록 계수정렬은 좋지 않음... 메모리를 많이 잡아먹기 때문
console.log(countingSort([54, 6, 645, 67, 3, 5, 7, 856, 898, 9, 657, 57, 1, 567, 2, 0], 898));
이렇게 바꾸면 어떨까요??!
4년 전
감사합니다~~
4년 전
현우님이 주신 예시를 조금 수정하여 반영했습니다! 덕분에 편하게 수정했습니다.
4년 전
배열안에 0이 들어갔을 경우가 고려 안된것 같습니다..! array[j]-1 부분이요!!!
4년 전
그러네요. 수정해보겠습니다!