Quick sort

기본규칙

1) sorted list 와 unsorted list 를 둔다.
2) unsorted list 의 맨 끝에서 pivot 을 고른다
3) pivot 대로 좌 우를 정렬한다.

생각의 변화

병합정렬에서는 분리후 merge 하지만, 퀵에선 반대로 partition 후에 분리하게 된다.

partition 시, pivot 보다 작은 수는 좌측에 하나씩 쌓아간다 (i)
다 쌓인 시점에 pivot 을 i로 옮긴다

pivot 과 비교할 index j 를 둔다.

partition 1번은 j for loop 1번이다.

pseudo code

partition(&A, lo, hi)
    pivot = A[hi]
    i = lo

    for j=lo  j<=hi-1  j++
        if A[j] <= pivot
            swap A[i] A[j]
            i++
        
    swap A[i] A[hi]
    return i

quick_sort(&A, lo, hi)
    if lo>=hi
        return
    
    p = partition(A, lo, hi)
    
    quick_sort(A, lo, p-1)
    quick_sort(A, p+1, hi)

검증

Q(0 6)
38 27 43 9 3 82 10
ij              p    P(0 6)
i        j

swap i j    i++

9 27 43 38 3 82 10
  i     j
           j

swap i j    i++

9 3 43 38 27 82 10
    i     j
             j
swap i p

9 3 10 38 27 82 43
    i

return 2

Q(0 1) Q(3 6) remain

Q(0 1)
9  3
ij p    P(0 1)

swap i p

3  9
i
   
return 0

Q(0 -1) x
Q(1 1) x

Q(3 6)
      38 27 82 43
      ij       p    P(3 6)

swap i j    i++

      38 27 82 43
         ij

swap i j    i++

      38 27 82 43
            ij

swap i p

      38 27 43 82
            i
            
return 5

Q(3 4)    remain
Q(6 6) x

Q(3 4)
     38 27    P(3 4)
     ij p         
     
     swap i p
     
     27 38

3 9 10 27 38 43 82

시간복잡도