공부/자료 구조 및 알고리즘
2019. 8. 4.
자료의 정렬 - 합병 정렬(Merge sorting)
합병 정렬(Merge sorting) 서로 다른 두 집합을 하나로 합치는 정렬 방식. 전체 원소를 하나의 단위로 분할한 뒤 다시 병합(merge)하면서 정렬된다. 합병정렬(Merge sorting)의 방법 ① 모든 그룹의 자료를 2개의 그룹으로 분할한다. ② 그룹 내의 자료가 1이 될 때까지 계속 분할한다. ③ 분할이 끝나면 두 그룹에서 가장 앞에 있는 자료의 크기를 비교해 작은 자료부터 먼저 정렬한다. ④ 두 그룹의 자료들이 크기 순으로 정렬될 때까지 반복하여 하나의 그룹으로 만든다. ⑤ 다시 남은 그룹에 대해 같은 방법을 수행한다. ⑥ 하나의 그룹으로 만들어지면 정렬이 완료된다. 합병정렬(Merge sorting)의 예시 1. 3, 7, 2, 5, 1, 4를 합병정렬을 이용하여 배열해보자. 그룹 내의..