pivot + partitioning 의 recursive한 구조를 가지고 있다.

space complexity : O(1)

time complexity 는 worst, average, best

best 는 pivot값을 정확히 medium 값으로 잡았을 때 가능하다. O(nlogn)

worst는 이미 정렬 되었고, pivot값을 계속 최대값으로 잡는 경우다. O(n제곱)

average는 O(nlogn)

맨 끝 값을 항상 pivot값으로 정해놓고 간다면 이미 정렬된 배열이 들어왔을 때 항상

worst의 time complexity를 가지게 된다. 그렇기 때문에 랜덤하게 잡거나 배열의 중간위치 값을 pivot으로 잡고 간다.

9 5 2 3 7 8 4

임의로 pivot을 5로 지정했다.

pivot과 가장 오른쪽 값인 4와 자리를 바꾼다.

9 4 2 3 7 8 5

Left 는 9 Right 는 8 pivot은 5를 가리킨다.

Left는 pivot보다 작아야 하며, Right는 pivot보다 커야 할 것이다.

9는 pivot보다 크므로 가만히 있는다.

8은 크므로 Right가 한칸 왼쪽으로 간다. Right -1

Right는 7을 가리킨다.

9 4 2 3 7 8 5

또 pivot 보다 크니까 Right -1

이젠 3을 가리킨다.