이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌8 - Algorithm - 2년 전 등록 / 일 년 전 수정

계수 정렬(counting sort)

조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

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

계수 정렬은 놀랍게도 작은 숫자에서는 복잡도가 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]

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

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

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

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

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

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));
이렇게 바꾸면 어떨까요??!
2년 전
감사합니다~~
2년 전
현우님이 주신 예시를 조금 수정하여 반영했습니다! 덕분에 편하게 수정했습니다.
2년 전
배열안에 0이 들어갔을 경우가 고려 안된것 같습니다..! array[j]-1 부분이요!!!
2년 전
그러네요. 수정해보겠습니다!