Results 1 to 3 of 3
  1. #1
    merik is offline Member
    Join Date
    Nov 2010
    Posts
    12
    Rep Power
    0

    Default Sorting challenge

    I can sort a list of n items in O(n log n) with quicksort or heapsort easily. I've been challenged that there is a way to get the top Log n elements in O(n). Do you have any idea about how this can be accomplished?

  2. #2
    couling is offline Member
    Join Date
    Nov 2010
    Posts
    54
    Rep Power
    0

    Default

    I'm inclined to believe this is impossible. You must touch at least all n elements once, but you want to keep hold of an expanding number of them (log n). The fact that the number you want to select increases as n increases means you need to add an extra term.

    If you were selecting a fixed constant of rows (eg: top 10) then the complexity could be O(n).



    The best I can come up with appears to have a complexity of O( n log ( log ( n ) ):
    1. Prime a priority queue with the first log ( n ) elements:
    2. For each of the remaining elements:
      1. Add the element to the priority queue
      2. Remove the smallest element from the priority queue
    3. Whatever is left in the priority queue at the end will be the top log(n) elements




    Interestingly you can combine the add and remove operations together for speed, that is to add one and remove one together:
    1. Compare the item to be added with the next to be removed. If the one to be added is smaller then stop.
    2. Replace the one to be removed with the one to be added.
    3. while the added value is larger than one of the values above it: Bubble up the added value (as you would for an empty space in the normal remove algorithm)


    This would give it a best case of O(n), but the worst case would still be O( n log ( log ( n ) ).
    ----Signature ----
    Please use [CODE] tags and indent correctly. It really helps when reading your code.

  3. #3
    merik is offline Member
    Join Date
    Nov 2010
    Posts
    12
    Rep Power
    0

    Default

    Thank you for your great answer. It was very enlightening.

Similar Threads

  1. Challenge!
    By pruttohutto in forum Forum Lobby
    Replies: 2
    Last Post: 04-28-2010, 05:15 PM
  2. Java Challenge [II]
    By [RaIdEn] in forum New To Java
    Replies: 10
    Last Post: 01-21-2010, 04:18 PM
  3. Challenge for jsp developers
    By himacherla in forum JavaServer Pages (JSP) and JSTL
    Replies: 1
    Last Post: 09-27-2009, 03:45 AM
  4. The Million Musician Challenge 0.821
    By levent in forum Java Software
    Replies: 0
    Last Post: 05-25-2007, 08:39 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •