merged_sort
-
#합병정렬에 대해 알아보자. #merge_sort #정렬Data miner 2019. 7. 12. 13:19
합병 정렬은 배열을 절반씩 나누어 그 각각을 정렬한 다음에, 다시 합하는 방식이다. 합병정렬은 Divide, Conquer, Combine 알고리즘으로 설명할 수 있다. 핵심 아이디어는 다음과 같다. 인풋으로 받는 리스트를 좌, 우로 나뉜 뒤(Divide)에 왼쪽 리스트와 오른쪽 리스트를 각각 정렬한뒤(Conquer), 이 정렬된 리스트를 하나로 합병하는 단계(Combine)로 구성되어 있다. 이 때 각각의 리스트는 정렬되어 있는 상태이다. 최종 합쳐진 리스트가 정렬되기 위해서는 각각 리스트 값의 첫번째 값들을 비교하여 하나로 합쳐야 한다. 정복(Conquer)부분이란, 부분 집합을 정렬해야 하는 단계이다. 부분 배열의 크기가 기준치 이하를 만족해야 한다. 그 크기는 0,1에 해당한다. 이 크기를 만족시..