평균 선형시간 선택
-
평균 선형시간 선택 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 28. 13:49
평균 선형시간 선택 퀵 정렬의 분할 알고리즘을 이용하여 n 번째 원소를 빠르게 찾아내는 선택 방식이다. 평균 선형시간 선택 알고리즘 분할 알고리즘으로 두 개의 영역으로 나눈 뒤 n 번째 원소가 왼쪽에 포함되면 왼쪽 배열을 아니면 오른쪽 배열을 선택하는 과정을 반복하여 n 번째 원소를 찾는다. 평균 선형시간 선택 알고리즘 Select(A[], p, r, i) { if (p = r) then { return A[p]; } q ← Partition(A, p, r); k ← q - p + 1; if (i < k) then { return Select(A, p, q - 1, i); } else if (i = k) then { return A[q]; } else { return Select(A, q + 1, r, ..