📈알고리즘/알고리즘
병합 정렬[분할 정복 알고리즘 + 재귀 정렬]
하얀성
2023. 3. 15. 13:43
병합 정렬 기본 슈도 코드(분할 정복 알고리즘 + 재귀 정렬)
MergeSort(A,p,q)
입력: A[p]~A[q]
출력: 정렬된 A[p]~A[q]
if( p < q) { // 배열의 원소의 수가 2개 이상이면
k = ⌊ (p+q)/2 ⌋ // k=반으로 나누기 위한 중간 원소의 인덱스
MergeSort(A,p,k) // 앞부분 순환 호출
MergeSort(A,k+1,q) // 뒷부분 순환 호출
A[p]~A[k]와 A[k+1]~a[q]를 합병한다.
}
입력 크기 n =8인 배열A에 대한 병합정렬(분할 정복 알고리즘 + 재귀 알고리즘) 수행과정(슈도 코드)
처음에 왜 가장 작은 배열에서 if조건이 성립되지 않으면 저절로 합병되지 않는가 이해하기가 힘들었다.
저렇게 { }와 들여쓰기로 정리를 통해 천천히 그려보니 이해가 되었다.
그리고 k는 임시적인 중간 값일 뿐이다.
합병될 때에 자동적으로 순서가 바르게 정렬되는데 이게 분할해서 정복한다는 의미라 할 수 있다.
js로 병합정렬 구현하기
난 js가 언어중에서 가장 마음에 든다. 이유는 모르겠는데 그렇다. 그래서 추가적으로 알고리즘들이 어떻게 js로 표현 가능한지 궁금했다. 아래 출처에서 코드를 읽으며 코드를 분석해 보았다.
출처: https://www.youtube.com/watch?v=wXZyuJqNk9U
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
function mergeSort(arr) {
if(arr.length < 2) {
return arr
}
const mid = Math.floor(arr.length / 2)
const leftArr = arr.slice(0, mid)
const rightArr = arr.slice(mid)
return merge(mergeSort(leftArr), mergeSort(rightArr))
}
function merge(leftArr, rightArr){ // 합병을 위한 함수
const sortedArr = []
while(leftArr.length && rightArr.length) { // 둘다 1일 경우. 1이 되어야 더 재귀되지 않고 합병시작.
if(leftArr[0] <= rightArr[0]) { // 왼쪽이 작으면
sortedArr.push(leftArr.shift()) // 왼쪽 맨앞에서 빼서 새 배열에 넣기
} else { // 오른쪽이 작으면
sortedArr.push(rightArr.shift()) // 오른쪽 맨앞에서 빼서 새 배열에 넣기
}
}
return [...sortedArr, ...leftArr,...rightArr] // 새로 정렬된 배열, 왼쪽 한개남은 배열, 오른쪽 한개남은 배열
}
const arr = [8, 20, -2, 4, -6]
console.log(mergeSort(arr))
|
cs |
