CountingSort
-
[알고리즘] 카운팅 정렬(Counting Sort)Study/자료구조,알고리즘 2022. 10. 21. 12:28
1. 특징 원소간 비교를 수행하지 않는 정렬이다. 모든 원소는 양의 정수여야 함 시간 복잡도는 O(n+k), k는 정렬할 배열의 최대값이다. 공간 복잡도는 O(n+k), 정렬을 위한 배열 하나, 카운팅을 위한 배열 하나가 필요하다. 2. 과정 입력 자료 input을 탐색하여 최대값 k를 구한다. k + 1 사이즈의 배열 counts를 생성한다. input을 순회하며, 등장하는 수의 빈도를 기록한다.. (input의 원소가 3이라면, counts[3]에 +1) 0이 1번, 2가 5번 등장하는 배열이라면, counts배열은 [1, 0, 0, 5]가 될 것 input을 순회하며 누적합을 구한다. 오름차순 정렬의 경우, 이전 값 (i-1)을 i에 더한다. 내림차순 정렬의 경우, input의 뒤쪽부터 시작해서, ..