퀵정렬 (2) 썸네일형 리스트형 <알고리즘> 퀵정렬은 병합정렬보다 항상 좋은 선택인가 1. 소개 최근에 필자는 하스켈이라는 언어를 공부하고 있다. 함수형 프로그래밍에 대한 깊은 이해를 위해서 겉핥기를 하고 있는데, 최근 정렬과 관련하여 궁금한 점이 생겨서 이렇게 정리하게 되었다. 참고로 이 포스팅에서 하스켈에 대해 깊이 알 필요는 없으며 함수형 언어라고만 생각해도 이해하는 데에는 지장이 없다. Data.List는 리스트 정렬을 위한 sort 함수를 제공한다. 이 함수는 퀵정렬을 쓰지 않는다. 대신 병합 정렬이라는 알고리즘의 효율적인 구현을 사용한다. - WikibooksHaskell - 지금까지 공부하기로는 대부분의 언어에서 정렬 함수는 퀵정렬(Quick Sort)을 활용하고 있다고 배웠다. 심지어 같은 시간복잡도를 가지는 병합정렬에 비해 일반적으로 더 빠르며, 면접 준비에서도 그렇게 대.. <알고리즘> 퀵 소트 & 힙 소트 1. 퀵 소트와 힙 소트 * 퀵 소트 - 퀵 소트(Quick Sort)는 병합 정렬(Merge Sort)와 마찬가지로 분할 정복 알고리즘을 활용한다. 그러나 병합 정렬과 달리 배열을 비균등하게 분할하여 정렬을 수행한다. - 퀵 소트는 불안정 정렬에 속한다. - 퀵 소트는 어떤 과정으로 정렬을 하는 것일까. 오름차순 정렬을 한다고 가정하자. 먼저 배열 내의 요소를 하나 선택한다. 이는 기준이 되는 원소로 피벗(pivot)이라 칭한다. 피벗을 기준으로 피벗보다 작은 원소는 피벗의 왼쪽으로 옮겨지고, 큰 원소는 피벗의 오른쪽으로 옮긴다. - 위의 과정을 한 번 거친 후, 피벗을 제외하고 왼쪽 배열과 오른쪽 배열에 대해 각각 같은방식으로 정렬한다. 부분 배열이 더 이상 분리가 불가능할 때까지 반복한다. 그러면 .. 이전 1 다음
