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번 째로 큰 혹은 작은 원소를 찾는다

알고리즘 순서

1. pivot의 index가 k이면 pivot를 return
2. pivot의 index가 k보다 작으면 pivot의 오른쪽만 다시 정렬
3. pivot의 index가 k보다 크며 pivot의 왼쪽만 다시 정렬

예시

위의 [5,4,3,2,1] 배열에서 3번 째로 큰 원소를 찾아보자.

피봇은 마지막 원소로 정한다.

• 1번째 iteration 결과 : [1,5,4,3,2]
  • 정렬 결과, 피봇의 위치가 첫 번 째 원소가 되는데 , 3번 째 큰 원소를 찾기 위해 피봇의 오른쪽 배열인 [5,4,3,2]를 다시 정렬해야 한다.
• 2번째 iteration 결과 : [1,2,5,4,3]
  • 정렬 결과, 피봇의 위치가 두 번 째 원소가 되는데 , 3번 째 큰 원소를 찾기 위해 피봇의 오른쪽 배열인 [4,3,2]를 다시 정렬해야 한다.
• 3번째 iteration 결과 : [1,2,3,5,4]
  • 정렬 결과 피봇의 위치가 3이 되므로, 3번 째 큰 원소를 찾았다.

시간 복잡도

최악의 경우, n+n-1+...n-k 이므로 O(N^2)이다.