* 아래 문제 출처 : 3장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사
** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.
주어진 배열이 아래 표와 같고 5번째로 작은 숫자를 찾을 때, 알고리즘을 적용하여 선택 문제를 푸는 과정은 다음과 같습니다.
INDEX
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
ARRAY
|
6
|
1
|
3
|
9
|
4
|
5
|
8
|
2
|
7
|
+ 직관적으로 사람은 답이 5라는 것을 알 수 있습니다. 답을 기억한 상태에서 알고리즘을 적용하며 결과가 맞게 나왔는 지 확인해 보겠습니다. +
먼저 Selection(ARRAY, left, right, k)에서 k를 설정합니다. 여기서 k는 n번째로 작은 숫자를 찾는 문제에서 n과 동일합니다.
문제에 적용하면 Selection(ARRAY, 0, 8, 5)로 설정할 수 있습니다.
1단계
먼저 피봇을 설정합니다. 알고리즘 상 피봇은 랜덤으로 설정되게 되어 있는데 보통 중간 위치를 설정하는 것이 덜 번거롭기 때문에 INDEX 4를 피봇으로 선정하겠습니다.
INDEX
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
ARRAY
|
6
|
1
|
3
|
9
|
4
|
5
|
8
|
2
|
7
|
피봇을 선정하고 나면 피봇의 값을 제일 왼쪽의 INDEX로 옮깁니다.
INDEX
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
ARRAY
|
4
|
1
|
3
|
9
|
6
|
5
|
8
|
2
|
7
|
그 다음 ARRAY에서 작은 값이 왼편에 올 수 있도록 서로 자리를 교환합니다.
INDEX
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
ARRAY
|
4
|
1
|
3
|
9
|
6
|
5
|
8
|
2
|
7
|
9, 2를 서로 교환하고
INDEX
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
ARRAY
|
4
|
1
|
3
|
2
|
6
|
5
|
8
|
9
|
7
|
피봇을 작은 수들의 제일 마지막 INDEX인 INDEX 3과 자리를 바꿉니다.
INDEX
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
ARRAY
|
2
|
1
|
3
|
4
|
6
|
5
|
8
|
9
|
7
|
그러면 피봇을 기준으로 피봇보다 작은 값들은 왼쪽에 위치하게 됩니다.
그 다음, 알고리즘에 따라 S = ( p -1 ) - left + 1에서 S값을 구합니다.
p는 피봇의 INDEX, left는 가장 왼쪽의 INDEX입니다.
따라서 S = ( p -1 ) - left + 1 는 S = (3-1) - 0 + 1 이고 계산하면 3이 됩니다.
S는 피봇보다 작은 값들의 개수입니다.
이제 5번째로 작은 값을 찾기 위해 조건문으로 넘어갑니다.
[만약 k가 S보다 작거나 같다면 Selection(ARRAY, left, p-1, k)로 설정하라] 라는 내용의 조건문입니다.
k는 5, S는 3이므로 위의 조건문은 거짓입니다. 따라서 다음 조건문으로 넘어갑니다.
[만약 k == S+1이라면, 피봇 값을 반환하라] 라는 내용입니다. 참일 경우, 피봇 값이 k번째로 작은 값이라는 뜻인데 5= 4 이므로 거짓이 됩니다.
위의 조건문 둘 다 거짓인 경우 Selection을 다음과 같이 다시 설정해줍니다.
Selction(ARRAY, p+1, right, k-S-1), 문제에 적용하면 Selction(ARRAY, 4, 8, 1)이 됩니다. INDEX 4부터 8까지, 1번째로 작은 숫자를 찾으라는 뜻입니다.
2단계
INDEX
|
4
|
5
|
6
|
7
|
8
|
ARRAY
|
6
|
5
|
8
|
9
|
7
|
마찬가지로 피봇을 설정해줍니다. 저는 INDEX 6을 피봇으로 선정하겠습니다.
INDEX
|
4
|
5
|
6
|
7
|
8
|
ARRAY
|
6
|
5
|
8
|
9
|
7
|
과정은 1단계와 동일합니다. 피봇 값을 제일 왼쪽으로 옮기고 피봇 값보다 작은 수가 왼편에 오도록 자리를 바꿔줍니다.
INDEX
|
4
|
5
|
6
|
7
|
8
|
ARRAY
|
8
|
5
|
6
|
9
|
7
|
그 다음 피봇 값보다 작은 수가 왼편에 오도록 자리를 바꿔줍니다. 피봇 값을 피봇보다 작은 수들의 제일 오른쪽 편에 있는 INDEX 7과 바꿔주면 됩니다.
INDEX
|
4
|
5
|
6
|
7
|
8
|
ARRAY
|
7
|
5
|
6
|
8
|
9
|
이제 다시 S값을 구합니다.
S = ( p -1 ) - left + 1에서 p는 7, k는 1입니다.
S = ( p -1 ) - left + 1 는 S = (7-1) - 4 + 1 이고 계산하면 3이 됩니다.
이제 1번째로 작은 값을 찾기 위해 조건문으로 넘어갑니다.
[만약 k가 S보다 작거나 같다면 Selection(ARRAY, left, p-1, k)로 설정하라] 라는 내용의 조건문입니다.
k는 1, S는 3이므로 위의 조건문은 참입니다. 따라서 Selection을 다음과 같이 설정합니다.
Selection(ARRAY, 4, 6, 1)이 되고 INDEX 4부터 6까지, 1번째로 작은 숫자를 찾으라는 뜻입니다.
3단계
마찬가지로 가운데 있는 INDEX 5를 피봇으로 선정하고, 5보다 작은 ARRAY값이 없기 때문에 값을 왼편으로 이동시키는 과정은 표현하지 않겠습니다. 알고리즘 상 실행은 됩니다.
이제 다시 S값을 구합니다.
S = ( p -1 ) - left + 1에서 p는 4, k는 1입니다.
S = ( p -1 ) - left + 1 는 S = (4-1) - 4 + 1 이고 계산하면 0이 됩니다.
이제 1번째로 작은 값을 찾기 위해 조건문으로 넘어갑니다.
[만약 k가 S보다 작거나 같다면 Selection(ARRAY, left, p-1, k)로 설정하라] 라는 내용의 조건문입니다.
k는 1이고 S는 0이므로 거짓입니다. 따라서 다음 조건문으로 넘어갑니다.
[만약 k == S+1이라면, 피봇 값을 반환하라] 라는 내용입니다. 1 = 0 + 1 이므로 참입니다. 즉, 피봇값이 찾던 값이라는 뜻입니다.
따라서 답은 5가 됩니다.