오늘은 정렬 알고리즘 중에 퀵 정렬과 힙 정렬에 대해 이야기해보려고 하는데요, 각각 알고리즘의 코드 구현보다는 인터넷을 돌아다니며 알게 된 재미있는 이야기?? 또는 사람들이 이야기??를 공유해보려 합니다.

제가 알고리즘에 대해 이해가 깊지 않아서 글에 잘못된 부분이 있을 수 있습니다. 혹시 잘못된 부분을 보신다면 댓글로 알려주시길 부탁드립니다 :)

참고.
1. https://brunch.co.kr/@k2u4yt/3
2. https://kldp.org/node/110384
3. https://v8.dev/blog/array-sort

1. 크롬(v8)에서 사용하는 정렬 알고리즘

자바스크립트에는 sort라는 내장 함수가 있는데요. 별생각 없이 자주 사용하던 함수인데, 문득 sort 함수는 어떤 알고리즘을 썼을까? 궁금증이 생겨서 알아봤는데요. ‘참고 1’ 글에서 아주 친절하고 자세히 설명이 되어 있었답니다. 대략 요약하자면,
우선 크롬을 기준으로 과거(약 2008년)에는 v8은 힙 정렬을 사용하였고 근래(약 2015년)에는 퀵 정렬로 변경되었답니다. 그리고 위 ‘참고 1’ 글에서는 힙 정렬이 퀵 정렬에 비해 최악의 경우의 시간 복잡도가 더 좋지만 많은 양의 데이터를 정렬할 경우 힙 정렬은 반복적인 *heapify 연산이 많은 자원을 사용하기 때문에 그로 인해 성능이 퀵 정렬에 비해 안 좋게 되고 그 부분이 v8이 정렬 알고리즘을 변경하게 된 하나의 이유가 아닐까 하는 이야기입니다.

*heapify : 힙 정렬은 정렬을 수행하면서 매번 가장 큰 값 또는 가장 작은 값을 루트 노드로 하는 힙 트리를 만드는 과정을 하는데 그 힙 트리를 만드는 과정을 말합니다.

그런데 ‘참고 1’글이 작성 시기가 2017년 이어서 지금은 또 바뀌지 않았을까? 하는 생각으로 깃헙 v8 리포지토리를 둘러보니 지금은 팀 정렬로 변경되었네요. 간단하게 팀 정렬은 합병 정렬과 삽입 정렬이 합쳐진 하이브리 형태의 정렬인데요. 이전에 합병 정렬과 퀵 정렬은 코드로 구현한 글을 썼었는데요. 조만간 힙 정렬이나 팀 정렬도 작성해 봐야겠어요.

v8 깃허브 리포지토리 : https://github.com/v8/v8

‘참고 3’ 글을 참고해보면, 퀵 정렬은 큰 배열을 정렬할 때 샘플을 위한 작은 스택 공간(log n)만을 사용하고 in-place(제자리 정렬?) 현재 메모리에서 정렬한다는 장점이 있고, 단점으로는 안정적인 알고리즘이 아니고 최악의 경우 n²의 시각 복잡도를 가진다는 점(적은 확률이지만)을 이야기합니다.

팀 정렬에 대한 이야기는 우선 공부를 좀 한 후 다음 시간에…

2. 퀵 정렬과 힙 정렬의 장단점

그리고 다음으로 ‘참고 2’번의 글을 보면, 퀵 정렬과 힙 정렬에 비교에 대해 어느 분이 질문을 남겨주셨고 그곳에 많은 분들이 답변을 달아주셨는데 그 내용이 참 재미있었어요.

적당히 제가 인상 깊게 본 내용들만 줄여서 이야기를 해보자면, 우선 힙 정렬은 최초에 정렬되어 있지 않은 값을 앞서 이야기한 heapify 과정에 서 O(n)의 연산이 소요되지만 이후 연산에서는 O(logn)의 연산이 가능합니다. 그리고 아주 적은 가능성이지만(2/n!) O(n²)의 시간 복잡도를 가질 수 있는 퀵 정렬에 비해 최대 O(nlogn)의 시간 복잡도를 갖는 힙 정렬의 안정감이 장점이기도 합니다.

앞서 ‘참고 1’의 글에서 이야기했듯이 힙 정렬은 모수가 많을수록 swap 연산이 훨씬 더 많아지기 때문에 최악의 경우의 시간 복잡도의 차이와 달리 퀵 정렬이 더 좋은 성능이 나오는 경우가 많습니다.(그래서 이름도 퀵 정렬이겠죠.. ??)

하지만 지금도 힙 정렬은 많이 사용되고 있는데요.(사실 애초부터 절대적으로 더 좋은 정렬 알고리즘은 정의할 수 없지만) 가장 생각해보기 좋은 예가 힙 정렬이 퀵 정렬보다 성능이 안 나오는 이유가 반복적인 heapify와 그에 따른 swap 때문이라고 했지만, 반대로 그 특징 때문에 정렬 중간중간에 값이 추가되거나 빠질 때에는 힙 정렬이 퀵 정렬보다 더 좋은 성능을 낼 수 있답니다. 대표적으로 ‘우선순위 큐’에서 사용될 때에는 퀵 정렬보다 힙 정렬이 더 좋은 성능일 내겠죠?

저는 공부하며 재미있었던 부분인데 도움이 되는 글이었을지 모르겠네요ㅎ

끝