k번째로 작은 값이 무엇인가 구하는 문제.
(모든 숫자를 순서대로 나열하는 알고리즘이 아니다.)
1. 퀵정렬과 똑같이 수행
2. 조건 3가지중에 맞는 것 따라서 계속 진행.
3. 선택. k = S + 1 이라는 조건을 성립하면 return A[p] 즉, 피봇이 된 index. 그 index의 값을 return 하고 종료.
S의 크기는?
ㅡ> k <= S => small group 안에서 몇 번째?
ㅡ> k = S + 1
ㅡ> 나머지 (S+1 < k) Large group 안에서 몇번째?
'📈알고리즘 > 알고리즘' 카테고리의 다른 글
| 그리디 알고리즘(2)[PrimMST(G)] (0) | 2023.04.03 |
|---|---|
| 그리디 알고리즘(1)[KruskalMST 구현(by js)] (0) | 2023.03.30 |
| 퀵정렬 이해하기 (0) | 2023.03.20 |
| 자료구와 알고리즘 학습시작. (0) | 2023.03.16 |
| 병합 정렬[분할 정복 알고리즘 + 재귀 정렬] (0) | 2023.03.15 |