퀵 정렬 (Quicksort)

Dicide-and-Conquer qaradigm을 사용 즉 풀기 어려운 정렬을 계산하기 쉽게 나누어 진행하는것

partition을 이용

 

 

Pivot을 정해서 작은것은 왼쪽 큰것은 오른쪽으로 위치시킨다. 재귀호출을 통해 계속 반복한는것 

 

Pivot 보다 큰것은 왼쪽(회색) 작은것은 오른쪽(녹색)

p는 배열의 첫번째 r는 배열의 마지막

 

퀵 정렬의 수행시간은 Pivot을 어떨게 설정하냐에 따라 달라진다. 

 

Balanced partitioning 일때의 수행시간 nlogn

Unbalanced partitioning 일때의 수행시간 n^2

Merge sort 는 nlogn이지만 공간은 사용해야 한다는 단점이 있다. HeapSort는 max-heap구조를 만들어야 한다는 어려움이 있다. Quicksort는 nlogn이지만 최악의 경우 시간이 많이 늘어난다.