-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCounting Sort.html
More file actions
37 lines (34 loc) · 1.39 KB
/
Counting Sort.html
File metadata and controls
37 lines (34 loc) · 1.39 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
// 계수정렬 O(N) - 크기를 기준으로 개수를 세면 어떨까? (정렬할 데이터들이 특정 범위 안에 있는 경우, 즉 '범위조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘)
// 위치를 바꿀 필요가 없고, O(N * log N)인 퀵 정렬, 병합 정렬, 힙 정렬보다 빠릅니다.
let temp;
let count = [];
// 범위 1 ~ 5인 배열
let array = [1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
3, 1, 4, 3, 5, 1, 2, 1, 1, 1]
for(let i = 0; i < 5; i++) {
count.push(0); // 0,0,0,0,0 -> 실제로는, 1,2,3,4,5가 카운트된 값이 들어갈 자리
}
for(let i = 0; i < 30; i++) {
// 실제로 1인 값은 인덱스 0번지에 카운트돼야 하므로, -1
count[array[i] - 1]++;
}
for(let i = 1; i <= 5; i++) {
// count 배열 작은 숫자(인덱스)부터 출력
if(count[i - 1] != 0) {
for(let j = 0; j < count[i - 1]; j++) console.log(i);
}
}
</script>
</body>
</html>