Quick Sort1 Quick sort 퀵 정렬 - 주어진 배열을 피벗(pivot) 을 기준으로 작은 원소들은 왼쪽, 큰 원소들을 오른쪽으로 위치시킨다. - 이렇게 나뉜 두 개의 배열을 같은 반복을 반복하여 정렬한다. - 특정 기준을 바탕으로 배열을 나눈다는 점에서 병합정렬과는 차이가 있다. 또한, 병합 정렬의 경우 각 부분의 정렬이 끝난 후 병합 처리를 해줘야 하는 반면, 퀵 정렬은 추가적인 작업이 필요하지 않다. - 평균적으로 O(n log n)의 시간복잡도를 가진다. 과정 - Pivot을 배열의 가장 왼쪽으로 잡냐(Hoare-Partition) 혹은 오른쪽으로 잡냐(Lomuto-Partition) 에 따라 과정에 차이가 있을 수 있다. - Hoare-Partition을 기준으로 설명한다. - Pivot은 가장 왼쪽에 위치하며, 두 개의 .. 2021. 10. 9. 이전 1 다음
