What selection sort normally does:
- Find highest element, swap to first place
- Find next highest element, swap to second place
- ...
- Find second-to-last element, swap to second-to-last place
- Done.
The normal running time is O(N * N), because each of the N steps is a search problem, which is O(N).
You can just stop when you found the first K elements. If you abort it early, it's not N steps any more; but each step is unchanged.
and so the big-O
of the aborted selection sort is thus O(K * N).
Heap sort is done in two steps: heapify and siftdown. Heapify (creating the heap structure) has to be done properly, and it will remain unchanged. Since it's performed in less operations than siftdown, it is omitted from heap sort's big-O.
Siftdown (swapping elements from the heap into a sorted array) is very, very similar to selection sort, but the operation performed in each of N steps to find the next highest element is faster: O(log N).
Since siftdown does pretty much the same thing, conceptually, as the selection sort, you can abort that as well as soon as it has found the top K results.
This means the big-O
of the aborted heap sort is thus O(K * log N).
