2024 동계 모각코 5회차

2025/02/03

5회차 목표

1) Udemy 강의:
- 섹션 15: 합병 정렬

2) 실습:
- 강의의 문제 구현
- 프로그래머스 문제

---

TIL

1️⃣ 합병 정렬 (Merge Sort)

분할 정복 알고리즘에 기반한 정렬 방식으로, 데이터를 반으로 나누고 나눈 부분을 정렬한 뒤 다시병합하면서 정렬하는 방식

 

📌 작동 원리

1. 분할 - 배열을 더 이상 쪼갤 수 없을 때까지 반으로 나눈다.
2. 정복 - 나뉜 배열들을 개별적으로 정렬한다.
3. 병합 - 정렬된 부분 배열들을 하나로 합치면서 정렬한다.

 

📌 알고리즘 동작 과정

1. 배열을 더 이상 나눌 수 없을 때까지 반으로 분할한다.
2. 분할된 배열을 각각 정렬한다.
3. 각각의 정렬된 상태의 배열을 병합한다.
4. 최종적으로 모든 원소가 정렬된 단일 배열로 병합된다.

 

📌 구현 코드

function mergeSort(arr){
	if(arr.length <= 1) return arr;
	
	const mid  = Math.floor(arr.length/2);
	const left = arr.slice(0,mid); 
	const right = arr.slice(mid);
	
	return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
	const result = [];
	let i = 0;
	let j = 0;
	
	while(i<left.length && j<right.length){
		if(left[i]<right[j]){
			result.push(left[i]);
			i++;
		}else{
			result.push(right[j]);
			j++;
		}
	}
	return result.cocat(left.slice(i)).concat(right.slice(j)); 
}


// 실행 예제
let arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // [3, 9, 10, 27, 38, 43, 82]

 

📌 시간 복잡도

최악의 경우 (역순 정렬)	O(nlogn)
평균적인 경우	O(nlogn)
최선의 경우 (이미 정렬된 상태)	O(nlogn)

모두 O(nlogn)로 동일하다.

 

📌 공간 복잡도 O(n)

O(n)

 

📌 특징

• 데이터 크기가 커질수록 성능이 좋음
• 병합 과정에서 O(n)의 추가 메모리가 필요함

 

---

느낀 점

파이팅