신비한 개발사전

퀵 정렬은 파티션(partition)이라는 알고리즘을 사용해 배열을 정렬한다. Big-O 표기법으로는 많은 정렬 알고리즘과 동일하게 n²이지만, 평균적으로는 n * log(n) 정도의 시간복잡도를 가진다고 한다. 파티션파티션 알고리즘에서는 말 그대로 배열을 부배열(subarray)이라는 파티션으로 나눈다. 이때 피벗(pivot)이라는 임의로 고른 원소의 좌우로 부배열이 나눠지게 된다. 좌측 부배열은 피벗보다 작거나 같은 값으로 이루어진 배열이고, 우측 부배열은 피벗보다 크거나 같은 값만 있는 배열이다. 파티션을 나누기 위해 먼저 전체 배열의 마지막 원소를 피벗으로 삼는다. 그런 다음 배열의 첫번째 인덱스부터 차례대로 피벗의 값과 비교하면서 정렬해나가는데, 이미 정렬된 부배열과 정렬해야 되는 부배열을 구분..