Quick Sort1 퀵 정렬(Quick sort) 퀵정렬 시간복잡도 공간복잡도 모든 값을 비교해야하므로 N 반복을 거듭할 때마다 반씩 줄어듦으로 log N O(N log N) 배열을 병합할 때 병합 결과를 담아놓을 배열이 필요함 O(N) 일반적으로 pivot이라고 부르는 임의의 기준값을 정하고 pivot보다 큰 값, 작은 값을 정렬하는 알고리즘. 분할 정복과 재귀용법을 사용. [6, 3, 1, 4, 5, 2, 7] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 먼저 기준이 될 pivot을 결정한다. 간단하게 첫번째 요소를 pivot으로 결정해보자. ☝퀵정렬은 어떤 값이 pivot으로 설정되냐에 따라 성능이 큰 영향을 받는다. 최악의 경우 시간 복잡도가 O(N²)이 될 수도 있다. 그래서 보통 pivot 값은 배열의 첫 값, 중간 값, 마지막 값 중.. 2022. 7. 14. 이전 1 다음