정의

퀵셀렉트는 정렬되지 않은 배열에서 'k번째로 작은 값'을 찾는 알고리즘입니다. 퀵정렬처럼 피벗을 기준으로 배열을 분할하지만, 분할 후 답이 들어 있는 한쪽 범위만 계속 좁혀가므로 정렬보다 빠릅니다.

핵심 특성

• ✓전체를 정렬하지 않음 - 답이 있는 한쪽만 재귀(반복)하여 평균 O(n)
• ✓Lomuto 분할 사용 - 맨 끝 원소를 피벗으로 고르고 작은 값을 앞으로 모음
• ✓분할 후 피벗 위치 p와 k-1을 비교해 왼쪽/오른쪽 중 한쪽만 진행
• ✓제자리(in-place) - 추가 배열 없이 O(1) 공간만 사용
• ✓최악 O(n²)이지만 평균 O(n) - 정렬 후 인덱싱(O(n log n))보다 빠름

시간 복잡도