Java - 정렬 알고리즘 - 6 (계수 정렬)

◎계수 정렬

정수들로 이루어진 배열을 원소들의 비교를 하지않고, 최소값과 최대값 사이에 존재하는 원소의 개수를 세어서 정렬하는 방식

---

◎계수 정렬의 특징

 

1. 비교 정렬(comparison sort)이 아니다

 계수정렬은 데이터를 비교하면서 찾지 않는다

 

2. 제자리 정렬(in-place sort)이 아님

정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 한다

 

3.  안정 정렬(stable sort)

정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다.

---

◎계수 정렬의 동작

※계수 정렬은 원소들의 최댓값과 최솟값을 안다는 가정하에 실행된다

 

1. 배열 내에 원소 값들의 갯수를 저장하는 카운팅 배열을 만든다.

- 카운팅 배열의 길이는 '원소들의 최댓값 - 원소들의 최소값 + 1'이다.

(ex. 최댓값이 5, 최솟값이 0이라면 카운팅 배열의 길이는 6이다.)

 

2. 배열을 idx 순서대로 살펴보면서 원소가 나온 횟수를 카운팅 배열에 누적시킨다.

(ex. [2,4,2]인 배열이 있다면, 최댓값이 4, 최솟값이 2이므로 카운팅 배열의 길이는 3이고, 2가 2번 4이 1번 나오므로

카운팅 배열은 [2,0,1]의 값을 가진다)

 

3. 카운팅 배열에 대해서 직전 요소들의 값을 더해준다.

(ex. 카운팅 배열이 현재 [2,0,1]이므로, 직전 요소들의 값을 더해주면, [2,2,3]([2,2+0,2+1])이 된다.)

 

4. 입력 배열과 동일한 크기의 출력배열을 만들고 입력 배열의 역순으로 요소들을 채워 넣어준다.

(ex.

원래 배열이 [2,4,2],

카운팅 배열이 [2,2,3],

출력 배열의 크기는 원래 배열과 동일한 3

카운팅 배열에 따라 2가 2개 4이 1개가 있으므로, 출력배열은 [2,2,4]

)

 

카운팅 배열 생성 및 누적

 

카운팅 배열에서 직전요소 더하기

출력 배열에 역순으로 원소 채워넣기, 출처: https://soobarkbar.tistory.com/101

---

◎계수 정렬의 구현

package SortAlgorithm;

public class sort {
	//계수 정렬
	private void countingsort(int[] numarr, int max, int min) {
		// 카운팅 배열 길이 = 원소들의 최댓값 - 원소들의 최소값 + 1
		final int counting_length = max - min +1; 
		int[] counting  = new int[counting_length];
		//출력 배열의 길이 = 입력 배열의 길이
		int[] output = new int[numarr.length];
		
		//카운팅 배열에 원소들의 출현 횟수 누적
		for(int i = 0; i<numarr.length; i++) {
			counting[numarr[i]-min]++;
		}
		//직전 요소들의 값 더해줌
		for(int i = 1; i<counting.length; i++) {
			counting[i] = counting[i] + counting[i -1];
		}
		//입력 배열의 역순으로 요소들을 출력배열에 채워 넣어준다
		for(int i = numarr.length-1; i>=0; i--) {
			/*
			 * counting 배열에서 1번 출현한 원소는 1로 표현되므로,
			 * output배열의 index로 사용할때 --연산자를 통해 미리 -1을 해준다.
			 * numarr[i]-min을 통해 counting 배열의 index 0에 있는 값이
			 * 원래 배열 최솟값의 출현횟수가 되도록 조정한다
			 */
			output[--counting[numarr[i]-min]] = numarr[i];
		}
		
		print(output, "계수 정렬");
	}

	// 출력
	private void print(int[] numarr, String sortname) {
		System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = { -1 ,5, 6, 3, 1, 4, 2 }; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));

		sort Sort = new sort();

		Sort.countingsort(numarr,6,-1);

	}
}

실행 결과:

원래 배열:[-1, 5, 6, 3, 1, 4, 2]
계수 정렬로 정렬된 배열:[-1, 1, 2, 3, 4, 5, 6]

---

◎계수 정렬의 시간복잡도 공간복잡도

계수 정렬의 시간복잡도는 O(n+k)(k는 최댓값 - 최솟값 +1)으로, 빅-오 표기법 상으로는 O(n)이고, 모든 비교 정렬(comparison sort)보다 빠른 정렬 방식이다. 하지만, 극단적으로 정렬해야할 배열이 [1억, 1]으로 정렬해야할 배열의 크기보다 수의 범위가 심히 클 때,  counting 배열의 길이 k=1억으로 카운팅 배열을 생성하고 직전요소를 더해 카운팅 배열을 완성하는 과정이 매우 오래 걸리고 공간효율성도 매우 떨어진다.

---

◎Sorting algorithm 시간 복잡도(time complexity) & 평균 정렬 속도(average sorting rate)

Sorting algorithm 시간복잡도(time complexity) & 평균 정렬 속도(average sorting rate) 출처:   https://st-lab.tistory.com/195

◆기수 정렬의 시간복잡도는 O(dn)이고, 계수정렬의 시간복잡도가 O(n+k)이다.◆

---

◎정렬 알고리즘 구현-github

github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/sorting_algorithm

jerry-ryu/java_problemsolving_algorithm