counting sort1 [JAVA] 계수정렬(Counting Sort) 개념과 코드 구현 계수정렬(Counting Sort)은 정수 정렬 알고리즘의 하나로 각 숫자(키)가 몇번 등장했는지 계수(카운팅)해서 각 키값의 위치를 정하는 알고리즘이다. 배열의 값의 범위가 제한되어있을때 효율으로 작동하지만, 입력값의 범위가 크면 카운트 배열이 커지므로 메모리 문제가 생길 수 있다. 구분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 계수정렬 O(n + k) O(n + k) O(n + k) O(n + k) Y * n: 정렬할 배열 길이, k: 정수의 범위 알고리즘 1. 입력 배열의 최댓값과 최솟값을 구한다. 2. 최솟값부터 최댓값까지의 범위를 가지는 배열을 만든다. (카운트 배열) 3. 배열의 각 요소들이 몇번 등장하는지를 카운트 배열에 저장한다. 4. 카운트 배열의 누적합.. 2023. 4. 17. 이전 1 다음
