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
2
Hoare’s Partition의경우i는피봇값보다큰값j는피봇보다작은 값에대해
서스왑을실행한다.이스왑을수행하는i의수와j의수는언제나같은데(당연
히쌍으로교환하니까)이쌍의수는결과적으로초기하분포4를따른다따라서
쌍수는(n−x)(x−1)
n−1이된다.
1
n
n
X
x=1
(n−x)(x−1)
n−1=n−2
6
4학교에서통계학을안들어서저도잘모릅니다 ㅠㅠ
17
정렬이 이미되어있는경우
Hoare’s Partition은스왑을실행하지않는다 그러나Lomuto’s Partition은n/2
만큼의스왑을수행한다.
모든배열이같은값으로설정되어있을때
Hoare’s Partition는무한루프에빠진다. Lomuto’s Partition인경우모든단일
요소에대해서스왑을실행하며i = n 이되어최악의파티션또한가지게되어
수행시간은Θ(n2)이된다.
Hoare’s Partition은실질적인측면에서볼때활용도가매우매우매우매우매우
매우매우매우매우떨어진다.버그를내기매우쉬운알고리즘이고코드가독성
또한매우떨어진다또한결정적으로중복값의처리가안되며이를고칠시에결
국성능이Lomuto’s Partition보다 느리게된다.5
다음의 실제테스트결과를봐도알수있다.6
5참고: hoare
6사진의출처인데Hoare, Lomuto testing 테스트케이스가상당히아쉬움을알수있다.
18
6 Quick sort의캐시히트율
다음은 Radix sort(기수정렬)과Quick sort의 입력n에따른수행명령어
수/n를나타낸것이다.기수정렬의시간복잡도는O(n)이나최고차항의계수가
커서초반입력n에대해서는Quick sort가빠른것을보여준다.
그러나실제수행시간과 캐시미스율를비교해봤을때,퀵소트가높은캐시
적중률로인해기수정렬보다약간더빠름을볼수있다.이는알고리즘적인부분
만으로는알수없는결과기에실제컴퓨터구조의캐시개념을알아야한다.작성
자 의견:해당그래프에서n의수치가최대가5000으로나와있는걸생각해볼때
값이정말커지면결국에는시간복잡도에따라기수정렬이더빠름이명확할것
으로예상한다.
19
그림6: Comparing Quicksort and Radix Sort by (a) instructions executed per
item sorted (b) time per item sorted, and (c) cache misses per item sorted.
This data is from a paper by LaMarca and Ladner [1996]. Due to such results,
new versions of Radix Sort have been invented that take memory hierarchy
into account, to regain its algorithmic advantages. Th e basic idea of cache
optimizations is to use all the data in a block repeatedly before it is replaced
on a miss.[2]
20
7개선
7.1 재귀함수제거
재귀함수를사용했을때에loop문과비교했을때나타나는문제점은다음이 있다.
•함수스택의오버헤드
•스택오버플로우위험성
•메모리부과
그러나quick sort의반복문사용은복잡하며코드가독성이떨어진다.
7.2 hybrid sort
Introsort
Quicksort는입력값에대한의존도가크기에일정깊이로들어같을경우이밑을
heapsort로처리하게한다. heapsort는Quicksort와같은시간복잡도가O(nlog n)
이지만최선,최악에대해서비교적평균적인수행시간을보장한다.일반적으로한
계깊이를2 log2n으로설정하고있다.
Quick insertion sort
삽입정렬(insertion sort)의시간복잡도는O(n2)이지만베스트케이스의경우
(완전히정렬되있는경우)O(n)이다.(탐색만하고넘어가기때문)또한작은 n에
대해서는상대적으로삽입정렬이더빠르게되어퀵소트분할중분할크기가일정
n이하가되면삽입정렬으로처리해실제quick sort를사용했을때보다시간적인
이득을볼수있다.또한중복처리에대해서처리가매우빠르기때문에이에의
한성능향상도생각해볼수있다.이n은 일반적으로10이며이값보다작을때
선택정렬을수행하도록한다.
다음은 선택정렬을수행하는n에따른수행시간이다.여기서테스트케이스의
N= 10000 이다.
1INSERTION SORT(A)
2f o r j = 2 t o A. l e n g t h
3key = A[ j ]
4i = j −1
5while i>0 and A[ i ] >key
6A[ i +1] = A[ i ]
21
그림7: 삽입정렬수행의분할크기n에따른퀵정렬수행시간[3]
7i = i −1
8A[ i +1] = key
7.3 중복값처리
네덜란드국기문제(Dutch national flag problem)로다익스트라가처음제시한
이문제는quick sort의중복값입력에대한처리문제를다룬다.배열에 같은값
으로만들어왔을때를생각해보자.같은값이들어왔음에도재귀는lgn까지깊이
들어간다.이를해결하기위해분할을세가지로한다.이를3 way partitioning이
라고한다.기존의왼쪽오른쪽은기존의피봇값보다크고작은값이들어가고 가
운데에는피봇과 같은값을모은다그런후에재귀의범위를왼쪽오른쪽으로만
한다.다음은 Dijstra가제안한 해답이다.코드는c++로작성되어있다.
22
그림8: 3-way-partitioning 작동방식[4]
1vo id Quick3way ( i n t a [ ] , i n t l o , i n t h i )
2{
3i f ( h i <= l o )
4return ;
5i n t l t = lo , i = l o + 1 , gt = hi ;
6i n t v = a [ l o ] ;
7while ( i <= g t )
8{
9i f ( a [ i ] <v )
10 {
11 st d : : swap ( a [ l t ] , a [ i ] ) ;
12 l t ++, i ++;
13 }
14 e l s e i f ( a [ i ] >v )
15 {
16 st d : : swap ( a [ g t ] , a [ i ] ) ;
17 gt −−;
18 }
19 e l s e // a [ i ]==v
20 {
21 i ++;
22 }
23 }
24 Quick3way ( a , l o , l t −1) ;
23
25 Quick3way ( a , gt + 1 , hi ) ;
26 }
다음은 J. Bentley과D. McIlroy 제안한좀더빠른의사코드이다.
그림9: Fast 3-way partitioning 작동방식[4]
1vo id q u i c k s o r t ( Item a [ ] , i n t l , i n t r )
2{
3i n t i = l −1, j = r , p = l −1, q = r ; Item v = a [ r ] ;
4i f ( r <= l ) return ;
5f o r ( ; ; )
6{
7while ( a[++ i ] <v ) ;
8while ( v <a[−− j ] )
9i f ( j == l ) break ;
10 i f ( i >= j )
11 break ;
12 exch ( a [ i ] , a [ j ] ) ;
13 i f ( a [ i ] == v )
14 {
15 p++;
16 exch ( a [ p ] , a [ i ] ) ;
17 }
18 i f ( v == a [ j ] )
19 {
20 q−−;
24
21 exch ( a [ j ] , a [ q ] ) ;
22 }
23 }
24 exch ( a [ i ] , a [ r ] ) ;
25 j = i −1;
26 i = i +1;
27 f o r ( k = l ; k <p ; k++, j −−)
28 exch ( a [ k ] , a [ j ] ) ;
29 f o r ( k = r −1; k >q ; k−−, i ++)
30 exch ( a [ i ] , a [ k ] ) ;
31 q u i c k s o r t ( a , l , j ) ;
32 q u i c k s o r t ( a , i , r ) ;
33 }
34
7.4 median of three
Sedgewick이제안했다.위의 의사코드는pivot값으로맨끝의값을설정한다.이
는역순정렬에의한최악의케이스를생성하기때문에이를입력p,r의중점을
피봇값으로설정하는것만으로도상수시간에개선가능하며,이에대한응용으로
값을랜덤으로세개뽑은후중간값으로하는방법도있다.
7.5 Parallelization
리커젼으로나눠지는두분할은각각의메모리침범을하지않는것이명확하기때
문에쓰레드분할로처리해도문제가없다.이때의가장 이상적인수행시간은트
리깊이인 O(lg n)이다.성능에대해서는병렬화의고질적인문제들도복합적으
로고려해야한다.
and ... 멀티피봇에대한논의도있으나생략한다7. quicksort에대한연구는
(특히pivot설정)매우많이진행되었고진행되고있다.8
7다음이 좋은참고자료가될것이다.Yukun Yao.(2019) A Detailed Analysis of Quicksort
Algorithms with Experimental Mathematics
8원래첫제목은All about Quicksort였으나Quicksort에대한방대한연구를담아내기엔상
상이상으로엄청난논문이줄을 이었다.
25
8성능테스트
환경
•msvc 14.2
•x86 Release모드
•C++
•Intel i7 7700
•RAM 16 GB
26
8.1 HOARE VS LOMUTO
횟수Hoare’s partition lomuto’s partition
1회0.012 0.015
2회0.029 0.031
3회0.033 0.036
4회0.02 0.021
5회0.031 0.036
6회0.009 0.012
7회0.021 0.023
8회0.031 0.034
9회0.017 0.018
10회0.019 0.02
표1: n = 10000000 랜덤순열partition 수행비교
횟수Hoare’s quick sort lomuto’s quick sort
1회0.719 0.759
2회0.704 0.77
3회0.712 0.764
4회0.69 0.761
5회0.698 0.758
6회0.696 0.759
7회0.696 0.769
8회0.692 0.761
9회0.697 0.765
10회0.695 0.755
표2: n = 10000000 랜덤순열quicksort 수행비교
앞서살펴본평균적인시간복잡도와는 다르게partition의실제차이가세배
가나지않았다.
8.2 개선 성능테스트
•PARALLELIZATION
•insertion sort 삽입
•3way partition
27
횟수Hoare’s quick sort lomuto’s quick sort
1회0.025 0.044
2회0.013 0.04
3회0.013 0.038
4회0.014 0.041
5회0.014 0.042
6회0.013 0.044
7회0.015 0.044
8회0.014 0.041
9회0.014 0.041
10회0.016 0.042
표3: n = 10000 역정렬된순열
횟수Hoare’s quick sort lomuto’s quick sort
1회0.023 0.035
2회0.015 0.032
3회0.019 0.037
4회0.017 0.033
5회0.012 0.031
6회0.015 0.036
7회0.016 0.036
8회0.014 0.035
9회0.015 0.034
10회0.02 0.036
표4: n = 10000 정렬된순열
insertion sort와PARALLELIZATION의파티션분할에선lomuto’s partition을
사용했다.
28
횟수PARALLELIZATION quick sort quick sort + insertion sort(n¡=10)
1회0.511 0.717
2회0.605 0.714
3회0.541 0.715
4회0.456 0.711
5회0.727 0.715
6회0.771 0.719
7회0.744 0.705
8회0.643 0.711
9회0.649 0.715
10회0.721 0.712
표5: n = 10000000 랜덤한임의 순열
횟수lumoto’s quick sort Dijkstra’s
1회0.778 0.772
2회0.774 0.778
3회0.759 0.777
4회0.774 0.77
5회0.761 0.766
6회0.773 0.778
7회0.772 0.782
8회0.767 0.774
9회0.777 0.784
10회0.767 0.781
표6: n = 10000000 랜덤한비중복임의 순열
횟수lumoto’s quick sort Dijkstra’s
1회0.41 0.033
2회0.39 0.038
3회0.366 0.032
4회0.367 0.03
5회0.36 0.032
6회0.357 0.032
7회0.361 0.031
8회0.358 0.032
9회0.356 0.031
10회0.365 0.032
표7: n = 10000000 0 ∼1000 범위의 중복포함한 랜덤순열
29
횟수Dijkstra’s J. Bentley D. McIlroy
1회0.036 0.032
2회0.037 0.034
3회0.036 0.031
4회0.038 0.036
5회0.04 0.035
6회0.036 0.034
7회0.043 0.031
8회0.036 0.033
9회0.038 0.036
10회0.036 0.031
표8: n = 10000000 0 ∼1000 범위의 중복포함한 랜덤순열
8.3 std::sort 성능테스트VS J. Bentley D. McIlroy
std::sort는J. Bentley D. McIlroy의3 way partition과수행시간이상당히유
사하다. 3 way partition에inertion sort를삽입했었는데오버헤드때문에전체
수행시간이오히려안좋아졌다.
횟수비중복임의 순열0∼1000 범위의 중복을포함한 랜덤순열모든값이0
1회0.964 0.38 0.007
2회0.927 0.374 0.007
3회0.959 0.373 0.007
4회0.95 0.386 0.006
5회0.946 0.381 0.006
6회0.947 0.383 0.006
7회0.947 0.392 0.006
8회0.929 0.383 0.006
9회0.932 0.385 0.006
10회0.957 0.383 0.007
표9: n = 10000000 std::sort의성능분석
30
횟수비중복임의 순열0∼1000 범위의 중복을포함한 랜덤순열모든값이0
1회0.985 0.337 0.008
2회1.011 0.332 0.008
3회0.979 0.338 0.008
4회0.956 0.336 0.008
5회1.019 0.338 0.007
6회0.974 0.333 0.007
7회0.979 0.341 0.008
8회0.973 0.341 0.009
9회0.98 0.326 0.009
10회0.98 0.332 0.008
표10: n = 10000000 J. Bentley D. McIlroy의3 way partition의성능분석
31
그림차례
1 quick sort 작동예시[1]......................... 5
2증가함수의대소비교[1]......................... 7
3 quick sort 최선의분할케이스재귀트리[1] ............. 10
4 9:1로분할하는재귀트리[1] ...................... 11
5최악,최선이번갈아나타나는재귀트리[1] .............. 11
6 Comparing Quicksort and Radix Sort by (a) instructions executed
per item sorted (b) time per item sorted, and (c) cache misses per
item sorted. This data is from a paper by LaMarca and Ladner
[1996]. Due to such results, new versions of Radix Sort have been
invented that take memory hierarchy into account, to regain its
algorithmic advantages. Th e basic idea of cache optimizations is
to use all the data in a block repeatedly before it is replaced on a
miss.[2] ................................. 20
7삽입정렬수행의분할크기n에따른퀵정렬수행시간[3] . . . . . . . 22
8 3-way-partitioning 작동방식[4] ................... 23
9 Fast 3-way partitioning 작동방식[4]................. 24
표차례
1 n = 10000000 랜덤순열partition 수행비교............. 27
2 n = 10000000 랜덤순열quicksort 수행비교............. 27
3 n = 10000 역정렬된순열....................... 28
4 n = 10000 정렬된순열......................... 28
5 n = 10000000 랜덤한임의 순열.................... 29
6 n = 10000000 랜덤한비중복임의 순열............... 29
7 n = 10000000 0 ∼1000 범위의 중복포함한 랜덤순열........ 29
8 n = 10000000 0 ∼1000 범위의 중복포함한 랜덤순열........ 30
9 n = 10000000 std::sort의성능분석................. 30
10 n = 10000000 J. Bentley D. McIlroy의3 way partition의성능분석31
32
참고자료
https://en.wikipedia.org/wiki/Quicksort
https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto
https://www.acmicpc.net/blog/view/58
https://www.youtube.com/watch?v=hq4dpyuX4Uw&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&
index=11
https://en.wikipedia.org/wiki/Recursion_(computer_science)
https://algs4.tistory.com/45
https://arxiv.org/pdf/1905.00118.pdf
http://rohitja.in/lomuto-hoare-partitioning.html
https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf https:
//en.wikipedia.org/wiki/Dutch_national_flag_problem
https://en.wikipedia.org/wiki/Introsort
https://www.geeksforgeeks.org/internal-details-of-stdsort-in-c/ https:
//stackoverflow.com/questions/44441876/quick-sort-using-stack-in-c
http://fpl.cs.depaul.edu/jriely/ds1/extras/lectures/23Quicksort.
pdf
참고문헌
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clif-
ford Stein. Introduction to Algorithms, Second Edition. MIT Press and
McGraw-Hill, 2001. ISBN 0-262-03293-7.
[2] Patterson, David A./ Hennessy, John L. Computer Organization and
Design, Fourth Edition: The Hardware/Software Interface (The Morgan
Kaufmann Series in Computer Architecture and Design). 2014. ISBN-13
9788994961897, ISBN-10 8994961895
[3] Sedgewick, R. (1978). ”Implementing Quicksort programs”. Comm. ACM.
21 (10): 847–857. doi:10.1145/359619.359631.
[4] Robert Sedgewick, Kevin Wayne Algorithms, 4th Edition, 2001 ISBN-13:
978-0321573513
33
