Algo. quick sort , merge sort 간단 정리

오늘 어쩌다 보니 sort에 대해 생각할 시간을 가지게 되었다. 갑작스럽게 생각을 하려니 또 잊어버린 부분이 많아서 다시 되새기는 김에 정리하려 한다.

먼저 merge sort부터 정리해 보겠다. 병합 정렬은 기본적으로 분할 정복 방식으로 정렬을 진행 한다. 코드의 진행을 먼저 간단히 말하면 재귀적으로 계속 반씩 쪼개나 가면서 길이가 1개일 때까지 내려간다.  그 뒤 다시 올라오면서 값들을 병합하는 단계를 거친다. 여기서 시간 복잡도를 결정하는 부분은 병합하는 부분인데 병합 단계에서 최대 n번만큼 비교할 수 있다. 또한 순환 호출할 때 깊이가 반씩 나누기 때문에 logn이다. 따라서 최종적으로 nlogn이 된다고 한다. 자세한 부분은 밑에 블로그를 참고 하자. 여기서 또 내가 생각해야 될 부분은 이 병합 정렬은 임시 배열이 필요한데 그래서 in place 정렬이 아니라고 볼 수 있다. 근데 여기서 연결 리스트로 구현하면 in-place 하게 구현 할 수 있다고 한다. 그리고 다른 특징으로 stable sort라는 점인데, 이건 정렬이 될 때 같은 키값을 가진 수들의  위치가 막 섞이면서 정렬되는 게 아니라 유지하면서 정렬된다는 것이다. 밑에서 말하지만 퀵소트는 이거랑 반대다. 아무튼 이런 임시 배열 옮기는 연산까지 다 합쳐서 O(nlogn)의 시간 복잡도를 갖는다.

다음은 퀵소트를 보자

퀵정렬은 위에서 말한 거처럼 unstable 한 정렬이다. 구현 방식은 병합 정렬처럼 분할 정복을 통해서 구현한다. 다만 병합 정렬과 다르게 균등하지 않게 구간을 나누게 된다. 또한 퀵 정렬은 이 비교를 하기 위해 피벗이라는 기준을 두는데, 여기서 피벗을 어떻게 두냐에 따라 정렬 속도가 달라진다. 그래서 상한이 O(nlogn) 이지만 최악의 경우에 n^2 이 될 수도 있다고 한다. 어떤 경우냐면 정렬이 다 돼있는 경우나 역순으로 정렬되어 있는 경우를 생각해 보자, 피벗을 맨 처음 수로 두면 모든 경우를 계속 다 보게 된다.  그니까 피벗을 잘 정해서 반으로 잘 나뉘면 nlogn 이 나오고 아니면 n^2까지 갈 수도 있다. 갑자기 이거 관련해서 생각났는데 정렬이 되어있는 배열에 대해 가장 빠른 방법은 삽입 정렬이라고 한다. 원소를 넣을때 마다 큰 숫자랑만 비교해서 O(n)만걸릴 수도 있다 근데 이건 특이한 경우고 보통 삽입 정렬은 n^2이다.

아무튼 그래서 구역을 잘 나누기 위해 퀵소트에서 partition을 나누는 방식에 대해 다양한 방법이 존재하는데, 일부러 오히려  랜덤으로 섞어서 다시 정렬하게 하는 방식도 있다고 한다.

 

생각난 김에 빠르게 정리해 봤는데 나중에 추가 더 해야겠다. 정말 기본적인 것들인데 막상 갑자기 떠올리려고 하면 버벅거리게 된다. 종종 찾아보면서 생각하는 시간을 가져야겠다.

 

출처 및 참고: 

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog