[JS] 퀵 정렬

1. 퀵 정렬 "퀵"이라는 말 그대로 정말 정말 정말 빠른 정렬이다. 퀵 정렬은 특별한 경우를 제외하고는 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다. 따라서 퀵 정렬의 시간 복잡도는 $$ O(N\times log_2{N}) $$ 이다. 여태 포스팅했던 선택 정렬, 버블 정렬, 삽입 정렬의 시간 복잡도는 $$ O(N^2) $$ 이다. 고등학교 수학을 배운 사람이라면 $$ N^2 > N \times log_2{N} $$ 이 성립된다는 것을 알 수 있다. 하지만, 빅오 표기법에서 log₂N과 N²의 차이는 어느정도일까? 차이는 어마무시하다고 말할 수 있다. $$ N=2^{10} $$ 일 때를 예로 들어보자. 2를 10번 곱하면 1024이다. 하지만 컴퓨터에서는 1024라고 하지 않고 통상 1000이라고..

2020.06.01