자료구조_정렬 ④ 퀵 정렬

 

 

[1] 퀵 정렬

---

(1) 퀵 정렬 개념

quick 정렬

가장 빠른 정렬 방법

분할 정복 정렬 방식 

데이터 리스트 중 중간에 위치한 값을 피벗이라한다 

피벗은 알고리즘에 따라 첫 값, 마지막 값, 중위수 값을 선택할수 있다 

피벗 기준으로 왼쪽에서는 피벗보다 큰 값을 , 오른쪽에서는 피벗보다 작은 값을 찾아 교환하는 작업을 반복하여 정렬한다 

 

(2) 퀵 정렬 과정 

 

(3) 시간복잡도 O(nlogn) 

최악이면 O(N⌒2) 가 나올수 있다