계수 정렬

(CS) 계수 정렬 & 기수 정렬

계수 정렬(Counting Sort)과 기수 정렬(Radix Sort)은 비교 정렬이 아닌 정렬 알고리즘으로, 특정한 상황에서 매우 효과적인 알고리즘이다. 각 정렬 알고리즘에 대해 자세하게 알아보자. 계수 정렬 계수 정렬은 범위에 해당하는 각 숫자의 빈도수를 계산하고, 빈도수의 누적값을 사용하여 데이터의 위치를 결정하여 정렬하는 알고리즘이다. 정렬할 데이터의 범위를 알고 있을 때 매우 효과적인 정렬 알고리즘이다. 비교 정렬이 아니기에 특정 상황에서 매우 빠르지만, 정렬할 데이터의 범위만큼의 추가적인 메모리가 필요하다. 정렬 과정 데이터들의 최솟값과 최댓값을 확인하여 전체 범위를 파악한다. 범위에 해당하는 각 숫자의 빈도수를 세어 배열에 저장한다. 각 숫자의 빈도수를 누적하여 해당 숫자의 정렬된 위치를 계..

계수 정렬

계수 정렬이란? 카운팅 정렬 (Counting Sort)이라고 부르기도 하는 계수정렬은 O(n)의 시간복잡도를 가지는 정렬이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다. 계수 정렬의 특징 주어진 데이터의 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다. 0과 양수 범위의 데이터들만 정렬할 수 있다. 데이터의 범위가 커지게 되면 소요되는 시간이 커지게 되고, 메모리가 낭비되는 문제가 발생한다. 또한 음수 범위의 데이터들은 정렬할 수 없다는 단점을 가진다. 계수 정렬의 과정 정렬되지 않은 수들을 count 배열에 몇 번씩 등장하는지 적어둔다. count 배열을 앞에서부터 순회하며 등장 횟수를 누적합으로 변경한다. 기존의 배열의 뒤에서부터 누적합 결과를 인덱스로 사..