[알고리즘] Counting sort (+ 백준 10989)

 

Counting sort

 

Counting sort는 정렬 알고리즘으로 시간 복잡도는 O(n)이다.

빠른 속도로 유명한 Quick sort의 시간 복잡도가 O(nlogn)이므로 counting sort의 속도는 상당히 빠르다. 

counting sort는 말 그대로 배열에 존재하는 숫자의 등장 횟수를 카운트해서 정렬한다.

 

 

<진행 과정>

 

1. 각 숫자의 등장 횟수를 카운트한다.

 

 

: A배열 원소의 범위를 0~5까지로 가정하면 B배열의 크기는 6이다.

B[idx] = A배열에 등장하는 숫자 idx가 등장하는 횟수

(ex. B[1] = A배열에서 1이 등장하는 횟수 = 1)

 

 

 

2. 등장 횟수를 누적 합으로 변경한다.

 

: B2[i] = B[i] + B[i-1] + B[i-2] + ... + B[0]

(ex. B2[2] = B[0]+B[1]+B[2])

 

 

 

3. 누적 횟수 배열을 이용하여 해당 숫자의 위치를 찾는다.

뒤에서 시작하는 것이 좋다:)

: A[5] = 3이므로 B2[3]의 값을 찾아 위치를 확인한다.

B2[3] = 4로 배열의 네번째 위치고 index로는 -1을 하여 C[3]이 자신의 위치다.

해당 값의 위치를 배정한 다음 누적 횟수의 값에서 -1을 해준다. (B2[3] = B2[3] -1)

 

 

 

: 위와 같은 과정을 반복하면 정렬된 배열을 얻을 수 있다.

 

 

 

정리 :  빠른 정렬이 가능하지만, 메모리 낭비가 발생할 수 있는 단점이 있다.

이에 Quick sort를 사용하는 경우가 많다.

 

 

 

활용) 백준 알고리즘 문제 10989

 

10989번: 수 정렬하기 3

 

: N개의 수가 주어졌을 때, 오름차순으로 정렬하는 프로그램 작성하기

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

class Main {
  public static void main(String[] args) throws IOException{
  
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine()); //수의 개수
    int[] carr = new int[10001]; //수의 범위가 10000이하의 자연수이기에 사이즈가 10000이다.

    for(int i = 0; i < N; i++)
      carr[Integer.parseInt(br.readLine())]++;

    br.close();
    
    //누적횟수를 구하지 않고 바로 정렬했다.

    StringBuilder sb = new StringBuilder();
 
        // 0은 입력범위에서 없으므로 1부터 시작
        for(int i = 1; i < 10001; i++){
            // i 값이 개수가 0 이 될 때 까지 출력 (빈도수를 의미)
            while(carr[i] > 0){
                sb.append(i).append('\n');
                carr[i]--;
            }
        }
    System.out.println(sb);
      
 
  }
}