8강. 퀵 정렬 (Quick Sort)

[ 목차 ]

1. 퀵 정렬

2. 파티션

3. 퀵 정렬의 Pseudo code

4. 퀵 정렬의 수행시간

5. 정렬 알고리즘 수행시간 비교

 

1. 퀵 정렬

1) Divide-and-Conquer paradigm을 사용, 풀기 힘든 큰 문제를 쉬운 여러 개의 작은 문제로 만드는 것

2) partition을 사용해서 Divide-and-Conquer paradigm를 수행

 

2. 파티션

1) Pivot이라는 기준을 정해 이보다 크거나 작은 집단으로 분리

2) 작은 값들은 앞, 큰 값들은 뒤로 이동

3) 모든 값들을 이동 후 Pivot과 뒤의 큰 값 중 가장 앞선 값과 교체

 

3. 퀵 정렬의 Pseudo code

1) A : 배열

2) p : 첫 번째 인덱스 값

3) q : Pivot

 

4. 퀵 정렬의 수행시간

1) Partition에 걸리는 시간

2) Partition의 횟수

  1] Balanced partitioning

    - 각 하위 문제의 크기가 기존 문제 크기의 절반 정도인 [n/2]과 [n/2]-1가 되도록 나누어지는 경우

  2] Unbalanced partitioning

3) 최악의 수행시간

  1] 

  2] 대체법을 사용해 확인

  3] c(2n-1)를 만족하는 아주 큰 c를 선택, 따라서 T(n) = O(n제곱)

 

4) 평균적인 경우의 수행시간

  1] X : 퀵 정렬로 n개의 입력을 정렬하는 동안 비교하는 횟수

  2] 퀵 정렬의 평균 수행시간 : O(n + E[X])

  3] 각각의 파티션에서 비교횟수를 분석하는 것은 어렵기에 전체 수행시간의 상한값을 구함

  4] k = j-i 라고 하면 다음 식은 하모닉 시리즈를 이용해 풀 수 있음

 

5) 무작위 퀵 정렬

  1] 최악의 경우를 피하기 위해 배열에서 Pivot을 무작위로 선택

  2] 무작위 퀵 정렬의 Pseudo Code

 

5. 정렬 알고리즘 수행시간 비교