반응형
개념
- 각 데이터의 갯수를 세어 정렬하는 알고리즘
- 위치를 변경할 필요없고 각 데이터에 한 번씩만 접근하기 떄문에 효율적
- 데이터의 크기 범위가 한정되어 있는 경우에만 사용할 수 있다.
static final int NUMBER = 5;
static int[] count = new int[NUMBER];
static int[] array = {
1, 2, 3, 2, 1, 3 ,5, 4, 3, 5,
2, 3, 5, 4, 2, 3, 1, 2, 3, 2,
1, 1, 2, 3, 4, 1, 5, 5, 4, 3
};
static void countingSort(int[] arr) {
//배열 초기화
for (int i = 0; i < count.length; i++) {
count[i] = 0;
}
//각 숫자별 갯수 설정
for (int i = 0; i < arr.length; i++) {
count[array[i]-1]++;
}
for (int i = 0; i < count.length; i++) {
if(count[i] != 0) {
for (int j = 0; j < count[i]; j++) {
System.out.printf(i+1+" ");
}
}
}
}
※ 시간복잡도 O(N)
반응형
'Algorithm > 기본' 카테고리의 다른 글
너비 우선 탐색(Breadth First Search, BFS) (0) | 2021.05.08 |
---|---|
힙 정렬(heap sort) (0) | 2021.05.06 |
병합 정렬(merge sort) (0) | 2021.04.29 |
퀵 정렬(quick sort) (0) | 2021.04.28 |
삽입 정렬(insertion sort) (0) | 2021.04.26 |