퀵 정렬 (Quick Sort)

: 기준 데이터 (pivot)을 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬 방법

: 일반적으로 첫 번째 데이터를 pivot으로 설정함

: 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나

: 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘

-> (일반적으로 표준 정렬 라이브러리 제공 시, 최악의 경우에도 시간복잡도 nlog₂n을 보장할 수 있는 형태로 구현됨)

: 재귀적으로 수행되며, 정렬이 수행될 때마다 정렬 범위가 점점 좁아짐

: 이상적인 경우 분할이 절반에 가깝게 일어남 -> 빠른 속도

: pivot 값 설정에 따라 분할이 한 쪽 방향으로 편향된 분할을 가지는 경우, 최악의 시간 복잡도 = n^2

퀵 정렬의 과정

1. 배열의 원소들 중, 하나의 값을 pivot값으로 정한다.

2. pivot값을 기준으로, pivot 앞에는 pivot보다 작은 값이 오고 pivot 뒤에는 pivot보다 큰 값들이 오도록 배열을 나눔

3. 나눠진 두 배열에 대하여 재귀적으로 1~2의 과정 반복