-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMerge Sort.html
More file actions
71 lines (61 loc) · 2.64 KB
/
Merge Sort.html
File metadata and controls
71 lines (61 loc) · 2.64 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
<!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 * logN) - 일단 반으로 나누고 나중에 합쳐서 정렬하면 어떨까?
// 퀵 정렬과 다르게 항상 정확하게 반절씩 나눈다는 점에서 최악의 경우에도 O(N * logN)을 보장합니다. (피벗 값 X)
// 병합하기 전 배열들이 이미 정렬이 돼있기 때문에, 그 순간 정렬 자체의 필요 수행 시간은 N
// 기존의 데이터를 담을 추가적인 배열 공간이 필요합니다 - 메모리 활용이 비효율적
let array = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9];
let number = 10;
let sorted = []
function merge(a, m, middle, n) {
let i = m; // 분할된 첫 번째 배열 시작 인덱스
let j = middle + 1; // 분할된 두 번째 ~
let k = m; // 임시로 넣을 배열의 인덱스도 마찬가지로 m부터 시작합니다
while (i <= middle && j <= n) { // i는 middle 전까지, j는 끝 인덱스인 n 전까지
if (a[i] <= a[j]) { // 더 작은 걸 삽입
sorted[k] = a[i];
i++;
} else {
sorted[k] = a[j];
j++;
}
k++; // 한번 넣고 나면 다음 반복 수행
}
if (i > middle) { // i가 먼저 넣는 작업이 끝났다면
for (let t = j; t <= n; t++) { // 남은 j들을 넣음
sorted[k] = a[t];
k++;
}
} else {
for (let t = i; t <= middle; t++) {
sorted[k] = a[t];
k++;
}
}
for (let t = m; t <= n; t++) { // 임시적으로 정렬된 데이터들을 넣기 위해 만든 sorted 배열을 원래의 배열인 a 배열에 삽입
a[t] = sorted[t];
}
}
function mergeSort(a, m, n) {
if (m < n) { // 크기가 1인 경우 제외
let middle = parseInt((m + n) / 2);
mergeSort(a, m, middle); // 분할 먼저 수행 후,
mergeSort(a, middle + 1, n);
merge(a, m, middle, n); // 그 후에 합칩니다.
}
}
mergeSort(array, 0, number - 1);
for (i = 0; i < 10; i++) {
console.log(array[i]);
}
</script>
</body>
</html>