자료구조_알고리즘/Algorithm
[Algorithm/Java] 카운팅 정렬 (Counting sort)
카운팅 정렬 (Counting sort) 카운팅 정렬은 정렬 시 데이터들의 개수를 세어 카운팅 배열에 저장하고 이후에 하나씩 꺼내오는 방식으로 정렬한다. 특정 조건이 부합할 때만 사용할 수 있지만, 데이터 수가 많더라도 중복된 값이 많이 분포되어 있는 배열을 정렬할 때 효과적이고 빠른 정렬 알고리즘이다. 시간복잡도는 O(N + k)이다. k는 컬렉션(카운팅배열) 내부의 최대 숫자이다. 따라서 최대값이 너무 큰 경우에는 시간복잡도가 매우 커질 수 있다. 카운팅 정렬의 조건 1. 데이터가 양의 정수인 경우 카운팅 정렬은 기본적으로 0~최댓값의 인덱스를 가지는 배열에 데이터 등장 횟수를 카운팅 하는 방식이다. 따라서 양의 정수만 가능하다. 2. 데이터의 크기 범위가 제한 된 경우 위에서 언급했듯이, 최대값이 ..
