Quick sort,selection 정리(2)
Quick Sort 분할 정복 기법 예시 시간 복잡도가 최악의 경우가 될 때를 생각해본다. 주어진 배열 [5,4,3,2,1] 을 작은 순으로 정렬한다. pivot은 배열의 마지막 원소로 설정한다 1번째 iteration : 1의 왼쪽인 5,4,3,2를 1과 비교한다. 결과 ⇒ 1의 왼쪽에는 원소가 없게 되고 오른 쪽에는 [5,4,3,2] 가 된다. ⇒[1,5,4,3,2] 2번째 iteration : 2를 피봇으로 [5,4,3,2]를 정렬한다. 결과 ⇒ 2의 왼쪽에는 원소가 없게 되고, 오른 쪽에는 [5,4,3]이 된다. ⇒ [1,2,5,4,3] 이런 식을 반복하다 보면 [1,2,3,4,5]가 얻어지고, 시간 복잡도는 O(N^2)이 된다. Quick Selection 목표 배열 내에서 K번 째로 큰 혹은 ..
