Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Write a sort, watch it go

visualsort.appspot.com

Post reply on HN
Print view View original

61–70 of 89 posts

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

#61

Post by thedufer »

eridius wrote: post #45

Very neat, but here's a couple of additions I'd like to see: 1. Allow for the array to contain values outside of the range of [1..length]. Ideally, allow for duplicate values as well. Since you control the swap and insert operations, you can maintain two separate sets, one of the actual numbers, and one of the "normalized" values that you display as your graph. 2. Give us an operation to highlight a set of lines and…

1. Requires a bit more work than I have time for right now. I'll keep it in mind.

2. Fantastic idea. This is exactly what I needed when I was struggling to write a quicksort from memory. Its in there now.

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

#62

Post by thedufer »

scotty79 wrote: post #56
scotty79 wrote: post #50

Yay. My first program in CoffeScript. It was fun to implement algorithm of which I only vaguely remembered how it worked. Details bit me few times before I got it working and right. Heapsort: fix_heap = (y, size) -> loop y1 = 2*y+1 y2 = 2*y+2 if y1 >= size then break if !(y2 loop y0 = (y-1) >> 1 if y == 0 || VA.lt(y, y0) then break VA.swap(y0, y) y = y0 for x in [1 ... VA.length] pull_up(x) for x in [VA.length-1 ...…

You can also build the heap from the bottom up and change fix_heap a little which altogether is faster and simpler (thanks wiki): fix_heap = (y, size) -> loop y1 = 2*y+1 if y1 >= size then break if y1 + 1 > 1 ... -1] by -1 fix_heap(x, VA.length) for x in [VA.length-1 ... 0] by -1 VA.swap(x, 0) fix_heap(0, x)

I put this implementation in as a prewritten sort. Thanks!

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

#66

Post by thedufer »

pbiggar wrote: post #57

I love the stats on the side. Knowing how many comparisons and swaps occur really shows the complexity of the algorithms. And to segue into my own area of interest with sorting, it would be awesome to see cache and branch behaviour too (though of course this running in the browser, it's not exactly the real behaviour, but still).

How would you expect such things to be calculated? Not sure exactly what you're looking for.

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

#68

Post by dhathorn »

Cocktail sort

  twoWayBubbleSort = ->
    VA.locals.swapped = true
    while VA.locals.swapped
      VA.locals.swapped = false
      for x in [0...VA.length - 1]
        VA.locals.x = x
        if VA.gt(x, x + 1)
          VA.swap(x, x + 1)
          VA.locals.swapped = true
      for x in[(VA.length-1)..1]
        VA.locals.x = x
        if VA.gt(x - 1, x)
          VA.swap(x - 1, x)
          VA.locals.swapped = true


  twoWayBubbleSort()

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

#69

Post by snow_mac »

robinhouston wrote: post #46

Sleep sort: pos = [0 ... VA.length] rpos = [0 ... VA.length] swap = (i, j) -> VA.swap i, j tmp = rpos[j]; rpos[j] = rpos[i]; rpos[i] = tmp pos[rpos[i]] = i; pos[rpos[j]] = j j = 0 for i in [0 ... VA.length] v = VA.get(i) do (v, i) -> setTimeout -> # Move the element that was originally in position i to position j swap pos[i], j++ VA.play() , 100 * v

Never heard of this one. It's awesome.
Post reply on HN