알고리즘 이론 7강. 퀵 정렬(Quick Sort)

 

[퀵 정렬(Quick Sort)]

- 주어진 배열에서 pivot(기준점)을 잡아 이를 기준으로 분할후 정복하는 방법

 

- 최악 수행 시간(Worst-case) : Θ(n^2)

- 평균 수행 시간(Average-case) : Θ(nlogn)

  (병합, 힙 정렬과 같은 Θ(nlogn)이지만 이들보다 2배정도 더 빠르다)

 

- 분할-정복 알고리즘중 하나

 

 

 

[퀵 정렬 알고리즘]

QUICKSORT(A,p,r):
  if p < r:
    then q <- PARTITION(A,p,r)   # q값 찾는 알고리즘
      QUICKSORT(A,p,q–1)
      QUICKSORT(A,q+1,r)
      
initial call:
QUICKSORT(A,1,length[A])

 

 

 

[PARTITION 알고리즘]

: 부분배열의 마지막 값(pivot)을 기준으로 비교해, 보다 작은 값을 왼쪽, 큰 값을 오른쪽으로 위치하게끔 한다.

PARTITION(A,p,r):
  x <- A[r]    #배열의 마지막 값
  i <- p–1
  for j in <- p to r–1
    do if A[j] <= x
      then i <- i + 1
        exchange A[i] <-> A[j]
  exchange A[i+1] <-> A[r]
  return i+1

– i : 기준으로 왼쪽에 A[r]값보다 작은 값, 오른쪽에 보다 큰 값 위치

– j : 기준으로 그 이전값이 비교완료된 값

PARTITION 코드 작동 예시

 

 

 

[퀵정렬 알고리즘의 수행력]

: pivot 설정에 따라 partition이 균형있게 이뤄지는지 아닌지에 따라 수행력이 달라진다.

 

– 최악 케이스 : pivot이 partition으로 위치된 후에 오른쪽 or 왼쪽에 한개의 원소만 위치해있을때.(Θ(n^2))

– 최선 케이스 : pivot 기준 양 partition의 크기가 동일 할때.(Θ(nlogn))

 

# 퀵정렬 점화식 ( 점화식증명 방법 생략)

  Worst = T(n-1) + Θ(n)

  Best = 2T(n/2) + Θ(n)

  Average = T(9n/10) + T(n/10) + cn

 

 

 

[pivot값 설정방법 종류]

1. 배열 S의 첫번째(마지막) 원소를 pivot으로 설정
2. 랜덤 pivot 
3. 배열의 중간값을 pivot
4. 예측되는 중간값을 pivot : 배열의 처음, 중간 끝 원소중 중간 값을 pivot으로

(1,2는 최악 pivot 설정 위험성이 있고, 3은 배열 S가 정렬될 필요성이 있기에 시간적으로 비효율..)

 

 

 

[퀵 정렬 vs 삽입 정렬]

 적은 양의 배열(20이하)는 삽입정렬이 빠르고, 그 이상은 퀵정렬이 빠르다.

퀵 정렬은 재귀 방식이기 때문에 적은 값에선 느리다.

그래서 Hybrid 알고리즘으로 배열의 크기에 따라 사용하는 정렬 방법을 다르게 한다.