[질문] 퀵 정렬과 힙 정렬의 비교에 관해 질문드립니다.
글쓴이: verejun / 작성시간: 목, 2009/11/19 - 1:26오후
제가 알고 있기로 정렬 알고리즘의 복잡도는 nlogn 이하로 나올 수 없다고 알고 있습니다.
다름이 아니라 궁금한건 퀵정렬과 힙정렬의 복잡도는 각각 nlogn이고 최악의 경우 퀵정렬은 n^2, 힙정렬은 nlogn으로 알고 있습니다.
최악의 상황까지 고려했을 때는 힙정렬이 훨씬 좋아보이는데 실제 돌려보면 퀵정렬이 퍼포먼스가 더 좋게 나옵니다.
왜 퀵정렬이 더 빠른지 궁금하고 덧붙여서 퀵정렬과 힙정렬의 차이점에 대해 자세히 알고 싶습니다.
Forums:
퀵정렬은 배열구조를
퀵정렬은 배열구조를 그대로 이용할 수 있는 특징이 있습니다.
알고리즘에 상관없이 계산에 필요한 데이터를 다루는 과정은 반드시 필요합니다.
퀵정렬이 배열구조를 그대로 쓸 수 있다는 것은 데이터를 다루는데에서 퍼포먼스가 줄어들지 않는다는 뜻입니다.
힙정렬이나 합병정렬은 알고리즘의 특성상 배열보다는 리스트에 어울리기 때문에, 보통의 Imperative Language에서는 데이터를 다루는데 시간이 많이 걸립니다.
Functional Language라면 힙정렬이나 합병정렬이 더 좋을 수 있습니다.
------------------------------
How many legs does a dog have?
------------------------------
How many legs does a dog have?
힙정렬은 처음 힙을
힙정렬은 처음 힙을 구성하는데 시간이 많이 걸리는것으로 알고있습니다..
힙이 일단 구성되면 큰 원소부터 하나씩 뽑아내는 작업은 매우 빠른것으로 알고있습니다..
그리고 힙정렬도 배열구조를 그대로 이용할 수 있습니다
WHAT'S UP
배열은 리스트를
배열은 리스트를 대신할 수 있고, 역으로 리스트는 배열을 대신할 수 있습니다.
중요한 것은 할 수 있느냐가 아니라, 어떤 게 더 타당한가죠.
힙의 특성은 동적이고, 힙정렬은 데이터의 위치(링크)를 변경하는 방식으로 동작합니다.
리스트는 동적이고, 자체적으로 데이터간의 링크를 제공합니다.
트리라는 구조는 배열로도 만들 수는 있지만, 의미적으로는 리스트에 더 가깝습니다.
------------------------------
How many legs does a dog have?
------------------------------
How many legs does a dog have?
Heap 만드는데 생각보다 시간 안 걸립니다.
우선 time complexity가 O(n)이니까요.
Quick 정렬이 평균성능이 더 잘 나오는 이유는 몇가지가 있습니다만 가장 큰 이유는 cache hit율로 알고 있습니다.
자세한 사항은 Wikipedia에서...
아.. heap 을
아.. heap 을 구성하는데 O(nlogn) 입니다..
모든 원소 각각에 대해 tree 의 특정 위치에 집어넣어야하니까요..
WHAT'S UP
O(n log n) 이라고 생각하기 쉽지만...
O(n) 입니다.
저도 helloneo님과 같은
저도 helloneo님과 같은 생각을 합니다.
용도를 조금 다르게 봐야 됩니다.
quick sort는 주어진 데이터를 '한 번' 빠르게 정렬할 때 유용합니다.
heap sort는 계속 데이터가 추가되거나 빠질 때, 그 순간마다 정렬된 상태를 유지할 수 있다는 장점을 가집니다.
heap도 실제는 배열로 구현할 수 있지만 개념적으로는 트리입니다.
리스트와 배열의 차이는 여기서 논외라는 생각이 드는군요.
예를 들어서, 10개의
예를 들어서, 10개의 원소로 구성된 트리에 원소가 90개 추가되기도 하고, 다시 50개가 빠지기도 할 수 있다고 가정해볼까요?
힙정렬을 쓰는 경우는 대부분 이렇게 자료양이 가변적인 경우가 많습니다.
극단적으로 퍼포먼스를 끌어올린 형태로 완전이진트리를 배열로 만들고 이를 바탕으로 힙소트를 구현하면, 자료양에 따라 배열 재할당이 일어나게되어서 못써먹습니다.
이를 위해서 따로 배열 재할당이 일어나지 않거나, 적은 양만 일어나도록 수정할 필요가 있습니다.
현재 할당 메모리의 2배씩 공간을 늘여서 재할당하는 것이 쉽게 생각할 수 있고 대표적인 방법인데, 이 방법은 메모리 낭비도 심할 뿐더러, 자료양이 많다고 가정하면 오랜 복사과정을 필요로 하기때문에 무리가 있습니다.
그렇다면 리스트를 만들어서 여기에 담는 방법이 있는데, 노드를 위한 메모리 할당과 해제가 자주 일어나서 결국 퍼포먼스를 다 잡아먹게 됩니다.
그래서, 위의 두 장점을 고려해서 배열의 리스트를 만들어서 구현하는 방법을 쓸 수 있습니다.
배열을 기본으로하는 언어에서는 어쨌든 로직이 복잡해지고, 메모리 재할당에 대한 문제로 인해 힙소트는 퍼포먼스가 줄어들 수 밖에 없습니다.
하지만, 만약 리스트가 기본인 언어라면 메모리 재할당에 대한 고민이 필요없으며, 이런 과정이 자연스럽게 이루지므로, 로직상에서 발생하는 퍼포먼스 저하는 거의 없습니다.
물론 리스트라는 구조가 실제머신에서 쓰는 구조가 아닌만큼, 가상머신에서의 발생하는 퍼포먼스 저하는 어쩔 수 없지요.
기본적인 자료구조가 무엇이냐는 것은 생각보다 중요할 수 있습니다.
------------------------------
How many legs does a dog have?
------------------------------
How many legs does a dog have?
솔직히 저도 이해하기 어려운 설명입니다만...
제가 보기에 helloneo님과 terzeron님은 Heap Tree와 Balanced Binary Search Tree 착각하시는 것 같은데요.
winner님께서
winner님께서 착각하시는 것 같습니다.
저는 '균형' 이진 '검색' 트리라고 말한 적이 없습니다.
heap은 그저 이진 트리(또는 배열)일 뿐이죠.
뭔가 심하게 이상한 말씀을 하시네요
힙소트는 배열로 자연스럽게 구현이 가능하고, 오히려 linked list에 힙소트를 적용하려면 훨씬 골치아파집니다.
그뿐만 아니라 힙소트는 in place로 구현 가능합니다. 이 얘기는 배열로 된 데이터가 있을 때 힙소트를 구현하기 위해서는 O(1)만큼의 메모리만 더 있으면 된다는 뜻입니다. 다른 곳으로 복사하고 말고 전혀 필요없습니다 (물론 그 배열 안에서는 뻔질나게 위치를 바꾸겠지만 그건 sort면 다 마찬가지니...)
오히려 quicksort의 경우 recursion 때문에 O(log N)만큼의 메모리가 더 필요합니다. (즉 in place 구현이 안된다는 뜻입니다.) 조심해서 안 짜고 대충 짜면 최악의 경우 O(N)의 메모리가 더 필요할 수도 있습니다. (자세한 것은 아무 알고리즘 책이나 보시면 나옵니다.)
확실히 배열이 coding하기 좋습니다만...
제가 한 것은 아니었지만 학교수업에서 Heap Sort를
책에서 개념적으로 배운대로 tree로 작성해보고, 그다음에 배열로 작성하더군요.
semmal님은 아마도 general list를 말씀하고 계시므로 보통 사람들이 tree라고 하는 놈을 말씀하고 계시는 걸겁니다.
힙소트 자체만으로
힙소트 자체만으로 보면 그렇습니다만
그런데 힙소트를 쓰는 상황이 원래 힙을 구성하고, 그 힙에 원소를 추가하거나 빼면서, 정렬을 계속 하려는 목적이죠.
힙 자체에 대한 연산을 위한 부분까지 고려를 해야한다는 말입니다.
그냥 별 생각없이 딱 한번 배열 구조에서 make_heap하고 sort_heap하는 것이 아니라, 힙을 관리하는 상황자체가 더 복잡하다는 말이죠.
또한, 글 중에 배열을 기본으로하는 언어에서 리스트를 쓰는 것이 더 좋지 않다고 분명히 언급했구요.
단지 리스트를 기본으로 하는 언어, 즉 Functional Language에서 힙정렬 구현이 Imperative Language보다 더 쉬울 수 있다는 사실에 대해 말한겁니다.
그리고, 퀵소트는 recursion없이 작성 가능하고, 이 경우에 추가적인 메모리를 필요로 하지도 않습니다. 인터넷 뒤져보시면 금방 나옵니다.
------------------------------
How many legs does a dog have?
------------------------------
How many legs does a dog have?
헉 Quick 정렬이 recursion 없이 되나요?
별로 하고 싶지는 않지만...
제품 code에서는 그렇게까지 해야 하나?... 으음...
성능을 중시했다는 STL도 그렇게는 안 하는데...
호어가 퀵정렬을
호어가 퀵정렬을 만들었을 때, 정렬이 엄청나게 빨리 동작하니까 신기하게 생각한 상사가 어떻게 만든 거냐고 물었답니다.
상사에게 열심히 코드를 설명을 해줬는데, 상사가 못알아 듣더라는 전설이 전해져옵니다. 그 사람도 전문가였을텐데 말이죠.
그리고, STL의 퀵정렬 소스를 확인해본 적은 없습니다만 구현이 다르다면, 이런 식으로 구현해버리면 generic하지 않기 때문이겠지요.
------------------------------
How many legs does a dog have?
------------------------------
How many legs does a dog have?
자꾸 이상한 정보를 유포하고 계신데...
힙소트를 쓰는 상황이란 게 "원래 힙을 구성하고 추가하거나 빼면서 정렬을 계속하려는" 상황에서 얼마나 자주 쓰이는지는 제가 그렇게 써본적이 없어서 잘 모르겠습니다만......
힙소트는 그런 거 다 필요없이 시작과 끝이 있는 1차원 배열 하나 덜렁 던져주고 "이거 소트해줘" 하는 상황에서도 아주 간편하게 써먹을 수 있습니다. 그리고 이때 "힙 자체에 대한 연산"을 (아마 힙 만드는 거 말씀하시는 것 같은데...) 포함해서 O(N log N) time, O(1) additional space 나옵니다.
그리고 퀵소트는 물론 명시적 recursion 없이 작성 가능하지만 이 경우 stack을 사용해야 하고, recursion level이 O(log N)이므로 스택의 크기도 O(log N)이 됩니다. 추가적인 메모리 없이 퀵소트를 하는 방법은 제가 알기로는 없는데 인터넷 뒤져보시면 금방 나온다니 하나만 찝어주시면 좋겠습니다.
heapsort를 배열의
heapsort를 배열의 리스트로 만들어서 구현하다는 이야기는 처음 듣는군요.
저는 고정 크기의 데이터셋에 대해서는 배열로 만드는 게 효율적이라고 생각하고
가변 크기의 데이터셋에 대해서는 이진 트리로 만드는 게 효율적이라고 생각합니다.
배열의 리스트로 힙을 만들어서 쓸 수도 있겠지만 그건 일반적으로 말하는 heap 구조는 아니죠.
질문이 어렵군요. ㅎㅎ
둘다 n log n 꼴이지만,
Quick sort가 n^2이 나올려면
하위로 내려가면서 잡는 pivot이 항상 제일작은수 or 제일큰수 이어야 합니다.
이 확률은 2/n! 입니다.
sort해야할 리스트(리스트든 어레이든)가 이렇게 되지 않도록 적당히 pivot만 잡아주면
quick sort가 n^2가 될 확률은 굉장히 낫다고 먼저 말씀드리고 싶습니다.
Heap Sort를 쓰는 이유는 "최악의 경우에도" n log n 이 유지되는 측면이 아닐까 생각하는데요
평균적인 수준에서 Heap Sort는 Quick sort에 비해 20%(수치는 적당하게 기억이)정도 느리고
최악인 경우는 또 20%정도 느립니다.
quick sort의 최악의 경우를 대비하여 Heap sort를 쓰는 가장 큰 이유라고 저는 생각합니다.
그런데 검색이라는 것은 다양한 검색상황에 대해서 평균적인 속도를 보장해야 되는데
평균적으로 quick sort가 heap sort보다 20%가량 성능이 좋다면
최악의 상황은 "불가피한 상황"으로 치부해버릴 수 있는 조건이 된다고 생각합니다.
정말 자세한 내용을 아시려면 역시 Knuth의 TAOCP vol.3 이 최고의 서적이라 생각합니다.
문제는 O(n^2)
문제는 O(n^2) complexity가 보안 문제를 발생시킬 수도 있다는 것입니다. randomized quicksort가 아닌 이상 (이 쪽은 이제 RNG의 품질이 문제가 되겠죠) 모든 pivoting 방법에 대해 최악의 데이터셋은 항상 존재하기 때문에 이 문제를 알고리즘의 변경 없이 해결할 수는 없습니다.
잘 알지 못하지만 아는대로 말해보겠습니다.
우선 semmal님의 함수형 언어 이야기로 대화가 조금 꼬인 것 같습니다.
답글 다신 분들은 이 문제에 대해서 다들 잘 아시는 것 같은데 조금씩 다른 부분을 중요한 요소로 집어서 견해차가 있는 것 같네요.
저는 이 문제에 대해서 심도있게 공부해 본 적은 없습니다만 아는대로 최대한 간명하게 설명해보도록 하겠습니다.
우선 이 분야의 책을 여러 권 읽어보시기를 추천합니다.
또한 Wikipedia를 비롯 web surfing을 해보세요.
보통 대학교 내에서는 논문을 자유롭게 얻을 수 있기 때문에 재학중이시라면 논문을 참고하는 것도 매우 좋습니다.
제가 'Algorithm' 수업을 들을 때 교수님께서 Hoare의 Quicksort 논문을 찾아보라는 보너스 숙제를 내셔서
찾아보고는 생각보다 훨씬 심도있는 이야기로 놀랬던 기억이 있습니다.
저는 그냥 정렬함수 하나 제작했다라로 끝날 줄 알았는데 그렇지가 않더라고요.
원전을 찾아보는 것은 항상 좋은 것 같습니다. 그리고 관련 변형 algorithm에 대한 논문도 많이 있습니다.
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이 아주 적당하죠.
Quicksort와 Heapsort를 중심으로 만들어진 혼합정렬인 Introsort를 만든 저자들의 노트가 있습니다.
참고하시기 바랍니다.
http://www.osl.iu.edu/~kyross/pub/introsort-print.pdf
http://www.cs.rpi.edu/~musser/gp/algorithm-concepts/introsort-screen.pdf
또한 다음 자료는 위 노트보다 좀더 자세한 자료가 있습니다.
http://ralphunden.net/?q=a-guide-to-introsort
제 생각에는 Quicksort에도 단점이 있습니다만 결국 제품코드로 들어가는 것이 Quicksort 변형이라는 것과
재귀를 사용한다는 점이 학생들에게 재귀를 가르치는 좋은 예라는 것, 마지막으로 Heap이라는 다소 특이한 자료구조와
그 연산들을 이해하는 어려움이 Heapsort가 Quicksort에게 밀린 요인이 아닐까라는 그런 생각이 듭니다.
오
감사합니다!
우연한 검색으로
우연히 검색하다가 들어오게되었고 댓글들이 흥미로워서 다 읽었는데 너무 웃겨서 댓글 달아옄ㅋㅋ
원래 이런 프로그래머들이 많은 사이트에서는 댓글들을 이렇게 달아요??ㅋㅋㅋㅋ
->제가 우연히 web surfing하다가 in this site들어왔습니다. reply들이 웃겨서 re:달아봅니다. ㅋㅋ
원래 이런 programmer들이 mian guest인 사이트에서는 re:이런식으로 다나요? ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
뭔 외국대학다녀서 한국어로 잘 바꾸기 어려운 말이거나 그런것도 아니고 겨우 대학생이 무슨 논문을 찾아보았고 ㅋㅋㅋ아 개웃기넹
달아옄ㅋㅋ
세벌식에서는 쓰기 어려운 댓글이죠... 님께서 쓴 댓글도 웃기네요. :)
세벌 https://sebuls.blogspot.kr/
댓글 달기