Quick Sort

 분할 정복 알고리즘을 사용한 정렬 알고리즘이다.굉장히 유명한 알고리즘으로 현재 많은 기본 언어에서의 Sort()함수는 Quick sort를 사용한다.퀵 정렬은 "in place"정렬이다.이는 삽입정렬과 동일하며 병합정렬와는 다르다.in place는 정렬하는데 있어서 추가적인 배열을 할당하지 않는다.반면 병합정렬은 combine하는데 있어서 배열을 추가적으로 할당해야한다.따라서 속도의 차이가 존재한다.

이제 알고리즘을 소개하자면 다음과 같다.

1. Divide:배열 a를 두 개의 부분 배열로 분할하는데 이는 피봇(Pivot)이라는 기준원소를 기준으로 피봇보다 작은 원소를 모아두는 배열과 큰 원소를 모아두는 배열로 나눈다.
2. Conquer:퀵 정렬을 재귀 호출해서 두 부분의 배열을 정렬한다.
3. Combine:부분 배열은 이미 정렬되어 있으므로 따로 합치는 작업을 할 필요가 없다.

Divide

이때 분할과정은 선형시간의 복잡도를 갖는다.O(n)

이를 수도코드로 구현하면 다음과 같다.

qucik sort's psuedo code

partitioning의 과정의 예는 다음과 같다.

Example of partitioning

이제 퀵정렬의 과정을 보면 다음과 같다.

example of quick sort

퀵 정렬의 특징은 한번 Partitioning을 했을때 적어도 pivot은 무조건 정렬된 자리를 찾아간다는 것이다.그리고 이는 알고리즘이 무한푸프가 걸리지 않는다는걸 보장한다.

알고리즘 성능 분석

 Quicksort에서 성능의 가장 중요한 작용을 하는 것은 Pivot이다.피봇을 어떻게 고르냐에 따라서 케이스가 나뉜다.

우선 worst-case를 분석해보면 다음과 같다.

1.Worst case

 극단적인 경우로는 피봇보다 모든 원소가 크거나 작은 경우로 이를 달리말하면 0개와 n-1개로 분할된다한다.그리고 이와 같은 상황이 매번 재귀호출될때마다 반복한다고 가정하면 점화식과 마스터정리를 통한 시간복잡도는 다음과 같다.

worst-case of quicksort

 

이때의 재귀트리를 살펴보면 

worst-case of recursion tree

즉,하나의 branch만 길이가 깊어지는걸 확인할 수 있다.

2.Best-case

 이 경우는 운이 좋게 Pivot을 잘 선택했을때로 중앙값을 골랐다 가정하면 다음과 같다.

Best case

그렇다면 1:9로 나뉘는 피봇을 선택한다는 가정을 해보고 점화식을 작성해보면 다음과 같다.

1:9 example

이때의 재귀트리는 다음과 같다.

1:9's recursion tree

이때도 결국 시간복잡도는 nlogn이됨을 확인할 수 있다.따라서 굉장히 우수한 정렬 알고리즘으로 평가 받는다.

Randomized Quicksort

 퀵소트는 피봇에 따라 성능이 많이 차이나기에 이를 해결하기 위한 방안으로 나오게된 알고리즘으로 기본적으로 퀵소트와 동일한 알고리즘이지만 피봇을 랜덤으로 정한다는 점에서 차이가 난다.따라서 정말 랜덤으로 최악의 경우를 계속 겪게되면 시간 복잡도는 O($n^{2}$)이 되지만 그럴확률은 매우 낮다.즉,입력 배열이 정렬되어 있거나 특정한 패턴을 가지고 있어도 O(n logn)의 성능을 보여줄 수 있다.

Randomized Quicksort analysis

  분석을 위해서는 랜덤 변수와 기대값을 사용한다.T(n)을 배열크기가 n일 때,랜덤화된 퀵 정렬의 실행 시간을 나타내는 랜덤변수라 할때

$X_{k}$는 모든 분할이 동일한 확률로 발생하고 다음과 같이 정의된다.

지표 랜덤 변수

이제 T(n)에 대해서 생각해보면 다음과 같다.

T(n)

이를 잘 정리해보면 다음과 같은 수식이 도출된다.

T(n)

랜덤 변수가 사용되는 이유는 배열이 2개 나뉘는 퀵소트에서 한 배열의 크기가 0이여서 분할이 이루어지지 않은 경우다.이때는 0으로 처리해야지 정확한 성능평가가 가능하다.이제 기대값을 구해보자

기대값 수식

식을 풀어보면 다음과 같다.

기대값 수식 전개

 이 식의 전개과정중에서 중요한것은 $E[X_k]$이다.결과론 적으로는 $E[X_k] = 1/n$이다.그 이유는 모든 분할이 균등한 확률로 발생하기 떄문으로 1:9,8:2,7:3으로 분할된 확률은 모두 동일하기 때문이다.저 정리된 수식을 수학적 귀납법으로 anlogn보다 작은지를 증명하면 된다.

 그전에 우선 n logn을가정하고 n에대해 식을 구해보면 다음과 같다.

n logn에 대해 구한 식

그리고 이제 아까전에 구했던 식을 전개해보자

정리된 식

 이로써 충분히 큰 a값에 대해서 정리된 식은 0보다 크므로 시간복잡도가 O(n log n)임을 증명했다.