20. 퀵(Quick) 정렬 알고리즘

1. 개요

 퀵 정렬은 속도는 같은 O(nlogn)이지만 모든 정렬중에서 일반적으로 가장 빠름.

 하지만 최악의 경우 속도는 O(n^2)에 수렴. (최악의 경우는 이미 정렬된 데이터면서 pivot으로 맨 우측을 선택할 때)

 병합 정렬과 마찬가지로 분할 정복의 좋은 예.

 하지만 재귀 전 작업을 하기 때문에 재귀 오버헤드가 큼.(아래 출력사진에서 확인) 

 병합 정렬은 높은 안정성으로 인해 데이터 크기 1억까지도 수행할 수 있지만 퀵 정렬은 현재 데이터 크기 10만에 터짐.

 두 번째 다른 점은 병합 정렬은 항상 1/2로 나누지만 퀵 정렬은 나누는 기준(pivot)이 다름.

 알고리즘 4단계

 (1) 배열을 2개로 나누는데 필요한 기준(pivot) 찾기.

 (2) pivot을 찾는 과정에서 정렬이 이뤄짐.

 (3) pivot으로 인해 나뉜 두 배열이 위의 (1)-(2) 과정을 반복함.

 세밀한 설명은 코드 주석으로 처리함.

2. 코드

2-1) 메인

2-2) 퀵 정렬 알고리즘

2-3) 출력

      *터진 이유: Stack Overflow 에러로 재귀 오버헤드가 쌓여서 발생

3. 해설

 병합 정렬보다 나은 장점

 (1) 평균적인 경우 병합 정렬보다 조금 더 빠를 수 있다.

 (2) 병합 정렬은 배열로 구성할 경우 임시 배열로인해 공간 복잡도가 O(n)이 필요.(리스트 기반일 경우 O(1))

 기억해야할 것

 (1) 인덱스의 범위는 정교해야한다. 인덱스 범위 한 치라도 틀릴 경우 알고리즘은 무너진다.

 (2) 결국 병합 정렬과 사촌과 같은 관계다.