계수정렬 자바스크립트

계수 정렬(Counting Sort) 이란

계수 정렬 특정한 조건이 부합할 때, 배열 원소 간 비교하지 않고 정렬하는 알고리즘이다. 특정한 조건이란, 원소들이 정수이며 0~K(K=정수)의 범위 안에 포함될 때를 가정한다. 즉, 데이터 개수가 N개이며, 모두 0이상의 정수이며 데이터 중 최댓값이 K일 때 사용할 수 있다. 계수 정렬은, 각각 데이터가 몇 번 씩 등장했는지를 세는 방식이다. 그래서 가장 큰 데이터의 크기로 배열을 선언해서 0부터 K까지 모든 범위를 포함할 수 있어야 하며, 배열 인덱스를 이용하기 때문에 0이상의 정수를 데이터로 갖는 배열을 가정해준다. 계수 정렬을 수행하는 순서를 살펴보자. 1. 인덱스 K를 참조할 수 있는 K+1 크기의 배열 countArr을 선언하고 모든 인덱스의 값을 0으로 초기화한다. 2. 원본 배열의 첫번째 ..