Not signed in (Sign In)

Vanilla 1.1.9 is a product of Lussumo. More Information: Documentation, Community Support.

    • CommentAuthorXyuzhg (Moderator)
    • CommentTimeMar 8th 2015
     
    It seems that I keep on implementing small projects into CI lately.
    Today I've written a small universal Heapsort function. Wikipedia has a pretty useful article (for once!): http://en.wikipedia.org/wiki/Heapsor...
    In short, it's an efficient comparative sorting algorithm.

    What's special is that I wrote the Heapsort function with auxiliary HeapsortCompare function such that you can sort arrays in any way you like. Just change the code in HeapsortCompare, no matter what types you are comparing, and the Heapsort function will still perform. Here's a simple showcase:

    I chose Heapsort because it's the only O(n log n) in-place sorting algorithm I know of. What's nice is that this is also the worst-case time complexity despite taking O(1) space.

    Clean import version:
    -----------------
    Hopefully PA is inconsistent.
    •  
      CommentAuthorMathdude314 (Advanced Member)
    • CommentTimeMar 8th 2015
     
    So... merge sort is not in-place I guess? Because, I thought merge sort took O(n log n) time too.-----------------
    If less people are active, that will only make for even less activity. Start making those designs!
    Currently working on a one-round no-elimination quick RP game...
    • CommentAuthorXyuzhg (Moderator)
    • CommentTimeMar 8th 2015 edited
     
    It is indeed O(n log n), but due to its process of merging, the space complexity is at worst O(n) and requires usually up to n/2 memory to implement.
    But it seems that there are some papers with an improvement that brings its space complexity to O(1): http://citeseerx.ist.psu.edu/viewdoc...

    Right now I'm actually using Wikipedia to see if I can find an algorithm I like better than Heapsort: http://en.wikipedia.org/wiki/Sorting...
    At the moment I'm interested most in Smooth sort, as it seems not too much work to adapt my implementation.-----------------
    Hopefully PA is inconsistent.
    •  
      CommentAuthorTheDudeFromCI (Advanced Member)
    • CommentTimeMar 8th 2015
     
    Wow, Xyuhgz. Thanks, bro. ^^ Once again, another great design. You're awesome.-----------------
    Orange is my favorite number.
    •  
      CommentAuthorMathdude314 (Advanced Member)
    • CommentTimeMar 8th 2015
     
    How can space conplexity by O(1)? You always need at least the length of the array!-----------------
    If less people are active, that will only make for even less activity. Start making those designs!
    Currently working on a one-round no-elimination quick RP game...
    • CommentAuthorXyuzhg (Moderator)
    • CommentTimeMar 8th 2015 edited
     
    That's definitely true. In this respect, all sorting algorithms are truly at least O(n) in space complexity.
    But that's not useful at all when you're trying to compare the memory taken by two sorting algorithms.
    That's why all of the space complexities I'm talking about are actually the auxiliary space complexities, the 'extra' space required by an algorithm.
    This includes any space used e.g. for swapping and merging outside of the original array, which is always going to contribute O(n) complexity.

    One nice way to look at it is that you might not be able to use Mergesort on a massive database at nearly full capacity, while Heapsort will do fine.-----------------
    Hopefully PA is inconsistent.
    • CommentAuthorpuzzle geek (Advanced Member)
    • CommentTimeMar 8th 2015
     
    i dont understand.
    how were the numbers sorted? they looked completely random to me.-----------------
    puzzled
    •  
      CommentAuthorMathdude314 (Advanced Member)
    • CommentTimeMar 8th 2015
     
    Improved:


    It seems like it takes 1/3 of a second, even though it only says 30 ms.-----------------
    If less people are active, that will only make for even less activity. Start making those designs!
    Currently working on a one-round no-elimination quick RP game...
    •  
      CommentAuthorTheDudeFromCI (Advanced Member)
    • CommentTimeMar 8th 2015 edited
     
    @Puzzle Geek
    The top list of numbers were randomly generated. The bottom list of numbers is the top list sorted from smallest to biggest.-----------------
    Orange is my favorite number.