728x90 합병정렬1 c언어 - 병합 정렬(Merge Sort) 이전 글에서 퀵 정렬에 대해 포스팅 했다. 병합 정렬은 퀵 정렬과 매우 비슷하지만 조금 다른 정렬이다. 퀵 정렬은 피벗을 정해 정렬을 하는데 피벗을 선택하는데서 정렬의 성능이 정해진다. 병합 정렬은 배열의 크기를 반으로 쪼개 정렬해 정렬되는 속도가 일정하다. 시간 복잡도로 보면 최악 평균 최선 퀵 정렬 O(N^2) O(NlogN) O(NlogN) 병합 정렬 O(NlogN) O(NlogN) O(NlogN) 시간 복잡도를 보면 평균은 비슷 하지만 최악에서 차이가 난다. O(N^2)는 버블, 선택 정렬과 같아 느리다. 속도가 일정하다는 장점을 가지고 있다. 단점은 메모리가 필요하다. 병합과정에서 같은 사이즈의 다른 배열에 임시로 저장하기 때문이다. 이제 병합 정렬은 배열의 크기/2 의 값을 기준으로 좌, 우로.. 2021. 1. 1. 이전 1 다음 728x90
