퀵 정렬 (Quick Sort)

 

  • 정렬 알고리즘.
  • 선택정렬보다 빠르고 자주 사용된다.
  • 분할 정복 전략. (기준 원소 (pivot)로 분할 (partitioning))

 

  1. 기준 원소를 고른다.
  2. 기준 원소를 기점으로 하위 배열로 분할한다.
  3. 하위 배열에 대해 재귀적으로 퀵 정렬을 호출한다.
    • 어떤 값을 기준원소로 고르든 두 개의 하위 배열에 재귀적으로 퀵 정렬을 호출하면 된다.

 


def quicksort(array) :
    if len(array) < 2 :
        return array  ## 기본단계 : 원소의 개수가 0이나 1이면 이미 정렬된 상태
    else :
        ##재귀단계
        pivot = array[0]
        ##기준 원소보다 작거나 같은 모든 원소로 이루어진 하위 배열
        less = [i for i in array[1:] if i <= pivot]
        ##기준 원소보다 큰 모든 원소로 이루어진 하위 배열
        greater = [i for i in array[1:] if i>pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10,5,2,3])

 

퀵 정렬의 성능은 선택한 기준 원소에 크게 의존한다. 예시로 첫 번째 원소를 항상 기준 원소로 선택한다면 분할된 두 개의 하위 배열중 하나는 항상 빈 배열이 되고 호출 스택이 길어지게 된다. 정 가운데 값을 기준 원소로 정할시 재귀적 호출을 많이 할 필요가 없이 기본 단게에 더 빨리 도달하게 되기 때문에 호출 스택이 짧아진다.

 

  • 참고 : 귀납적 증명 알고리즘이 재대로 동작하는지 증명하는 방법 중 한가지. 귀납적 증명에도 기본단계(base case)와 귀납 단계 (inductive case)라는 두가지 단계가 필요하다. 분할 정복 전략과 함께사용되기도 한다.

 

 

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘