[알고리즘] Merge sort 코드 및 풀이

 

KEY WORD

 

1. Merge sort: 합병 정렬

2. Divide: 분할

3. Conquer: 정복

4. recurrence: 재귀 (=> 순환 호출의 의미)

- 주어진 문제를 해결하기 위하여 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식.

- 어떤 루틴이나 프러시저가 자기 자신을 반복적으로 호출하여 문제를 풀어 나가는 알고리즘으로, 이를 이용하기 위해서는 스택을 사용한다. 

- 간단한 루틴을 풀 수 있지만, 처리 속도가 느리고 횟수가 지나치게 많으면 프로그램이 정지하기도 한다. (출처: 네이버사전_우리말샘)

5. subarray: 부분 배열

6. Pseudocode: 의사 코드

- 프로그래밍 언어에 무관하게 간략하게 표현한 코드, 참고하여 코드 작성

 

---

 

Merge Sort 란? 
 

▶ Divide and Conquer방법 중 하나

- 배열을 2개의 조각으로 나눈 후 각각을 정렬하고 그 조각들을 다시 모아 원래 배열을 정렬시키는 방법

- 대개 순환 호출을 이용하여 구현

 

출처: https://www.101computing.net/merge-sort-algorithm/

 

< Step >

Step 1 Divide

→ 입력 배열을 비슷한 크기의 2개의 부분 배열로 분할한다

(ex. 배열 8개 -> 4개 4개 / 배열 9개-> 5개 4개)

 

Step 2 Conquer

→ 부분 배열을 정렬한다.

 

Step3 Combine

→ 정렬된 부분 배열들을 하나의 배열로 합병

 

※ 순환 호출을 통해 부분 배열의 크기가 충분히 작아지도록 계속해서 쪼개고, 정렬하고,

     합병하는 방법을 반복하여 원래 배열이 모두 정렬되도록 함

※ 배열의 길이가 0 또는 1이면 이미 정렬된 것으로 판단

 

---

Pseudocode

 

Pseudocode를 같이 첨부하니 전체 코드를 보기 전 참고하여 직접 코드를 짜보는 것을 추천!

( cf. 이 의사 코드에서는 배열의 인덱스가 1에서부터시작,

C언어와 같이 배열의 인덱스가 0부터 시작하는 언어를 이용할 때 주의 필요 )

 

 

< Divide and Conquer >

 

< Combine > - Recurrunce

 

---

 

Code

 

< main 함수 > - 배열 설정 및 출력

 

< merge 함수 > - Divide and Conquer

 

< merge_sort 함수 > - Combine/ Recurrunce

- 함수 내에서 함수를 호출함으로써 재귀적으로 합병 정렬을 하게 됨

: 함수 내에서 함수 호출 (순환 호출) → 배열이 반복적으로 쪼개지면서 계속 작은 단위로 분할 → 작은 단위에서 정렬 → 정렬된 작은 조각들이 합병 → 최종적으로 원래 배열 하나가 전체 정렬이 됨

 

Result

 

 

---

수업 자료를 토대로 작성한 것이니 혹시라도copy는 자제부탁드립니다.

 

이해가 안가는 부분은 부담없이 댓글 남겨 주시고

도움이 되셨다면 공감 부탁드립니다 :)