퀵셀렉트 k번째 원소 계산기

평균 O(n)으로, 정렬의 O(n log n)보다 한 단계 빠릅니다. 퀵정렬과 분할까지는 똑같지만 양쪽을 모두 정렬하지 않고 k가 있는 한쪽만 따라 내려가기 때문입니다. 매번 절반씩 줄어든다고 치면 훑는 양이 n + n/2 + n/4 + … = 2n이 되고, 정렬은 층마다 전부를 다시 훑어야 해서 층이 log n개 쌓입니다.

최악의 경우 O(n²)입니다. 이미 정렬된 배열에 「첫 원소」 피벗 규칙을 쓰면 피벗이 매번 남은 구간에서 가장 작은 값이라 한쪽이 텅 비고 다른 쪽이 하나씩만 줄어, 비교 횟수가 n(n−1)/2에 이릅니다. 이 계산기의 「최악」 예제에서 그 숫자를 직접 볼 수 있습니다.

실제 구현은 무작위로 고릅니다. 어떤 입력이 오더라도 최악의 경우에 걸릴 확률을 낮출 수 있기 때문입니다. 이 계산기는 같은 입력에 같은 과정이 나와야 해서 첫 원소·가운데 원소·세 값의 중앙값 세 가지로 고정했습니다. 세 값의 중앙값은 실전에서 흔히 쓰는 절충안으로, 정렬된 입력에서도 무너지지 않습니다.

쓸 수 있습니다. 원소가 n개일 때 k를 ⌈n/2⌉로 두면 중앙값이 나옵니다. 짝수 개라면 n/2번째와 n/2+1번째를 각각 찾아 평균을 내면 됩니다. 전체를 정렬해서 가운데를 꺼내는 것보다 평균적으로 빠른 것이 이 알고리즘을 쓰는 가장 흔한 이유입니다.

로무토(Lomuto) 분할입니다. 피벗을 구간 맨 뒤로 보내 놓고 왼쪽부터 훑으며 피벗보다 작은 값을 앞으로 모은 뒤, 마지막에 피벗을 그 경계로 되돌립니다. 호어(Hoare) 분할보다 교환이 잦지만 「지금 어디까지 모았는가」가 한눈에 보여 과정을 따라가기에 낫습니다. 비교 횟수는 구간 길이가 m일 때 정확히 m−1번입니다.

됩니다. k번째로 작은 값은 중복을 따로 세지 않고 「정렬했을 때 k번째 자리에 오는 값」으로 정의합니다. 예를 들어 3, 3, 1에서 2번째로 작은 수는 3입니다. 다만 중복이 아주 많으면 로무토 분할에서 한쪽으로 몰려 단계가 늘어날 수 있습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.