선형시간 선택 알고리즘에 대한 자료 요약/정리 레포트

본문내용

기준원소보다 큰 오른쪽은 계산하지 않는다.
6 4 27 1 20 / 28 13 11 35 17 / 39 37 19 14 45 / 38 23 29 51 42 / 31
/ 60 62 66 76 83 /
1
4
6
20
27
11
13
17
28
35
14
19
37
39
45
23
29
38
42
51
31
1
4
6
20
27
11
13
17
28
35
31
14
19
37
39
45
23
29
38
42
51
다시 기준원소 31보다 확실히 작은 6개의 수와 작거나 클수도 있는 8개의 수로 분할된다. 이들은 다시 기준원소 31보다 작은수와 큰수로 나눈다.
1 11 14 23 4 / 13 19 29 6 17 / 20 28 27
35
1
11
14
23
4
13
19
29
6
17
20
28
27
1
4
11
14
23
6
13
17
19
29
20
27
28
다시 기준원소 17보다 작은 5개의 수와 작거나 클지도 모르는 3개의 수로 분할된다. 이를 다시 기준원소 17보다 작은 수와 큰 수로 나눈다.
1 4 6 11 13 14 17 20 23
기준원소 17은 7번째 원소이고, 찾으려고 하는 수는 5번째 수이기 때문에
13이 5번째로 작은 수가 된다.

키워드

선형시간 ,   선택,   알고리즘,   최악