I don't understand. If you were to extract the largest element of the list, you'd make one pass and find it, even if the largest element is at the end. No need to sort the entire array here.
The same with finding the topN. Instead of keeping track of the largest element so far, you keep track of the largest N elements so far. If you do it in a heap, you can add an element, or remove the smallest element in O(log N) time. Still need one pass through the array. Don't have to sort the array. Note that if N equals the size of the list, you perform a sort in O(N log N) time. Which is optimal.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|
