Quick Sort

Quick Sort는

최악의 경우 n^2

평균 nlgn

퀵 정렬의 내부 루프는 컴퓨터 아키텍쳐에서 효율적으로 작동되도록 설계되어 있다.

(메모리 참조가 지역화되어 있기 때문에 CPU캐시의 히트율이 높다.)

핵심만 정리하자면

pivot의 왼쪽엔 pivot보다 작은값

pivot의 오른쪽엔 큰값

do

if arr[i] > pivot && arr[j] < pivot // i와 j는 알아서 증가한다고 가정

swap arr[i++], arr[j--]

while(i <= j)

if(left < j) quickSort(arr, left, j)

if(right > i) quickSort(arr, i, right)