카운팅정렬(CountingSort)

• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘

• 제한사항
  - 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능 : 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다.
  - 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.

• 시간복잡도 (n+k) : n은 리스트 길이, k는 정수의 최대값

구현코드

package array1;
import java.util.Arrays;

public class CountingSort {
	public static void main(String[] args) {
			int arr[] = {0,4,1,3,1,2,4,1};
			int m = Arrays.stream(arr).max().getAsInt(); //배열에서 최댓값을 찾아낸다.
			
			System.out.println("m="+m);
			
			int[] c= new int[m+1];
			int[] s= new int[arr.length];
		
			for (int i = 0; i < arr.length; i++)c[arr[i]]++;
			for (int i = 1; i < c.length; i++)c[i] += c[i-1];
			for (int i = 0; i < arr.length; i++) {
				c[arr[i]]--;
				s[c[arr[i]]] = arr[i];
			}
			System.out.println(Arrays.toString(arr));
			System.out.println(Arrays.toString(s));
	}

}