Introduction to Quick Sort
EUnS
2019년11월15일
차례
차례...................................... 1
1소개.................................... 3
2의사코드및동작............................. 3
3여러기초지식.............................. 6
3.1 시간복잡도............................. 6
3.2 조화급수의상한과하한 ..................... 6
3.3 확률................................. 7
4대략적인복잡도분석.......................... 9
4.1 최악의분할케이스........................ 9
4.2 최선의분할케이스........................ 9
4.3 일반적인케이스직관적인방법 .................. 10
5상세분석................................. 13
5.1 최악의케이스분석........................ 13
5.2 기대수행시간........................... 13
5.3 Hoare’s Partition VS Lomuto’s Partition . . . . . . . . . . . . 16
6 Quick sort의캐시히트율........................ 19
7개선.................................... 21
7.1 재귀함수제거........................... 21
7.2 hybridsort............................. 21
7.3 중복값처리............................ 22
7.4 medianofthree .......................... 25
7.5 Parallelization........................... 25
1
8성능테스트................................ 26
8.1 HOARE VS LOMUTO . . . . . . . . . . . . . . . . . . . . . 27
8.2 개선 성능테스트.......................... 27
8.3 std::sort 성능테스트VS J. Bentley D. McIlroy . . . . . . . . . 30
그림차례................................... 32
표차례.................................... 32
참고자료................................... 33
참고문헌33
2
1소개
•일반적으로가장많이사용하는정렬알고리즘
•비교정렬
•내부정렬
•불안정 정렬
•평균복잡도:O(nlg n)
•최악의복잡도:O(n2)
•C++ std::sort의내부구현이퀵소트로되어있음1
2의사코드및동작
분할정복(divide and conquer) 방법을통해설계되었다.작동의 이해는 당장에
유튜브에검색만해봐도 동작설명하는5분짜리유튜브가많으니그걸참고하는
게편하다.
1QUICKSORT(A, p , r )
2i f p<r
3q = PARTITION(A, p , r )
4QUICKSORT(A, p , q−1)
5QUICKSORT(A, q+1, r )
Lomuto’s Partition Scheme
1PARTITION(A , p , r )
2x= A[ r ] // p i v o t
3i = p−1
4f o r j = p to r−1
5i f A[ j ]<= x
6i = i + 1
7exchang e A[ i ] with A[ j ]
8exchang e A[ i +1] with A[ r ]
9return i + 1
1정확하게는introsort : quicksort와heapsort, insertionsort를셋다사용한다.
3
Hoare, C. A. R.이1961년처음으로Quick sort를제안했다. PARTITION
은현재 일반적으로Lomuto가제안(1999)한PARTITION이 유명하여이를기
준으로설명하며, Hoare가제안한Partition의두프로시저의비교는후에따로
다룬다.
PARTITION 프로시저의시간복잡도는Θ(n)이다.
4
3여러기초지식
3.1 시간복잡도
정의3.1 (복잡도)상한,하한,
•상한big O O
함수f(n), g(n)에대해서0≤f(n)≤cg(n)(∀n≤n0)을만족하는n0,양
의상수c가존재할때f(n) = O(g(n))이라한다.
•하한 omega Ω
함수f(n), g(n)에대해서0≤cg(n)≤f(n)(∀n≤n0)을만족하는n0,양
의상수c가존재할때f(n) = Ω(g(n))이라한다.
•Theta Θ
Θ(g(n))일필요충분조건은f(n) = O(g(n))이고f(n) = Ω(g(n))이성립
할때이다.
3.2 조화급수의상한과하한
n
X
k=1
1
k= Θ(lg n)
감소함수f(k)에대해서다음이 성립한다
Zn
m−1
f(x)dx ≤
n
X
k=m
f(k)≤Zn+1
m
f(x)dx
증가함수f(k)에대해다음이 성립함을그림4를통해서이해 할 수있다.감
소함수는이와반대로생각하면쉽게해당부등식을 이해할 수있다.
Zn+1
m
f(x)dx ≤
n
X
k=m
f(k)≤Zn
m−1
f(x)dx
다음두가지방식으로계산한다
n
X
k=2
1
k+ 1 ≤Zn+1
2
f(x)dx + 1 = ln(x) + 1 = O(ln x)
Zn+1
1
f(x)dx = ln(x+ 1) = Ω(ln x)≤
n
X
k=1
1
k
따라서
n
X
k=1
1
k= Θ(lg n)
6
4대략적인복잡도분석
해당절과다음절의복잡도분석은quicksort에모든입력값에중복값이존재하
지않음을 미리가정하고있다.
4.1 최악의분할케이스
최악의경우분할케이스를생각해보자 이는왼쪽오른쪽분할이한쪽으로쏠려
(오름차순,내림차순)극도로불균형하게일어났을때이다.피봇값에의한분할이
아예일어나지않을때최악의케이스가된다.이때비용을나타낸재귀함수다.
T(n) = T(n−1) + cn
T(n) = T(n−1) + cn
=T(n−2) + c(n−1) + cn
=c
n
X
k=1
k
=1
2cn2
= Θ(n2)
따라서시간복잡도는Θ(n2)이다.
4.2 최선의분할케이스
정확하게반으로나누어졌을때최선의분할케이스이다.
이때의비용을나타낸재귀함수는
T(n) = 2T(n
2) + cn
이다.
그림2의 재귀트리를 통해서전체비용을계산하여시간복잡도를구하면Θ(nlg n)
이다.3
3marster theory를사용하여바로구해도된다.
9
서이둘의시간복잡도를합쳐도결국Θ(n)이고이를합쳐서보면결국에최선
의분할케이스가된다따라서이때의시간복잡도는결국Θ(nlg n)이다.
12
5상세분석
5.1 최악의케이스분석
실제재귀함수를일반화식은다음이 된다.
T(n) = max
0≤q≤n−1(T(q) + T(n−q−1)) + Θ(n)
이때T(n)이Θ(n2)임을 보이면된다.치환법을 이용해서이점화식을풀수있
다.T(n)≤c1n2이라가정하자.그러면
T(n)≤max
0≤q≤n−1(c1q2+c1(n−q−1)2) + Θ(n)
이성립한다.
0≤q≤n−1인c1q2+c1(n−q−1)2에대해서
f(q) = c1q2+c1(n−q−1)2이라하고f′(q)=2c1q−2c1(n−q−1)이므로
q=n−1
2일때극솟값을가진다.이극솟값은q의존재범위에포함되고따라서
이차함수의특성에따라양끝점이최댓값이될수있는후보가된다.q= 0일때와
q=n−1일때극댓값을가지는데이때의두함숫값은같아서둘중어느값을택
해도최댓값이된다.
T(n)≤c1(n−1)2+ Θ(n)
≤c1n2−c(2n−1) + Θ(n)
≤c1n2
이때Θ(n) = dn에서c1> d인상수c1을가지게함으로써결과적으로
T(n)이c1n2보다작거나같음을 보일수있다.반대로c2n2≤T(n)임을 가정하
고c2< d인상수를잡음으로T(n)이c2n2보다크거나같음을 보일수있다.따라
서T(n) = Θ(n2)를얻을수있다.
5.2 기대수행시간
1부터모든n에대해서모든비용의평균.
13
E[X] = E"n
X
i=1
Xi#
=
n
X
i=1
E[Xi]
시간복잡도를분석하기위해서다음의 보조정리를 이용한다.
Lemma 5.1. X가길이가n인배열에서QUICKSORT의전체실행에대해서
PARTITION의4행에서수행된비교문의실행수라고 가정하면QUICKSORT
의실행시간은O(N+X)이다.
Proof. 알고리즘은PARTITION을최대n회 호출한다.각호출은for 루프를
실행하는데, for 루프의각반복은4행비교문을실행한다.
따라서모든호출에대해서총비교수X를구하는문제로바뀌는데각호
출에대한비교를분석하지않고총비교수를계산한다.그렇게하기위해배열
A={z1, z2, ..., zn}의각요소가내림차순으로정렬되어있다고생각한다.또한
집합Zij ={zi, zi+1, ..., zj}라정의한다.여기서zi와zj는최대한번비교된다.
이유는PARTITION에서비교를하는경우는하나의원소가pivot으로선택되
었을때인데,이후에이pivot은절대로다른원소와비교하지않는다.따라서
Xij =I{zi가zj와비교한다}
X=
n−1
X
i=1
n
X
j=i+1
Xij
E[x] = E
n−1
X
i=1
n
X
j=i+1
Xij
=
n−1
X
i=1
n
X
j=i+1
E[Xij ]
=
n−1
X
i=1
n
X
j=i+1
P r{zi가zj와비교한다}
14
P r{zi가zj와비교한다=P r{Zij 에서zi또는zj가첫번째로선택된다.}
=P r{Zij 에서zi가첫번째로선택된다.}+P r{Zij 에서zj가첫번째로선택된다.}
=1
j−i+ 1 +1
j−i+ 1
=2
j−i+ 1
E[X] =
n−1
X
i=1
n
X
j=i+1
2
j−i+ 1
이는j−i을k로치환해서상한을얻을수있다.
E[X] =
n−1
X
i=1
n
X
j=i+1
2
j−i+ 1
=
n−1
X
i=1
n−i
X
k=1
2
k+ 1
≤
n−1
X
i=1
n
X
k=1
2
k
≤
n−1
X
i=1
clg n
≤cn lg n
E[X] = O(nlg n)
15
하한은다음과 같이직접구한다.
E[X] =
n−1
X
i=1
n−i
X
k=1
2
k+ 1
=
n−1
X
k=1
2
k+ 1 +
n−2
X
k=1
2
k+ 1 +· · · +
1
X
k=1
2
k+ 1
= (n−1) 2
1+1+ (n−2) 2
2+1+· · · + 1 ×2
(n−1) + 1
=
n−1
X
k=1
2
k+ 1 ×(n−k)
=
n−1
X
k=1 2n
k+ 1 −2k
k+ 1
= 2n
n−1
X
k=1
1
k+ 1 −2
n−1
X
k=1
k
k+ 1
≥2nc lg n−2(n−1) ∵−
n−1
X
k=1
k
k+ 1 ≥ −
n−1
X
k=1 k
k+ 1 +1
k+ 1!
≥Ω(nlg n)
따라서
Θ(nlg n)
5.3 Hoare’s Partition VS Lomuto’s Partition
Lomuto’s Partition Scheme
1PARTITION(A , p , r )
2x= A[ r ] // p i v o t
3i = p−1
4f o r j = p to r−1
5i f A[ j ]<= x
6i = i + 1
7exchang e A[ i ] with A[ j ]
8exchang e A[ i +1] with A[ r ]
9return i + 1
Hoare’s partition scheme
1PARTITION(A , p , r )
2x= A[ r ] // p i v o t
16
3i = p
4j = r
5while TRUE
6repeat
7j = j −1
8u n t i l A[ j ] <= x
9repeat
10 i = i + 1
11 u n t i l A[ i ] >= x
12 i f i<j
13 exchang e A[ i ] with A[ j ]
14 e l s e r e t u r n j
다음사이트의답변을번역했습니다 stackexchange
이해하기편하고 간편한알고리즘을따질때Lomuto’s Partition이간편하다.
그렇기에우리들이알고리즘을 이렇게기억하고있는것일것이다.성능적인측
면만따지면다음을 비교해볼수있다.
비교횟수
모든요소가피봇가비교하기때문에둘다n-1번비교한다.
스왑횟수
Lomuto’s Partition의경우1<=x <=n인pivot값x에대해서스왑은정확히
x−1번수행한다.
1
n
n
X
x=1
(x−1) = n−1