퀵 정렬

분할 정복 알고리즘

피벗이라는 기준점을 이용하여 파티션닝을 합니다.

파티셔닝

기준 점(피벗)을 잡아 배열의 첫번 째 값부터 비교하여 피벗보다 작은 값은 왼쪽 큰 값은 오른쪽으로 이동 시킵니다.

Pseudo code

QUICKSORT(A,p,r)
if p < r
	q = PARTITION(A,p,r)
    QUICKSORT(A,p,q-1)
    QUICKSORT(A,q+1,r)

수행 시간

파티셔닝에 걸리는 시간

• $\theta(n)$

파티셔닝의 횟수

• 경우에 따라 다릅니다

Balanced partitioning

각 하위 문제의 크기가 기존 문제의 크기의 절반 정도인 n/2 과 n/2 -1이 되도록 나우어지는 경우

$T(n) \leq 2T(n/2) +\theta(n)=O(nlng)$

Unbalanced partitioning

이미 정렬된 배열일 경우

무작위 퀵 정렬

최악의 경우를 피하기 위해 배열에서 피벗을 무작위로 선택하는 방법입니다.

분석

아직 이해 못했기 때문에 후술..

정렬 알고리즘 수행 시간 비교

가장 빠른 알고리즘은 Merge Sort,Heap Sort,Quick Sort가 있지만
각 각의 장 단점을 따져서 사용해야합니다.

• Merge sort
  추가 공간 필요
• Heapsort
  힙 구조를 만들고 구조를 유지 해야함
• Quicksort
  피벗이 어떻게 뽑히냐에 따라 성능에 영향을 미침