🚩[Algorithm] 1. 정렬 - 계수 정렬

계수정렬(counting sort)

---

1. 계수정렬이란?

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘

• <특정한 조건> 계수 정렬은 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.

• 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 ⭐수행 시간 O(N+K)를 보장한다.

• 주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다. ⭐최대값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다.

• ⭐계수 정렬은 특정한 조건이 부합될 때만 사용할 수 있지만 데이터 수가 많더라도 중복된 값이 많이 분포돼있는 배열을 정렬할 때 효과적이고 빠른 정렬 알고리즘이다. 최대, 최소 값 차이가 100만 이하일 경우 효과적이다. 카운팅 정렬이라고 하기도 한다. 선택, 삽입, 퀵 정렬처럼 데이터를 비교하며 위치를 변경하는 비교 기반의 정렬 알고리즘이 아니다.

2. 계수정렬의 조건

1. 데이터의 크기 범위가 제한된 경우
   • ex) 0 ~ 100 까지의 점수를 정렬하는 경우
2. 데이터가 양의 정수인 경우
   • 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못함
   • 인덱스를 이용한다는 것이 핵심이다.
3. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000(백만)을 넘지 않는 경우
   • 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아짐

3. 정렬 과정

⭐⭐
1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트를 생성
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
3. 증가된 리스트에서 0인 값을 제외하고, 인덱스를 인덱스 값만큼 출력

출처 : https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c

출처 : https://spagnuolocarmine.github.io/counting-sort.html

4. 코드 구현

1) 파이썬 - 리스트 자료형(배열) 활용

def counting_sort(arr):
    max_arr = max(arr)
    count = [0] * (max_arr + 1)	#⭐ 배열최대값+1만큼 인덱스 요소 만드는 동시에 배열 값 0으로 초기화
    sorted_arr = list()	# ⭐ 배열객체 sorted_arr 선언
    
    for i in arr:	# ⭐카운팅 (배열은 0부터 max_arr까지 존재하는 상태)
        count[i] += 1

    for i in range(max_arr + 1): # ⭐존재하는 인덱스 0~max_arr+1까지 
        for _ in range(count[i]):	# ⭐ 더미변수 '_'활용하여 count[i]에 저장된 값만큼 반복
            sorted_arr.append(i) # ⭐ sorted_arr에 i 붙이기
    return sorted_arr # ⭐ sorted_arr 반환

2) 파이썬 - 딕셔너리 자료형 활용

def counting_sort(arr):
    count = dict()
    sorted_arr = list()
    
    for i in arr:
        if i in count:
            count[i] += 1
        else:
            count[i] = 1

    for i in sorted(count.keys()):
        for _ in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr
    
 # 🌟<collections> 모듈의 defaultdict를 활용

from collections import defaultdict


def counting_sort(arr):
    count = defaultdict(int)
    sorted_arr = list()
    
    for i in arr:
        count[i] += 1

    for i in sorted(count.keys()):
        for _ in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr

3) Java - 배열, 누계 출력 등

public class CountingSort {
	public static void main(String[] args) {
		
		int[] array = new int[100];		// 수열의 원소 : 100개
		int[] counting = new int[31];	// 수의 범위 : 0 ~ 30
		int[] result = new int[100];	// 정렬 될 배열 
		
		for(int i = 0; i < array.length; i++) {
			array[i] = (int)(Math.random()*31);	// 0 ~ 30
		}
 
		
		// Counting Sort
		// 과정 1 
		for(int i = 0; i < array.length; i++) {
			// array 의 value 값을 index 로 하는 counting 배열 값 1 증가 
			counting[array[i]]++;			
		}
		
		// 과정 2 
		for(int i = 1; i < counting.length; i++) {
			// 누적 합 해주기 
			counting[i] += counting[i - 1];
		}
		
		// 과정 3
		for(int i = array.length - 1; i >= 0; i--) {
			/*
			 *  i 번쨰 원소를 인덱스로 하는 counting 배열을 1 감소시킨 뒤 
			 *  counting 배열의 값을 인덱스로 하여 result에 value 값을 저장한다.
			 */
			int value = array[i];
			counting[value]--;
			result[counting[value]] = value;
		}
		
		
		
		/* 비교 출력 */
		
		// 초기 배열 
		System.out.println("array[]");
		for(int i = 0; i < array.length; i++) {
			if(i % 10 == 0) System.out.println();
			System.out.print(array[i] + "\t");
		}
		System.out.println("\n\n");
		
		
		// Counting 배열 
		System.out.println("counting[]");
		for(int i = 0; i < counting.length; i++) {
			if(i % 10 == 0) System.out.println();
			System.out.print(counting[i] + "\t");
		}
		System.out.println("\n\n");
		
		
		// 정렬된 배열
		System.out.println("result[]");
		for(int i = 0; i < result.length; i++) {
			if(i % 10 == 0) System.out.println();
			System.out.print(result[i] + "\t");
		}
		System.out.println();
	}
 
}

⭐Java - 단순 출력

public class counting_sort {
	public static void main(String[] args) {
 
		int[] arr = new int[101]; // 수의 범위 : 0 ~ 100
 
		for (int i = 0; i < 50; i++) {	// 수열의 크기 : 50 
			arr[(int) (Math.random() * 101)]++;	// 0 ~ 100
		}
		
		for(int i = 0; i < arr.length; i++) {
			
			while(arr[i]-- > 0) {	// arr 값이 0보타 클 경우 
				System.out.print(i + " ");
			}
		}
	}
 
}

<실행결과>
0 1 6 6 9 10 14 14 16 16 19 21 23 25 25 27 31 36 39 40 40 42 43 46 46 48 49 53 54 55 55 63 66 67 67 68 74 76 76 77 78 79 79 89 91 92 93 96 97 98 

---

출처

• 컴공생의 다이어리 - 카운팅 정렬(Counting Sort, 계수 정렬) 알고리즘
• 카운팅 정렬(Counting Sort, 계수 정렬)이란?
• 이코테 파이썬 - 정렬
• 자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)