내일은 알고리즘

카운팅 소~트 밤 하늘의 퍼얼~ 

오늘은 여섯 번째 정렬 알고리즘이자, 시간 복잡도가 O(N+K)인 특이한 정렬 알고리즘.
계수정렬(Counting sort)에 대해 알아보겠습니다.

1. 데이터의 범위를 전부 표현가능한 자료구조(배열,리스트 whatever)를 준비한다.
2. 데이터를 한 번 순회하면서 각 값의 갯수를 세어준다.
3. 알게 된 갯수만큼 데이터를 저장하거나 출력하면 정렬이 끝!

기존의 정렬들과는 달리 딱 한 번만 데이터를 순회하면 정렬이 완료됩니다.

그림과 함께 정렬의 순서를 확인 해보겠습니다.

1~5 범위의 데이터가 무작위로 준비되어 있습니다.

데이터를 전부 표현 가능한 5 사이즈의 배열을 준비했습니다.

정렬되지 않은 첫 데이터의 값은 3입니다.

값을 셀 배열에서 3의 값을 의미하는 위치의 값을 1 증가시킵니다.

두번째 데이터의 값은 2입니다.

마찬가지로 배열에서 2의 위치의 값을 1 증가시킵니다.

이런 방법으로 데이터를 한 번 순회하면...

위 처럼 정렬되지 않은 데이터가 몇개의 값으로 이루어진지 알 수 있습니다.

이제 값을 센 결과를 통해 정렬된 데이터를 만들어 봅시다.

1의 값을 가진 데이터가 2개이니 2개를 출력(혹은 정렬 후의 배열에 저장)

2의 값을 가진 데이터의 갯수도 2개이니 똑같이 출력

같은 작업을 끝까지 해주면 짠! 하고 정렬된 데이터를 얻게 됩니다.

이해하기도 쉽고 구현도 쉽고 시간복잡도까지 빠른 정렬 알고리즘입니다.

하지만 계수정렬은 특정 상황에서만 유용하게 쓰입니다.

시간복잡도 O(N+K)에서 알 수 있듯, K값인 데이터의 범위에 따라 그 효율성이 크게 달라지기 때문입니다.

예를 들어, 100명이 100점 만점의 시험을 본 점수결과 데이터를 정렬한다고 해봅시다.

K값은 100이고 이 데이터를 정렬하는데엔 대략 200번의 연산이면 충분할겁니다.

반면 100명의 연봉 데이터를 정렬한다고 해봅시다.

100명중에 능력있는 프로그래머가 한 명 있어서 최댓값이 1억이라고 생각해보면 K값은 1억이 되고 이 데이터를 정렬하는데엔 약 1억번의 연산이 필요합니다!

같은 100개의 데이터를 정렬하는데 효율성이 엄청나게 차이가 나죠.

따라서 계수정렬은 특정 상황에서만 유용하게 쓸 수 있는 정렬알고리즘입니다. 

아래는 간단하게 계수정렬을 구현한 JAVA코드 입니다.

디버깅 해보시며 정렬의 흐름을 따라해보시길 바랍니다.

import java.util.Arrays;
import java.util.Random;

public class sort_06_counting {
	static int size = 50;
	static int bound = 10;
	static int count = 0;
	// 데이터의 갯수와 범위 설정

	public static void main(String[] args) {
		int[] data = new int[size];
		Random random = new Random();

		for (int i = 0; i < size; i++) {
			data[i] = random.nextInt(bound);
		}
		// 랜덤 값 넣어주기

		System.out.println(Arrays.toString(data));
		// 랜덤하게 들어간 데이터 확인

		//////////////// 계수정렬 구현코드는 하단으로 /////////////////
		countingSort(data, bound);
		//////////////////////////////////////////////////////

		System.out.println(Arrays.toString(data));
		System.out.println("비교횟수 : " + count);
	}

	private static void countingSort(int[] data, int bound) {
		int[] countingsort = new int[bound + 1];
		int idx = 0;

		for (int i = 0; i < data.length; i++) {
			countingsort[data[i]]++;
			count++;
		}
		
		for (int i = 0; i < bound; i++) {
			count++;
			for(int j = 0; j < countingsort[i]; j++) {
				data[idx++] = i;
			}
		}

	}
}