퀵정렬

[33, 15, 10]의 배열이 있다고 치자. 분할정복을 이용해서 이것을 정렬하기 위해서는 어떻게해야하는가?

1. 배열에서 원소를 하나고른다. 이것을 기준원소(pivot)이라고한다. 여기서는 33을 기준원소로 잡았다.
2. 이제 모든원소를 기준원소보다 작은원소와 큰원소로 분류를 한다. 15, 10, 33(기준원소) [] 마지막은 빈배열. 이것을 분할이라고 한다.

퀵배열은 다음과 같이 구성이 된다.

• 기준 원소보다 작은 하위 배열
• 기준 원소
• 기준 원소보다 큰 하위 배열

  여기서 중요한것은 양쪽에 있는 하위 배열은 정렬이 되어 있지 않다는 것이다!

예시의 경우에는 [10, 15] + [33] + [] = [10, 15, 33]인 경우이다. 이제 원소의 개수를 늘려서 5개로 기준을 늘려보자. [3, 5, 2, 1, 4] 위의 배열은 기준원소를 무엇으로 삼느냐에 따라 5가지 방법으로 달라질 수 있다.

1. [1] [3, 5, 2, 4]
2. [1] [2] [3, 5, 4]
3. [2, 1] [3] [5, 4]
4. [3, 2, 1] [4] [5]
5. [3, 2, 1, 4] [5] []
   • 위의 배열을 통해 모든 하위배열들이 0-4개까지의 원소를 가진것을 알 수 있다. 이것을 n개의 개수인 배열에 일반화를 시키면 n개의 기준원소로 나눌 수 가 있고, 0~n-1까지의 원소를 가진것을 알 수 있다.

어떤 원소를 기준원소로 고르던, 양쪽의 하위 배열에 재귀적으로 퀵 정렬을 하면 된다.

• 예를들어 3을 기준원소로 하면
  1. qsort([2, 1]) + [3] + qsort([5, 4])
  2. [1, 2] + [3] + [4, 5]
  3. [1, 2, 3, 4, 5]

python code

def quicksort(array):
	if len(array) < 2:
    	return array
    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] + greater)

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

퀵정렬은 선택한 기준 원소에 따라 처리속도가 달라지는 특징이 있다. 일반적으로 O(nlogn)을 따른다.

맺으며

• 분할 정복은 문제를 더 작은 조각으로 나누어서 푼다.
• 퀵 정렬을 구현하려면 기준 원소를 무작위로 선택한다. 평균적인 실행시간은 O(n log n)이다.