[ALGORITHMS]문제 10 병합정렬

문제 10

병합 정렬

리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 정렬 알고리즘을 만들어보세요

재귀호출을 사용해서 정렬 문제를 더 빠르게 풀어보도록 하겠습니다.

1. 병합 정렬로 줄세우기

1. 학생들에게 일일이 지시하는 것이 귀찮아진 선생님은 학생들이 알아서 줄을 설 수 있는 방법이 없을지 고민입니다. 열명이나 되는 학생들에게 동시에 알아서 줄을 서라고 하면 너무 소란스러울 것 같아서, 다섯 명씩 두조로 나누어 그안에서 키 순서로 줄을 서라고 시켰습니다.

2. 이제 선생님 앞에는 키 순서대로 정렬된 두 줄(중간 결과 줄)이 있습니다.

3. 선생님은 각 줄의 맨 앞에 있는 두 학생 중에 키가 더 작은 민수를 뽑아 최종 결과 줄에 세웁니다. 그리고 다시 각 중간 결과 줄의 맨 앞에 있는 두학 생을 비교해 더 작은 학생을 최종 결과 줄의 민수 뒤에 세웁니다

4. 이 과정을 반복하다가 중간 결과 줄 하나가 사라지면 나머지 중간 결과 줄에 있는 사람을 전부 최종 결과 줄에 세웁니다.

2. 쉽게 설명한 병합 정렬 알고리즘

* 종료조건

*재귀 호출로 병합 정렬하는 부분

3. 병합 정렬에서의 재귀 호출

 병합 정렬의 입력 리스트에 자료가 한 개 뿐이거나 아예 자료가 없을때는 정렬 할 필요가 없으므로 입력 리스트를 그대로 돌려주면서 재귀 호출을 끝내면 됩니다.

4. 일반적인 병합 정렬 알고리즘

5. 알고리즘 분석

병합 정렬은 주어진 문제를 절반으로 나눈 다음 각각을 재귀 호출로 풀어가는 방식입니다. 이처럼 큰 문제를 작은 문제로 나눠서 푸는 방법을 알고리즘 설계 기법에서는 분할 정복이라고 부릅니다. 분할 정복을 잘 활용하면 계산 복잡도가 더 낮은 효율적인 알고리즘을 만드는데 도움이 됩니다.

분학정복을 이용한 병합정렬의 계산복잡도는 O(nlogn)으로 선택 정렬이나 삽입정렬의 계산 복잡도 O(n^2)보다 낮습니다. 따라서 정렬해야 할 자료의 개수가 많을수록 병합 정렬이 선택 정렬이나 삽입 정렬보다 훨씬 더 빠른 정렬 성능을 발휘합니다.

*연습문제

10-1 프로그램 10-2에서 다룬 정렬 알고리즘은 숫자를 작은 수에서 큰 수 순서로 나열하는 오름차순 정렬이었습니다. 오름차순 정렬을 큰 수에서 작은 수 순서로 나열하는 내림 차순 정렬로 바꾸려면 프로그램의 어느 부분을 바꿔야 할까요?

답 : 대소비교 부분

읽어주셔서 감사합니다