컴퓨터알고리즘#9
LeeMir, 07 April 2021
합병정렬
분할통치법
- 분할
- 입력 데이터 L을 둘 이상의 분리된 부분집합 L1, L2, …으로 나눔
- 재귀
- L1, L2, … 각각에 대한 부문제를 재귀적으로 해결
- 통치
- 부문제들에 대한 해결을 합쳐 L을 해결
- 재귀의 베이스 케이스 : 상수 크기의 부문제들
- 점화식을 사용하여 분석
합병 정렬
- 분할통치법에 기초한 정렬 알고리즘
- 비교에 기초한 정렬, O(n log n) 시간에 수행
- 외부의 우선순위 큐를 사용하지 않음
- 데이터를 순차적 방식으로 접근
- 따라서 디스크의 데이터를 정렬하기에 적당
- 분할
- 무순리스트 L을 각각 n/2개의 원소를 가진 두 개의 부리스트 L1과 L2로 분할
- 재귀
- L과 L2를 각각 재귀적으로 정렬
- 통치
- L1과 L2를 단일 순서리스트로 합병
- 각각 n/2개의 원소를 가지며, 이중연결리스트로 구현된 두 개의 정렬 리스트를 합병하는데 O(n) 시간 소요