2JINISHAPPY 2JINISHAPPY

2jinishappy.tistory.com/124 Array의 k번째 작은 element 찾기 - QuickSelect 알고리즘 Size가 n인 int형 Array에서 k번째로 작은 element를 찾는 방법은 여러 가지가 있다. 가장 formal하게, 배열을 sort한 뒤 인덱스가 k인 element를 반환하면 간단하게 구할 수 있다. 우리가 알고있는 Sort 알고 2jinishappy.tistory.com 이전 포스팅에서 배열에서 k번째로 작은 element를 찾아내는 Quick Select 알고리즘을 알아봤다. Quick Select를 진행하면서 선정한 pivot이 너무 작거나 크다면, partitioning이 제대로 이루어지지 않아 Worst-Case에 O(n²)이 소모됨을 확인했다 그렇기 때문에..