위 그림을 보면 좀 더 쉽게 이해할 수 있을 것 같다.
퀵 정렬은 Pivot 이라는 선정된 기준값에서 작으면 왼쪽으로 모으고, 크면 오른쪽으로 모아서 Pivot을 기준으로 정렬을 시키는 방법이다. 그래서 1회 작업이 끝나면, Pivot의 위치는 고정이 된다.
그래서 퀵 정렬의 시간 / 공간 복잡도는 아래와 같다.
선정된 기준값인 Pivot에 따라서 시간복잡도가 결정된다. 선정된 Pivot의 값이 최소이거나 최대이면, 전체를 돌아야하기 때문에 최악의 상황이 될 수 있다.
이를 해결하기 위해서 Pivot 값을 랜덤으로 잡거나, 인덱스가 0번째 값와 중간값, 그리고 마지막 인덱스 값을 뽑고 3개 값을 우선적으로 정렬한 뒤, 그 중 중간 값을 가장 좌측 또는 우측으로 이동시켜 진행하는 방법이 있다.
자바스크립트로 짠 Quick Sort 코드는 아래 URL에서 확인 할 수 있다.
GitHub : Quick Sort
- Quick Sort 공부 자료
초보개발자