병합정렬
-
알고리즘 (정렬) - 고급 정렬 알고리즘(Merge Sort)1CS지식/알고리즘 2024. 1. 2. 11:27
고급 정렬 알고리즘 선택정렬, 버블정렬, 삽입정렬 과 같은 기본 알고리즘은 모두 평균 ϴ(n²)의 시간이 소요된다. 하지만 앞으로 게시물에서 다룰 고급 정렬 알고리즘은 모두 평균 ϴ(n log n)의 시간이 소요된다. 병합 정렬, 퀵 정렬, 힙 정렬을 소개하는데 회악의 경우에도 병합 정령과 힙정렬은 ϴ(nlogn)이 소요되고, 퀵 정렬 ϴ(n²)이 소요된다. 이 중 퀵 정렬은 최악의 경우 때문에 성능이 가장 나빠 보일 수도 있으나 평균 성능은 어떤 정렬에도 뒤 떠러지지 않아 실무에서 가장 많이 사용된다. 병합 정렬(Merge Sort) 병합 정렬은 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다...