☑️카운팅 정렬

백준 2751번을 풀고 시간 초과로 애를 먹던 중 counting 정렬을 접하게 되었다
st_lab님의 글을 보고 내 언어로 정리한 것이다

---

개요

퀵 정렬, 합병 정렬 등은 O(nlogn)의 시간 복잡도를 갖는다. 특히 퀵 정렬은 최악의 경우 O(n^2)의 시간복잡도를 갖는다 (Array.sort를 쓰면 2751에서 시간 초과가 나는 이유)

카운팅 정렬은 시간복잡도가 O(n)이다. 엄청나게 빠르다

---

알고리즘

• 데이터의 중복이 있을 경우
  • 데이터의 값이 몇 번 나왔는지 세어 저장
  • counting한 개수의 누적 합을 저장
  • 결과 배열에 값 저장
  • 출력
• 데이터 중복이 없을 경우
  • 해당하는 인덱스의 값을 true로 초기화
  • true인 것만 출력

정말 매우 간단하다

---

구현

int array[] : 정렬해야할 값들이 있는 배열
int counting[] : 값들의 빈도를 저장하는 배열 (수의 범위와 크기 동일)
int result[] : 정렬이 완료된 배열 (array[]와 크기 동일)

1단계
array[]의 인덱스 0부터 array.length-1 까지 돌면서 그 값을 인덱스로 하는 counting[] 의 값을 증가시킨다 (데이터가 중복되기 때문에 데이터가 단순히 있다, 없다만 표시해서는 안 됨)

그러니까 array[0]=3 이면 counting[3]++; 을, array[1]=6 이면 counting[6]++; 해주는 것이다

2단계

1단계가 끝나면 counting 배열에는 인덱스에 해당하는 데이터의 개수가 저장되어 있을 것이다
이것을 누적합으로 바꿔준다 (시작 위치를 알기 위해서)
즉 counting[i]=counting[i-1]+counting[i] 를 반복한다

3단계

2단계까지 끝났으면 counting에는 시작 위치+1이 저장되어 있다
즉 counting[7]=6 이라면 7의 시작 위치는 6-1 을 한 result[5] 라는 것이다

만약 array[]를 순환하면서 같은 값이 여러 개 있을 경우 시작 위치로부터 한 칸씩 앞에다가 저장하므로 result[] 에 저장하는 순간에 counting[] 값을 하나씩 감소시켜주어야 한다

범위는 0~30, 정렬 개수는 100인 예제를 해보면 다음과 같다

public class CountingSort {
    public static void main(String[] args) {
        int array[]=new int[100];
        int counting[]=new int[31];
        int result[]=new int[100];
        for (int i=0;i<array.length;i++){
            array[i]=(int)(Math.random()*31);// 범위 0~30 랜덤으로
        }
        for(int i=0;i< array.length;i++){
            counting[array[i]]++; //array 값에 해당하는 counting 인덱스의 값 증가
        }
        for(int i=1;i< counting.length;i++){
            counting[i]=counting[i]+counting[i-1]; //누적합 구하기
        }
        for(int i= array.length-1;i>=0;i--){//array 배열 끝부터 순회하면서
            int a=--counting[array[i]]; //counitng값 감소시키고 a에 저장
            result[a]=array[i]; // result 배열의 인덱스 a에 array값 저장
        }
    }
 }

---

느낀 점: 진짜 쉬운데 내가 이해한 그대로를 적는게 어렵다 .. 뭔가 확연한 말이 있으면 좋겠는데 하여튼 counting의 인덱스 = 정렬할 값 counting의 값 = 특정 값의 빈도 수

이미 인덱스가 오름차순으로 되어있기 때문에 특별히 정렬할 필요가 없는 것이다..

그래서 시간 복잡도가 O(n) 인것이다. 순회만 몇 번 해주면 되니까 ..