sort (1) 썸네일형 리스트형 Algo. quick sort , merge sort 간단 정리 오늘 어쩌다 보니 sort에 대해 생각할 시간을 가지게 되었다. 갑작스럽게 생각을 하려니 또 잊어버린 부분이 많아서 다시 되새기는 김에 정리하려 한다. 먼저 merge sort부터 정리해 보겠다. 병합 정렬은 기본적으로 분할 정복 방식으로 정렬을 진행 한다. 코드의 진행을 먼저 간단히 말하면 재귀적으로 계속 반씩 쪼개나 가면서 길이가 1개일 때까지 내려간다. 그 뒤 다시 올라오면서 값들을 병합하는 단계를 거친다. 여기서 시간 복잡도를 결정하는 부분은 병합하는 부분인데 병합 단계에서 최대 n번만큼 비교할 수 있다. 또한 순환 호출할 때 깊이가 반씩 나누기 때문에 logn이다. 따라서 최종적으로 nlogn이 된다고 한다. 자세한 부분은 밑에 블로그를 참고 하자. 여기서 또 내가 생각해야 될 부분은 이 병합 .. 이전 1 다음