[알고리즘] 퀵 정렬 | Quick Sort | C++코드 해석

병합정렬(Merge Sort)과 함께 기본 정렬알고리즘인 퀵정렬.

병합정렬이 수열을 반으로 쪼개가며 정렬했다면,

퀵정렬은 기준을 두고 기준보다 작은값들, 기준보다 큰값들로 쪼개가며 정렬한다.

 

병합정렬은 따로 정렬해둔 값을 저장해둘 메모리공간이 필요했다면

퀵정렬은 따로 메모리공간이 필요하지 않다.

 

하지만 병합정렬은 언제나 시간복잡도가 일정한 반면

퀵정렬은 잡히는 기준에 따라 시간복잡도가 O(n^2)까지 올라갈수있다고한다. 

 

코드는 이러하다.

pivot이 기준 값이 되고

i가 pivot의 자리를 찾아준 다고 생각하면된다.

이해하기 쉽게 예시를들어 그림으로 설명해보자면 이런식이다.