|
|---|
|
|
|
|
|
|
m*******a
发帖数: 192 | 1 If I have N numbers
and I want to find out the top X of them
and sort the top X from largest to smallest,
what kind of sorting algorithm would you recommend? thanks | f*o
发帖数: 654 | 2 heap sort
【在 m*******a 的大作中提到】
: If I have N numbers
: and I want to find out the top X of them
: and sort the top X from largest to smallest,
: what kind of sorting algorithm would you recommend? thanks
| t*****e
发帖数: 2206 | 3 depends on the relationship between N and X.
N=100000, X=1 or X=99999, different algorithms?
【在 f*o 的大作中提到】
: heap sort
| f*o
发帖数: 654 | 4 and depends on the array sorted or not
hehe
【在 t*****e 的大作中提到】
: depends on the relationship between N and X.
: N=100000, X=1 or X=99999, different algorithms?
| m*******a
发帖数: 192 | 5 suppose N=1000
and X = 32?
thanks
【在 f*o 的大作中提到】
: and depends on the array sorted or not
: hehe
| j**w
发帖数: 382 | 6 Step 1: build a heap at one shot, O(N).
Step 2: Pick the top, which is the largest, O(1).
Step 3: Update the heap, O(logN).
Do Step 1 once, Step 2, X times, Step 3 X times.
Total: O(N) + X*O(logN) = O(N)
PS: Step 1 can be seen here
http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node9.html | j*****s
发帖数: 80 | 7 Depend on the values of N and X, and your requirement on space/time
Assume N is very large, and X is relatively small.
(1) Find the X'th largest number in the list, say, T - using randomized
selection, O(N) time
(2) Go through the list, put numbers larger than T into an array. - O(N)
time, O(X) space.
(3) Sort the array. O(XlogX) time.
Of course, if the original list has many duplicated numbers, it will be a bit more complicated. For example, in step (2), you will probably have an array with size larger than X.
【在 m*******a 的大作中提到】
: If I have N numbers
: and I want to find out the top X of them
: and sort the top X from largest to smallest,
: what kind of sorting algorithm would you recommend? thanks
| k*1
发帖数: 723 | 8 max heap
【在 f*o 的大作中提到】
: heap sort
| j******0
发帖数: 558 | 9 if you are in industry, quick sort is enough.
【在 m*******a 的大作中提到】
: If I have N numbers
: and I want to find out the top X of them
: and sort the top X from largest to smallest,
: what kind of sorting algorithm would you recommend? thanks
|
|
|
|
|
|
|
|
