Show HN: Write a sort, watch it go • Hacker News Board

Re: Show HN: Write a sort, watch it go

#31

Post by thedufer » Mon, Sep 26, 2011, 8:55 PM UTC

kingkilr wrote: post #27

akavi wrote: post #15

>Nothing will display if there is an infinite loop. Did someone solve the halting problem while I wasn't looking?

I assume it just computes every step, and then displays them all.

This is exactly what's going on. You can't get a reflow on the page without giving up control, and I didn't want to require people to write asynchronous code to give up control after every swap. So it runs your code and queues up actions, to be played back when its done. This is also why you have to use the methods on VA instead of working directly on the array.

Re: Show HN: Write a sort, watch it go

#32

Post by thedufer » Mon, Sep 26, 2011, 8:56 PM UTC

ilikejam wrote: post #11

Needs a shuffle() function - can't bogosort without it.

You should be able to write one with swaps - go for it.

Re: Show HN: Write a sort, watch it go

#33

Post by cpeterso » Mon, Sep 26, 2011, 9:15 PM UTC

Wikipedia has similar animations for some of its articles about sorting algorithms, e.g.:

https://secure.wikimedia.org/wikipedia/en/wiki/Quicksort

Re: Show HN: Write a sort, watch it go

#34

Post by thedufer » Mon, Sep 26, 2011, 9:18 PM UTC

HardyLeung wrote: post #18

The quicksort implementation is incorrect. The code simply picking the left-most element as the pivot, and as a result it becomes pathologically slow for nearly-sorted array -- for example, run bubblesort then quicksort, or run quicksort twice -- not to mention potential stack overflow problem due to O(N) recursive call.

I said this in another comment, but I coded up the simplest version of each algorithm - the quicksort is correct, just not optimal. The focus was on letting people write their own code, not the pre-written algorithms.

Re: Show HN: Write a sort, watch it go

#35

Post by SeoxyS » Mon, Sep 26, 2011, 9:19 PM UTC

Had fun writing a gnome-sort in a minute or two:

    pos = 1
    while pos  1)
          pos--
        else
          pos++

Re: Show HN: Write a sort, watch it go

#36

Post by ginkgo » Mon, Sep 26, 2011, 9:20 PM UTC

The input set is problematic because it contains every number from 0 to VA.length exactly once.

This allows "algorithms" like this:

  for x in [0...VA.length]
    while (VA.get(x) > x)
      VA.swap(VA.get(x), x)

Re: Show HN: Write a sort, watch it go

#37

Post by DrHankPym » Mon, Sep 26, 2011, 9:20 PM UTC

This might be a dumb question, but can you add numbers about the size of the stack to the right-side statistics? I.e. How many variables and calls to functions are stored in memory at at a time.

I'm not sure if this possible or relevant to record based on how Javascript engines compile and work, but it would seem interesting to know.

Re: Show HN: Write a sort, watch it go

#38

Post by thedufer » Mon, Sep 26, 2011, 9:28 PM UTC

ginkgo wrote: post #36

The input set is problematic because it contains every number from 0 to VA.length exactly once. This allows "algorithms" like this: for x in [0...VA.length] while (VA.get(x) > x) VA.swap(VA.get(x), x)

Its not a game; its a learning tool. It doesn't bother me that people can do that.

Also, that's not going to work quite right - the values are [1..VA.length] (see the bottom of the page), while the indices are [0...VA.length].

Re: Show HN: Write a sort, watch it go

#39

Post by CountHackulus » Mon, Sep 26, 2011, 9:32 PM UTC

How about adding the VA.equals and VA.notequals functions? You've got all the other comparators, but it seems a shame that you don't have these.

Re: Show HN: Write a sort, watch it go

#40

Post by leif » Mon, Sep 26, 2011, 9:43 PM UTC

cschneid wrote: post #22

HardyLeung wrote: post #18

The quicksort implementation is incorrect. The code simply picking the left-most element as the pivot, and as a result it becomes pathologically slow for nearly-sorted array -- for example, run bubblesort then quicksort, or run quicksort twice -- not to mention potential stack overflow problem due to O(N) recursive call.

That's still a quicksort - it always has n^2 as its worst case I thought? If you pick the wrong pivot each time.

There are ways to make the n^2 worst case extraordinarily unlikely, and there is a way to make it impossible (though it is highly technical).

Some others have posted methods (random pivot, median of 3). The gnu libc qsort implementation is a good learning tool (it uses median of 3). I think CLRS has the guaranteed n log n version.