quick sort
def quick_sort(a, left, right):
pl = left
pr = right
x = a[(left+right)//2]
while pl <= pr: # pl과 pr이 같을때도 한번 더 이동시키기 위해 등호 포함
while a[pl] < x: pl += 1 # 바꾸기도 전에 피벗 넘어가지 않게 등호 미포함
while a[pr] > x: pr -= 1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1 # 같을 때에도 한번 더 돌려 결국 pl은 pr보다 커진다.
if left < pr: quick_sort(a, left, pr)
if right > pl: quick_sort(a, pl, right)- pivot과 같은 값을 가지는 경우에도 위치변경이 이루어지기에 항상 안정하지 못하다.
- 시간복잡도와 공간복잡도상 유리하기에 많이 사용된다.
pivot을 지정하는 것의 차이로 시간복잡도의 큰 차이가 발생한다.
그래도 평균적으로 n log n 이라는 빠른 속도를 비교적 적은 공간복잡도로 제공한다.
