목록시간복잡도 (1)

홍카나의 공부방

[자료구조] 머지 소트(Merge Sort, 합병 정렬)

합병 정렬은 분할 정복(devide & conquer) 방법에 속하는 정렬 알고리즘이다. 문제를 쪼개서, 작게 나누고, 해결하는 방법이다. 어느 컴퓨터공학과든 자료 구조 시간에 이 머지 소트는 무조건 배우고 간다고 생각할 정도로 기본적인 알고리즘이라고 본다. 머지소트는 다음의 단계를 거친다.1. 정렬되지 않은 리스트를 원소를 1개 가지는 N 개의 서브리스트로 나눈다. (N = 리스트의 길이). 나눌 때는 절반씩 쪼개게 된다.2. 서브 리스트를 합치면서 정렬을 하고, 원소를 N개 가지는 1개의 리스트까지 합병한다.   합병 과정에서 어떻게 정렬하는지 살펴보면, 아래와 같이 합병 과정 중인 2개의 서브리스트가 있을 때 로직은 다음과 같다.  1. i와 J가 기리키는 숫자의 대소관계를 비교하고, 작은 숫자를 ..
Data Structure + Algorithm 2024. 8. 5. 13:54
이전 Prev 1 Next 다음