알고리즘 5 [퀵정렬, quick sort]

5. 퀵정렬(quick sort)

By en:User:RolandH, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1965827

 

퀵 정렬 이란?
배열 중간의 피벗(pivot) 요소를 설정한 뒤, 데이터의 비교를 통해 좌 위에 배치하는 방법

---

e.g.) 오름차순 퀵 정렬

[ 5, 3, 8, 4, 9, 1, 6, 2, 7]의 배열이 있을때

1. 5를 피벗 요소로 선택 후 작은값과 큰값을 각각 좌우에 배치
   -> [3, 4, 1, 2, '5(pivot)', 9, 6, 8, 7]
2. 5의 좌측 리스트(부분 리스트)에서 3를 피벗으로 설정 후 같은 패턴
   -> [1, 2, 3(두번째 pivot), 4, 5(첫번째 pivot) ...]
3. 5의 우측 리스트(부분 리스트)도 실행
4. 부분 리스트의 크기가 0 또는 1이 될때까지 반복

---

[ 장점 ]

• 불필요한 데이터의 이동이 적고, 피벗 요소들이 다음 연산에서 제외됨
• 즉, 시간복잡도 면에서 알고리즘 중 제일 효율적임

[ 단점 ]

• 불안정한 정렬(unstable)
• 이미 정렬된 상태에서는 오히려 수행시간이 길어짐

시간 복잡도 : 최선의 경우 & 평균 - O(nlogn), 악의 경우 - O(n^2)
공간 복잡도 : O(n)