[Algorithm] 정렬 ③

- Quick Sort : 빠른 정렬

=> Merge Sort처럼 분할 - 정복 - 합병의 분할정복법을 이용함.

Ex) 정렬할 배열이 주어졌을 때, 마지막 수를 기준(pivot)으로 삼음 -> 기준보다 작은 수는 기준의 왼쪽에 나머지는 기준의 오른쪽에 오도록 재배치(분할:partition)를 함. -> 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬함. => 정렬 완료

 

- 최악의 경우

항상 한 쪽은 0개, 다른 쪽은 n-1개로 분할되는 경우

이미 정렬된 입력 데이터 ( 마지막 원소를 기준으로 선택하는 경우 )

 

- 최선의 경우

항상 절반으로 분할 되는 경우

=> 분할이 얼마나 되어 있는지에 따라 Quick Sort는 영향을 받음.

 

- 평균시간복잡도

최악의 경우는 매우 극단적인 예이며 대체적인 경우가 존재

 

- 기준(Pivot)의 선택

첫 번째 값이나 마지막 값을 기준으로 선택 -> 이미 정렬된 데이터 혹 or 거꾸로 정렬된 데이터가 최악의 경우일 수 있음. 현실의 데이터는 랜덤하지 않으므로 (거꾸로) 정렬된 데이터가 입력으로 들어올 가능성은 매우 높음. 즉, 좋은 방법이라고 할 수 없음

첫번째 값, 가운데 값, 마지막 값 중에서 중간값을 기준으로 선택 -> 최악의 경우를 피할 수 있는 확률을 높이는 현실적인 방법임 하지만, 최악의 경우 시간복잡도가 달라지지는 않음.

기준을 랜덤하게 선택 -> 잘 선택된다면 최선의 경우일 수 있음