퀵 정렬

퀵정렬을 실제 문제푸는데 가장 많이 사용되는 정렬 알고리즘이다.

대부분 언어에서 정렬 라이브러리는 퀵 정렬이다.

"기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?"

 

기준을 설정한 다음 큰 수와 작은 수를 교환한 이후 리스트를 반으로 나누는 방식으로 동작한다.

 

Pivot이라는 개념이 등장 (Pivot = 기준)

기준을 어떻게 설정할 것인가?

가장 대표적인 분할 방식으로 호어 분할 방식이 있다.

"리스트에서 첫 번째 데이터를 Pivot으로 정한다"

퀵 정렬의 시간 복잡도는 O(NlogN) (선택 정렬, 삽입 정렬에 비해 빠른 편이다.)

(최악의 경우에는 시간 복잡도가 O(N^2) 이다.)

 

- 데이터가 무작위로 입력되는 경우는 퀵 정렬은 빠르게 동작한다.

- 데이터가 정렬되어 있을 경우에는 느리게 동작한다.