MergeSort와 QuickSort

병합정렬과 퀵정렬 둘 다 시간복잡도는 nlogn으로 알려져 있다.

다만, 퀵정렬같은경우 최악의 경우 n^2이 되는 경우가 발생하지만 병합정렬은 항시 nlogn을 보장해준다.

 

물론 병합정렬은 추가적인 메모리공간을 소비한다는 단점이 있긴 하다.(배열기반의 정렬이라면)

대신 링크드리스트같은 컨테이너의 정렬이라면 추가적인 메모리공간마저 소비하지 않기 때문에 굉장히 효율적이다.

병합정렬이란거 자체가, 쪼갠다음 다시 조합하는건데 배열기반의 경우 조합하기위해서 새로운 공간에다가 조합하는거고

링크드리스트는 각각의 노드가 독립적이기 때문에(주소만 안잃어버린다면) 값 비교후 포인터만 머리와 꼬리에 연결해주면 되기 때문이다. 

 

그리고 퀵정렬은 불안정한 정렬에 속한다. 정렬을 했을 때 중복된 값이 처음의 배열과 불일치하는 경우를 말한다.

단순히 숫자만 정렬하는 경우라면 상관없겠지만, 나중에 구조체나 클래스를 정렬할 때, 특정값을 기준으로 정렬을 하되 나머지 순서는 동일하게 유지하고 싶다면 불안정한 정렬을 하는것은 피해야 할 것이다.

병합정렬은 다행히 안정정렬에 속한다.

 

퀵정렬은 최악의 경우 n^2라는 시간복잡도임에도 불구하고 굉장히 좋은 성능을 지녔다.

그 이유로는 n^2이 되는 경우의 확률은 상당히 적으며, pivot값을 어떻게 선정하느냐에 따라 회피할 수 있기 때문이다.

그리고 하드웨어적으로 퀵정렬은 병합정렬보다 상대적으로 효율이 더 좋다.

 

하드웨어적?

CS공부를 하다보면 반드시 접하게될 '참조지역성(locality of reference)'이라는 키워드가 등장한다.

참조지역성은 크게 3가지로 나뉜다.

 

1. 시간지역성 : 최근 사용된 페이지를 다시 참조할 확률이 높다.

2. 공간지역성 : 최근 사용된 페이지의 '근처 페이지'들이 다시 참조될 확률이 높다.

3. 순차지역성 : 데이터가 순차적으로 접근되는 경향으로, 프로그램 명령어가 순차적으로 구성되어 있는 경우이다.

 

즉, 다시 참조할 확률이 높은 페이지를 메모리뿐만 아니라 캐쉬에도 적재하게 되는데, 위의 참조지역성의 원리에 따라

Hit율이 높다면 캐쉬에서 바로 페이지를 접근할 수 있기 때문에 속도가 훨씬 빠르게 된다.

 

그러면 아래의 퀵정렬과 병합정렬의 로직수행애니메이션을 봐보자.

 

 

https://imgur.com/gallery/omL5k

 

https://imgur.com/gallery/omL5k

 

 

위의 애니메이션을 보면 병합정렬같은 경우는 끝과 끝을 왔다갔다하면서 데이터를 탐색한다.

병합하는 과정에서 쪼개진 두 리스트의 값을 비교해야하기 때문이다.

또한 이후에는 새로운 배열에 합쳐야 하기 때문에 데이터들을 복사해야해서 시간이 좀 더 걸린다.

 

그러나 퀵정렬 같은 경우는 넓지 않은 범위내에서 좌우로 왔다갔다하면서 정렬하기 때문에 캐쉬의 Hit가 상대적으로 병합정렬에비해 더 높다.(캐쉬에 있는 페이지를 자주 바꿀필요가 없다는 말.)

 

심지어 여기에 더해서, 퀵정렬에는 Tail Recursive Elimination 도 적용이 된다..!

Tail Recursive Elimination이 어떤것인지는 아래를 참고..

https://maxlevel-trace.tistory.com/314

Tail Call Optimization, Tail Recursive Elimination

 

어쨌든 결국 퀵정렬에도 Tail Recursive Elimination이 적용된다는 것이다.

퀵정렬 또한 함수 종료직전에 별다른 연산없이 온전한 자기자신을 호출하기 때문이다.

 

이러한 여러 최적화들이 퀵정렬에 유리하다보니 퀵정렬은 굉장히 빠른 정렬기법으로 평가받고 있다.