편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
{{위키데이터 속성 추적}} | {{위키데이터 속성 추적}} | ||
{{Infobox algorithm|class=[[정렬 알고리즘]]|data=[[배열]]|time=<math>O(n+k)</math>, where k is the range of the non-negative key values.|space=<math>O(n+k)</math>}} | {{Infobox algorithm|class=[[정렬 알고리즘]]|data=[[배열]]|time=<math>O(n+k)</math>, where k is the range of the non-negative key values.|space=<math>O(n+k)</math>}} | ||
'''계수 정렬''' 또는 '''카운팅 소트'''(counting sort)는 [[컴퓨터 과학]]에서 [[정렬 알고리즘]]의 하나로서, 작은 양의 [[정수]]들인 키에 따라 객체를 수집하는 것, 즉 [[정수 정렬]] 알고리즘의 하나이다. 구별되는 키 값들을 소유하는 객체의 수를 계수하고 출력 시퀀스에 각 키 값의 위치를 결정하기 위한 해당 계수에 전위합을 적용함으로써 동작한다. 실행 시간은 항목의 수, 그리고 최대 키 값과 최소 키 값의 차이에 선형적이므로 키의 다양성이 항목의 수보다 상당히 크지 않은 상황에서 직접 사용하는 데에만 적절하다. 더 큰 키들을 더 효율적으로 처리할 수 있는 다른 정렬 알고리즘인 [[기수 정렬]]의 서브루틴에 종종 사용된다.<ref name="clrs">{{인용 | '''계수 정렬''' 또는 '''카운팅 소트'''(counting sort)는 [[컴퓨터 과학]]에서 [[정렬 알고리즘]]의 하나로서, 작은 양의 [[정수]]들인 키에 따라 객체를 수집하는 것, 즉 [[정수 정렬]] 알고리즘의 하나이다. 구별되는 키 값들을 소유하는 객체의 수를 계수하고 출력 시퀀스에 각 키 값의 위치를 결정하기 위한 해당 계수에 전위합을 적용함으로써 동작한다. 실행 시간은 항목의 수, 그리고 최대 키 값과 최소 키 값의 차이에 선형적이므로 키의 다양성이 항목의 수보다 상당히 크지 않은 상황에서 직접 사용하는 데에만 적절하다. 더 큰 키들을 더 효율적으로 처리할 수 있는 다른 정렬 알고리즘인 [[기수 정렬]]의 서브루틴에 종종 사용된다.<ref name="clrs">{{인용 | ||
| last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen | | last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen |