Skip to content

Latest commit

 

History

History
144 lines (97 loc) · 5.37 KB

Counting-sort.md

File metadata and controls

144 lines (97 loc) · 5.37 KB
Raw

계수 정렬(Counting Sort)

비교정렬(comparison sort)의 시간복잡도의 하한은 O(nlogn) 이다.

계수 정렬은 non-comparison sort 기법이며, 정렬에 드는 계산복잡도을 O(n) 으로 낮추기 위한 알고리즘이다.

정확히 말하면, 정렬할 수 중 가장 큰 값을 k라고 했을 때 계수정렬의 계산복잡도는 O(n+k) 이다.

따라서 정렬할 수의 최대값이 낮을때 효과적이며, k의 값이 매우 커지게 되면 다른 정렬 알고리즘에 비해 성능이 떨어진다.

가령 k가 n^2보다 커지게 되는 경우 선택, 삽입, 버블 정렬 등의 기본적인 정렬 알고리즘보다도 속도가 느리게 된다.

수행 과정

계수 정렬은 정렬하려는 수들의 개수를 세어 누적합을 구한 뒤, 누적합에 따라 수를 정렬하는 것이다.

이 때, 정렬 대상의 원소는 모두 양의 정수여야한다.

  1. 정렬 대상에서 중복되는 값의 개수를 구하여 저장한다.
  2. 저장한 중복 횟수를 누적합으로 바꾼다.
  3. 정렬 대상을 역순으로 순회하며 결과를 출력한다.

예시1

// 아래의 배열을 정렬
arr = {2, 0, 2, 0, 4, 1, 5, 5, 2, 0, 2, 4, 0, 4, 0, 3}

  • 배열 arr 에 들어있는 요소들이 몇 개씩 들어있는지 파악한다.

    cnt = {5, 1, 4, 1, 3, 2}
cnt[0] 0의 개수이다. 배열 A에 0이 5개 들어있기 때문에 cnt[0] 의 값은 5가 된다.

  • 배열 cnt 의 요소값에 이전 요소들의 누적값을 더해준다.

    cnt = {5, 6, 10, 11, 14, 16}
cnt[1] = cnt[0] + cnt[1] // 5 + 1
cnt[2] = cnt[0] + cnt[1] + cnt[2] // 5 + 1 + 4
cnt[3] = cnt[0] + cnt[1] + cnt[2] + cnt[3] // 5 + 1 + 4 + 1
...

    이 과정을 거치지 않고, 순서대로 출력하면 된다고 생각할 수 있다.

    이 경우 정렬 대상의 최대값에 큰 영향을 받기 때문에 오히려 비효율적이다.

    non-comparison 방식으로 정렬을 하기 위해서는 배열 cnt 의 길이가 정렬 대상의 최대값과 같아야하기 때문이다.

    각 요소를 비교하지 않고 누적합을 이용하기 때문에 non-comparison이 된다.

    또한, 원본배열을 역순으로 순회하며 정렬하는 방식을 이용하면 stable한 상태를 유지할 수 있다.

    stable하다는 것은 처음 순서대로 정렬이 된다는 것인데, 위의 예시에서는 첫 번째 0과 두 번째 0이 뒤바뀌지 않고 정렬된다. 이는 아래 예시2 에서 설명할것이다.

  • 배열 arr 의 요소값을 역순으로 저장한다.

    int[arr.length] result; // 결과값 배열의 크기는 정렬 대상과 같아야 한다.
for(i = arr.length-1; i>=0; i--){
  result[cnt[arr[i]] = arr[i];
  /* 배열 cnt의 값이 result의 인덱스가 되기 때문에,
   * 값을 저장한 수의 누적값을 감소시켜야 한다.
   */
  cnt[arr[i]]--;
}

예시2

계수정렬은 stable한 정렬이고, 이를 위해 카운팅 이후 한 번의 과정을 더 거친다.

숫자의 정렬 예시 만으로는 그 이유가 한 눈에 들어오지 않을 수 있다.

좀 더 쉬운 이해를 위해 이번에는 단어 banana 를 정렬해보자.

확인을 위해 순번 seq 필드를 추가한 Alphabet 타입을 사용할 것이다.

Alphabet{
  int seq = 0;
}

Alphabet b, a, n, a, n, a = new Alphabet();

// 아래의 배열을 정렬
Alphabet[] word = {b, a, n, a, n, a};

word를 카운팅한 누적합의 인덱스는 쉬운 이해를 위해 영문으로 표기할 것이다.

또한 크기가 a...n 이고 각 요소가 0으로 초기화된 배열 count 가 있다고 가정한다.

// 중복 개수 카운팅
for(Alphabet alphabet : word){
  count[alphabet] ++;
  // 카운팅 순서 저장
  alphabet.seq = count[alphabet];
}
// 누적합
for(int i = 1; i < word.length; i ++;){
  word[i] += word[i-1];
}

누적합이 구해진 count 배열은 아래와 같을 것이다.

a b n
3 4 6

예시1과 마찬가지로, 배열 word 에 저장된 알파벳을 역순으로 꺼내서 결과 배열에 저장하면 stable하게 저장된 결과를 얻을 수 있을 것이다.

역순으로 꺼내는 것과 비교 하기 위해 이번에는 원본 배열을 앞에서 부터 순회해보자.

// word == {b, a, n, a, n, a};
// count == {3, 4, 6}

result[3] = b; // b.seq == 1, count == {3, 3, 6}
result[2] = a; // a.seq == 1, count == {2, 3, 6}
result[5] = n; // n.seq == 1, count == {2, 3, 5}
result[1] = a; // a.seq == 2, count == {1, 3, 5}
result[4] = n; // n.seq == 2, count == {1, 3, 4}
result[0] = a; // a.seq == 3, count == {0, 3, 4}

앞에서부터 정렬할 경우도 a a a b n n 의 순서로 정렬되는 것은 동일하지만, 원본 배열 word 와 순서가 달라진 정렬이 된다.

이는 stable한 정렬이 아니다. result[0] 의 a 는 word[5] 의 a 와 같고, result[1] 의 a 는 word[3] 의 a 와 같기 때문이다.

stable한 정렬은 result[0] 의 a 가 word[1] 의 a 와 같아야 하고 result[1] 의 a 가 word[3] 의 a 와 같아야 한다. 즉 원본 배열의 순서를 유지한채로 정렬이 되어야 한다.

References