퀵 정렬 개념 . 2

퀵 정렬
표준 라이브러리를 이용하는 경우에는 기본적으로 NlogN 을 항상 보장한다

 

 

 

 

퀵 정렬 동작 예시

 

 

 

 

아주 중요!!! :  위치가 엇갈릴 때는 '피벗'과 '작은 데이터'의 위치를 서로 변경한다.

 

 

 

 

퀵 정렬의 시간 복잡도 

 

 

 

 

퀵 정렬은 이미 정렬된 배열에서 최악의 시간 복잡도를 가진다

(우측에서부터 0보다 작은 데이터가 없기 때문이다)

그래서 결국 위치가 엇갈려서 0이 자기 자신과 위치를 바꾸는 상황이 된다

그리고 0과 나머지 숫자들의 묶음으로 분할이 된다

그 후 계속 가장 작은 수와 나머지 숫자들의 묶음으로 분할이 되서 시간 복잡도가 O(N^^2) 이다.