제가 알고 있기로 정렬 알고리즘의 복잡도는 nlogn 이하로 나올 수 없다고 알고 있습니다.
다름이 아니라 궁금한건 퀵정렬과 힙정렬의 복잡도는 각각 nlogn이고 최악의 경우 퀵정렬은 n^2, 힙정렬은 nlogn으로 알고 있습니다.
최악의 상황까지 고려했을 때는 힙정렬이 훨씬 좋아보이는데 실제 돌려보면 퀵정렬이 퍼포먼스가 더 좋게 나옵니다.
왜 퀵정렬이 더 빠른지 궁금하고 덧붙여서 퀵정렬과 힙정렬의 차이점에 대해 자세히 알고 싶습니다.
----------------------------------------------
퀵정렬은 배열구조를 그대로 이용할 수 있는 특징이 있습니다.
알고리즘에 상관없이 계산에 필요한 데이터를 다루는 과정은 반드시 필요합니다.
퀵정렬이 배열구조를 그대로 쓸 수 있다는 것은 데이터를 다루는데에서 퍼포먼스가 줄어들지 않는다는 뜻입니다.
힙정렬이나 합병정렬은 알고리즘의 특성상 배열보다는 리스트에 어울리기 때문에, 보통의 Imperative Language에서는 데이터를 다루는데 시간이 많이 걸립니다.
Functional Language라면 힙정렬이나 합병정렬이 더 좋을 수 있습니다.
-----------------------------------------------
우선 time complexity가 O(n)이니까요.
Quick 정렬이 평균성능이 더 잘 나오는 이유는 몇가지가 있습니다만 가장 큰 이유는 cache hit율로 알고 있습니다.
자세한 사항은 Wikipedia에서...
----------------------------------------------------
예를 들어서, 10개의 원소로 구성된 트리에 원소가 90개 추가되기도 하고, 다시 50개가 빠지기도 할 수 있다고 가정해볼까요?
힙정렬을 쓰는 경우는 대부분 이렇게 자료양이 가변적인 경우가 많습니다.
극단적으로 퍼포먼스를 끌어올린 형태로 완전이진트리를 배열로 만들고 이를 바탕으로 힙소트를 구현하면, 자료양에 따라 배열 재할당이 일어나게되어서 못써먹습니다.
이를 위해서 따로 배열 재할당이 일어나지 않거나, 적은 양만 일어나도록 수정할 필요가 있습니다.
현재 할당 메모리의 2배씩 공간을 늘여서 재할당하는 것이 쉽게 생각할 수 있고 대표적인 방법인데, 이 방법은 메모리 낭비도 심할 뿐더러, 자료양이 많다고 가정하면 오랜 복사과정을 필요로 하기때문에 무리가 있습니다.
그렇다면 리스트를 만들어서 여기에 담는 방법이 있는데, 노드를 위한 메모리 할당과 해제가 자주 일어나서 결국 퍼포먼스를 다 잡아먹게 됩니다.
그래서, 위의 두 장점을 고려해서 배열의 리스트를 만들어서 구현하는 방법을 쓸 수 있습니다.
배열을 기본으로하는 언어에서는 어쨌든 로직이 복잡해지고, 메모리 재할당에 대한 문제로 인해 힙소트는 퍼포먼스가 줄어들 수 밖에 없습니다.
하지만, 만약 리스트가 기본인 언어라면 메모리 재할당에 대한 고민이 필요없으며, 이런 과정이 자연스럽게 이루지므로, 로직상에서 발생하는 퍼포먼스 저하는 거의 없습니다.
물론 리스트라는 구조가 실제머신에서 쓰는 구조가 아닌만큼, 가상머신에서의 발생하는 퍼포먼스 저하는 어쩔 수 없지요.
기본적인 자료구조가 무엇이냐는 것은 생각보다 중요할 수 있습니다.
-------------------------------------------------------
Heap은 완전 정렬은 아니며, 적당히 정렬된 상태를 만드는 방식입니다. 완전이항트리(Complete Binary Tree)이기 때문에
C array 처럼 일차원으로 펼쳐놓고, index 만으로 부모 자식 관계를 찾을 수 있어서 동적할당을 통해 노드를 할당하는
트리구현보다 훨씬 성능이 좋습니다. Heap은 최대원소를 찾기 편하고 (O(1)입니다), 최대원소를 제거한 후 깨진 Heap 구조를 재조정하는데
O(log n) 연산으로 가능합니다. 또한 최초에 Heap을 만드는데 걸리는 연산은 O(n)이면 가능합니다.
그리고 이런 모든 연산에 추가적으로 요구되는 공간복잡도는 O(1)이므로 공간제약요소도 받지 않습니다.
이런 특성으로 Heap을 통해 매우 효율적인 정렬 algorithm 제작이 가능합니다.
하지만 정렬에 사용되는 기본연산인 비교와 대입이 원소 수에 따라 거의 일정하기 때문에 초기 원소들의 배치상황에 따라 더 짧은 시간 내에
정렬이 끝나는 특성은 얻지 못합니다. 또한 최대원소 제거 후 Heap 구조를 재조정하는 연산이 배열을 전체적으로 다 훑고 지나가므로
참조지역성의 특성을 활용한 cache의 성능가속을 얻기가 어렵습니다.
이런 이유로 Heapsort는 Quicksort에게 정렬의 대명사를 내주었으며, 대신 Heap은 우선순위큐를 만드는데 많이 활용됩니다.
우선순위큐는 최대원소를 빼내면서 원소를 중간마다 추가할 수 있어야 한다는 요구사항을 반영한 자료구조이므로 Heap이 아주 적당하죠.
'컴퓨터 공학' 카테고리의 다른 글
| [공유] 완벽주의의 4가지 폐해 - 완벽을 고집하지 마라 (0) | 2015.11.27 |
|---|---|
| 사운드 라이브러리, FMOD (0) | 2015.11.27 |
| [퍼옴] vi 단축키 (0) | 2015.11.27 |
| 윈도 95에서부터 존재해 온 '19년 된 윈도우 버그' 해결...MS (0) | 2015.11.27 |
| MS, 닷넷 서버 스택 오픈소스로 공개…비주얼 스튜디오 커뮤니티 2013도 무료 (0) | 2015.11.27 |