quick sort (1) 썸네일형 리스트형 32. Quick Sort 병합 정렬은 Θ(n lg n)의 시간복잡도를 갖지만 메모리 사용량이 너무 많다는 문제가 있다. 이러한 문제가 발생하지 않으면서 병합 정렬과 같은 평균 시간복잡도를 갖는 정렬 방법으로 퀵 정렬(Quick Sort)이 있다. 퀵 정렬은 한 원소의 위치를 고정하고 앞뒤 원소들을 같은 방법으로 정렬하는 분할 정복 기법의 일종이며, 평균적인 상황에서 최고의 성능을 보이지만 최악의 시간복잡도는 O(n2)라는 문제점이 존재하며, 동일한 값이 여러 개 존재하는 경우 정렬 과정에서 상대적인 순서가 바뀔 수 있다. 퀵 정렬의 과정을 요약하면 다음과 같다. 1. 피벗을 고른다. 2. 피벗보다 뒤에 나와야 하는 첫 번째 원소 ai를 찾는다. 3. 피벗보다 앞에 나와야 하는 마지.. 이전 1 다음
