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

Sorting algorithms visualizer

sorting-algorithms.com

Post reply on HN
Print view View original

1–10 of 41 posts

Re: Sorting algorithms visualizer

#2

Post by wgman »

"The ideal sorting algorithm would have the following properties:

- Stable: Equal keys aren't reordered.

- Operates in place, requiring O(1) extra space.

- Worst-case O(n·lg(n)) key comparisons.

- Worst-case O(n) swaps.

- Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.

There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application."

Is there any formal proof that such an algorithm doesn't exist? Are some of those criterion mutually exclusive?

Re: Sorting algorithms visualizer

#3

Post by foota »

This is interesting, I'd never thought about considering the number of swaps that an algorithm does. It seems like low swapping algos should be better in multithreaded environments due to less locking.

Re: Sorting algorithms visualizer

#5

Post by awalGarg »

Shameless-self-plug:

I once wrote a generic algorithm visualizer where you write your own algorithm, and a view function. Then the framework records the state of the algorithm as it changes and passes it to the view function. Then you can play the states like you play a video, go back and forth etc. Here is an example with bubble-sort: http://awal.js.org/alpg/?gist=8b5c6679edc3b85106fb (hit run, then play/rewind/etc.)

The source is available at https://github.com/awalGarg/alpg if anyone feels like dabbling in.

Re: Sorting algorithms visualizer

#6

Post by nightcracker »

wgman wrote: post #2

"The ideal sorting algorithm would have the following properties: - Stable: Equal keys aren't reordered. - Operates in place, requiring O(1) extra space. - Worst-case O(n·lg(n)) key comparisons. - Worst-case O(n) swaps. - Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys. There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on th…

Most of these are possible to combine (see for example https://github.com/BonzaiThePenguin/WikiSort), but I feel that this subset is impossible together:

  - Operates in place, requiring O(1) extra space.  
  - Worst-case O(n·lg(n)) key comparisons.  
  - Worst-case O(n) swaps.
I don't have a formal proof, but I believe one should be possible.

Re: Sorting algorithms visualizer

#7

Post by quantumtremor »

Just for fun: my friend and I 3D printed a model of SelectionSort: https://gfycat.com/HospitableTenderDiamondbackrattlesnake. Each successive layer behind the front one is one iteration of the algorithm. We also made mergesort and quicksort versions, and I'm working on a model of Dijkstra's right now.

To be honest the 3D model doesn't really confer a greater understanding of the algorithm as hoped, but it's nice to play with.

Re: Sorting algorithms visualizer

#9

Post by BlackFingolfin »

This is a really nice page!

It would be even nicer if there was some way to find out who made it and/or how to contact the author(s); and/or how and whether one can add more algorithms (e.g. I'd love to see timsort and introsort).

As it is, this site seems to be completly anonymous. Which is of course a valid choice by the author(s), but IMHO quite sad :-(.

Re: Sorting algorithms visualizer

#10

Post by yakshaving_jgt »

BlackFingolfin wrote: post #9

This is a really nice page! It would be even nicer if there was some way to find out who made it and/or how to contact the author(s); and/or how and whether one can add more algorithms (e.g. I'd love to see timsort and introsort). As it is, this site seems to be completly anonymous. Which is of course a valid choice by the author(s), but IMHO quite sad :-(.

Not completely anonymous.

http://who.is/whois/http://www.sorting-algorithms.com

Post reply on HN