합병정렬1

• 

  210628 합병 정렬(merge sort) & 퀵 정렬(quick sort) 합병 정렬(merge sort) : 안정적, 분할 정복 알고리즘(문제를 작은 문제로 분리하고 각각 해결하여 합쳐서 문제를 해결하는 방법) 중 하나 리스트의 길이 0 또는 1이면 정렬된 것으로 취급, 아닌 경우는 비슷한 크기로 잘라 두 개의 리스트로 만듬 각 부분 리스트 재귀적으로 합병 정렬을 통해 정렬함 두 부분 리스트 합병 반복함 단: 만약 배열로 구성한다면 임시 배열 필요 , 제자리 정렬 아님 데이터의 크기가 큰 경우에는 이동 횟수가 많아 매우 비효율적 장 : 안정적인 정렬 방법, 데이터의 분포에 영향 덜 받음, 입력 데이터에 영향 덜 받음 레코드를 연결 리스트로 구성하면, 링크 인덱스만 바꾸면 되기에 데이터의 이동은 무시할 수 있을 정도로 작아짐, 제자리정렬로 구현 가능 큰 데이터 다를 때 연결 리.. 미가공 필기(알고리즘) 2021. 6. 28.