[알고리즘] Quick sort: divide-and-conquer & loop invariants

(2021.10.09)

알고리즘 수업들으면서 정리하기 8탄

5주차 내용-2 

 

 

---

Quick sort

input: sequence of numbers

output: permutation (오름차순)

 

 

 

 

Divide-and-conquer approach

• Divide: Partiton the array into two subarrays(A[p..q-1] and A[q+1..r]) (A[p..q-1] ≤ A[q] < A[q+1..r]) 
• Conquer: Sort the two A[p..q-1] and A[q+1..r] by recursive calls to quick sort
• Combine: no work is needed to combine them(subarrays are already sorted)

a pivot x = A[q]

 

출처: 교수님 강의노트

 

 

PARTITON(A,p,r)
  x=A[r]
  i=p-1
  
  for j=p to r-1
    if A[j] ≤ x
      i=i+1
      exchange A[i] with A[j]

  exchange A[i+1] with A[r]
  return i+1

 

// main

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

 

 

 

 

partition 과정 예시

 

 

 

quick sort 의 loop invariants

 

statement: 1) A[p..i] ≤ pivot

              2) A[i+1..j-1] > pivot

              3) A[r]=pivot

Initialization(초기조건): loop가 시작하기 전에도 참이어야하는데, i=p-1, j=p 이므로 A[p..i]와 A[i+1..j-1]은 empty이고, r은 pivot이기 때문에 참이다.

Maintenance(유지조건): loop가 시작되면, A[j]≤pivot 이라면, i가 증가하고, A[j] 와 A[i](증가한 i)이 swap하고, j가 증가한다. A[j]>pivot 이라면, j만 1 증가한다. 따라서 A[p..i]≤pivot, A[i+1..j-1]>pivot, A[r]=pivot 을 만족하므로 참이다.

Termination(종료조건): loop가 종료되면, j=r이다. A는 세가지로 partiotioning된다. A[p..i]≤pivot 인 부분과 A[i+1..r-1]?pivot 인 부분, 그리고 A[r]=pivot 인 부분이다.

 

 

 

 

runtime of quick sort

 

quick sort는 subarray가 balanced 인지, unbalanced 인지에 따라서 runtime이 다르다

 

• Worst case: unbalanced 한 경우
• Best case: balanced 한 경우

 

Worst case

 

 

 

 

Best case