11 ms·

Sorting Algorithms Revisualized

281 points by mdturnerphys 9y ago

mrguyorama 9y ago
The problem with colorblindness is a common one. I saw the post in question and it was just a typical rainbow color scheme, and it never even occurred to me that they might cause trouble for color blind users. Is it possible to map the RGB colorspace onto a colorblindness safe colorspace? This would be a cool feature that I feel Web Browsers could provide to be more accessible for their users
- BugsJustFindMe 9y ago
  > Is it possible to map the RGB colorspace onto a colorblindness safe colorspace? Multiple variant options are built into Android. Even color blindness aside, the rainbow color map is bad because of the relative overrepresentation of green among other things. See https://www.research.ibm.com/people/l/lloydt/color/color.HTM https://www.research.ibm.com/people/l/lloydt/color/color.HTM
  - akx 9y ago
    If you're referring to what I think you're referring to, those are just emulations for development use, i.e. you can use them to figure out if your app is accessible for people with those colorblindnesses.
- alanbernstein 9y ago
  > Is it possible to map the RGB colorspace onto a colorblindness safe colorspace? Sure, grayscale is safe. I don't think it's possible without losing some information.
  - mcgarnagle 9y ago
    Sorry, why not just gradient from white to black?
    - gatmne 9y ago
      Because colors with components that result in the same intensity will be identical. Think a shade of red and a shade of blue that wined up the same shad of gray. The fact that both were distinct colors is lost. By limiting the transformed colors to those a person is blind to, you limit the amount of information loss. I think the ideal place to tackle this issue is as near to the display as possible. A screen purpose-built for the color-blind would be best, but redshift-esque software would do the job just as well.
- kzrdude 9y ago
  You might find this interesting, the story about the new default colormap in matplotlib 2.0 It's about more than colorblindness -- about how represent a steady linear scale with color and how to keep it faithful in grayscale. http://medvis.org/2016/02/23/better-than-the-rainbow-the-matplotlib-alternative-colormaps/ http://medvis.org/2016/02/23/better-than-the-rainbow-the-mat...
- vanderZwan 9y ago
  There is the cube-helix approach, but I suspect you're thinking about something else. The linked talk about the creation of the viridis colour map[0] actually spends a good ten minutes on explaining colour theory, and makes it look very simple in the process. About ten minutes in it shows the "perceptual colour space" of a typical non-colourblind person. A few minutes later it shows the color spaces for people with various types of colourblindness. Perhaps one could project one perceptual space into the other in a way that more-or-less preserves the original information, but essentially with more banding? [0] https://www.youtube.com/watch?v=xAoljeRJ3lU https://www.youtube.com/watch?v=xAoljeRJ3lU
  - itronitron 9y ago
    +1 for cubehelix... https://www.mrao.cam.ac.uk/~dag/CUBEHELIX/ https://www.mrao.cam.ac.uk/~dag/CUBEHELIX/
- aw3c2 9y ago
  Try https://github.com/gmculp/OGA_recolor https://github.com/gmculp/OGA_recolor
- gsich 9y ago
  Not really. Colorblindness affects 0.001% of the population. (but that's wikipedia)
  - em3rgent0rdr 9y ago
    Although I also imagine with all the new electronic-ink monitors, there might be a larger need for grayscale-compatible colors. Also regular grey-scale printing.
  - Franciscouzo 9y ago
    From wikipedia: "Red–green color blindness affects up to 8% of males and 0.5% of females of Northern European descent." That's around 4% of the population, not 0.001%.
    - mrleiter 9y ago
      Well, those 4% hold true if there is an equal amount of males and females of Northern European decent. But yeah, should be aroune 4%.
    - gsich 9y ago
      That's red-green color deficiency, not "colorblindness" as in "I only see grayscale". The english wikipedia says it's about 0.025% of the population [0]. So I'll take that instead of the german one. [0] https://en.wikipedia.org/wiki/Achromatopsia https://en.wikipedia.org/wiki/Achromatopsia
      - fao_ 9y ago
        > That's red-green color deficiency, not "colorblindness" from The Free Dictionary: "Noun. 'color blindness' - genetic inability to distinguish differences in hue" and from https://en.wikipedia.org/wiki/Color_blindness https://en.wikipedia.org/wiki/Color_blindness "Color blindness, also known as color vision deficiency, is the decreased ability to see color or differences in color.[2] [...] Red–green color blindness is the most common form, followed by blue–yellow color blindness and total color blindness.[2] Red–green color blindness affects up to 8% of males and 0.5% of females of Northern European descent.[2]" Your very specific definition of colour blindness (i.e. 'colour blindness' = 'Achromatopsia') does not seem to be represented in the colloquial usage. Thus the parent of you is correct.
vanderZwan 9y ago
I have protanomally and saw the original post, and I didn't even think about the rainbow map. It was very informative still. However, the pixels are so much easier to follow in the new version! Guess I am so used to being "deprived" of full information that I didn't even realise what I was missing!
minimaxir 9y ago
Here’s a good writeup on the benefits of using the viridis palettes for data visualization, using examples in R: https://cran.r-project.org/web/packages/viridis/vignettes/intro-to-viridis.html https://cran.r-project.org/web/packages/viridis/vignettes/in...
em3rgent0rdr 9y ago
Wouldn't the gif for Bogosort be humongous, because it has to try all possible permutations? Maybe this article is just using random noise gif instead for size concerns.
- anyfoo 9y ago
  Bogosorting an array of the given size would take much longer than the lifetime of our sun. You think the author might not have given us the full gif depicting that sort? I don't know!
  - em3rgent0rdr 9y ago
    right, that is my point! I made my comment because I feel the author was being misleading about just how much a "long time" and by falsely suggesting that the animation he put up for it was real and not just random noise.
    - anyfoo 9y ago
      I feel like he made a joke.
- SeanDav 9y ago
  > "This is a very important sorting algorithm, though it takes a long time to sort this data." The author is clearly being tongue-in-cheek here and making a bit of a joke!
em3rgent0rdr 9y ago
Would be nice to see a visualization that took into account real computer performance concerns such as caching, branch prediction, and instruction-level parallelism.
josh_blum 9y ago
Really cool! Is the code available publicly?
- Franciscouzo 9y ago
  It's not OP's, but I made a this [0], and the code is available here [1] [0] https://franciscouzo.github.io/sort/ https://franciscouzo.github.io/sort/ [1] https://github.com/franciscouzo/franciscouzo.github.io/tree/master/sort https://github.com/franciscouzo/franciscouzo.github.io/tree/...
  - josh_blum 9y ago
    Thank you!
mordechai9000 9y ago
This brings back something I had all but forgotten. The first ever assembly language program I got to run was a bubble sort implementation that sorted the text characters on the screen. I painstakingly typed it in from a book on 6809 assembly language programming. I didn't know what it was going to do, so I was blown away when I saw how it could actually manipulate and sort characters in video memory right before my eyes.
Edmond 9y ago
try: http://schoolnotez.com/ http://schoolnotez.com/ click on the computer science page to see the various sorting algos.
Sharlin 9y ago
Ahh, this is so much better. I'm red-green colorblind but I'd have thought that using the "rainbow" color wheel gradient wasn't very intuitive to people with normal color vision either. Given two hues it isn't intuitively obvious which hue is "greater" (as is evident from the fact that people have to memorize the order of the colors in a rainbow), plus the scale wraps around perceptually (as the term "color wheel" implies) so it isn't even a proper total order.
fastball 9y ago
Why is imgur so magnified on my desktop? It's horrible. I can't even see an entire gif at one time on my screen.
caspervonb 9y ago
Neat, made my own a few weeks back, It's in JavaScript tho so can't deal with huge datasets, oh and there's sound. - https://caspervonb.github.io/toneofsorting/ https://caspervonb.github.io/toneofsorting/ :-}
avyfain 9y ago
Every time something like this comes up, I think of Mike Bostocks wonderful Visualizing Algorithms[0]. The essay is not comprehensive, but shows more than just sorting. It also deals with sampling, and with maze generation. Truly worth your time. [0]: https://bost.ocks.org/mike/algorithms/ https://bost.ocks.org/mike/algorithms/
CyberDildonics 9y ago
One thing to remember with these is that they don't show the speed of the sorting algorithms because the movement of numbers is animated. If they are written further away, the square of that color travels further, which takes time.

281 points by mdturnerphys 9y ago

The problem with colorblindness is a common one. I saw the post in question and it was just a typical rainbow color scheme, and it never even occurred to me that they might cause trouble for color blind users. Is it possible to map the RGB colorspace onto a colorblindness safe colorspace? This would be a cool feature that I feel Web Browsers could provide to be more accessible for their users

BugsJustFindMe 9y ago
> Is it possible to map the RGB colorspace onto a colorblindness safe colorspace? Multiple variant options are built into Android. Even color blindness aside, the rainbow color map is bad because of the relative overrepresentation of green among other things. See https://www.research.ibm.com/people/l/lloydt/color/color.HTM https://www.research.ibm.com/people/l/lloydt/color/color.HTM
- akx 9y ago
  If you're referring to what I think you're referring to, those are just emulations for development use, i.e. you can use them to figure out if your app is accessible for people with those colorblindnesses.
alanbernstein 9y ago
> Is it possible to map the RGB colorspace onto a colorblindness safe colorspace? Sure, grayscale is safe. I don't think it's possible without losing some information.
- mcgarnagle 9y ago
  Sorry, why not just gradient from white to black?
  - gatmne 9y ago
    Because colors with components that result in the same intensity will be identical. Think a shade of red and a shade of blue that wined up the same shad of gray. The fact that both were distinct colors is lost. By limiting the transformed colors to those a person is blind to, you limit the amount of information loss. I think the ideal place to tackle this issue is as near to the display as possible. A screen purpose-built for the color-blind would be best, but redshift-esque software would do the job just as well.
kzrdude 9y ago
You might find this interesting, the story about the new default colormap in matplotlib 2.0 It's about more than colorblindness -- about how represent a steady linear scale with color and how to keep it faithful in grayscale. http://medvis.org/2016/02/23/better-than-the-rainbow-the-matplotlib-alternative-colormaps/ http://medvis.org/2016/02/23/better-than-the-rainbow-the-mat...
vanderZwan 9y ago
There is the cube-helix approach, but I suspect you're thinking about something else. The linked talk about the creation of the viridis colour map[0] actually spends a good ten minutes on explaining colour theory, and makes it look very simple in the process. About ten minutes in it shows the "perceptual colour space" of a typical non-colourblind person. A few minutes later it shows the color spaces for people with various types of colourblindness. Perhaps one could project one perceptual space into the other in a way that more-or-less preserves the original information, but essentially with more banding? [0] https://www.youtube.com/watch?v=xAoljeRJ3lU https://www.youtube.com/watch?v=xAoljeRJ3lU
- itronitron 9y ago
  +1 for cubehelix... https://www.mrao.cam.ac.uk/~dag/CUBEHELIX/ https://www.mrao.cam.ac.uk/~dag/CUBEHELIX/
aw3c2 9y ago
Try https://github.com/gmculp/OGA_recolor https://github.com/gmculp/OGA_recolor
gsich 9y ago
Not really. Colorblindness affects 0.001% of the population. (but that's wikipedia)
- em3rgent0rdr 9y ago
  Although I also imagine with all the new electronic-ink monitors, there might be a larger need for grayscale-compatible colors. Also regular grey-scale printing.
- Franciscouzo 9y ago
  From wikipedia: "Red–green color blindness affects up to 8% of males and 0.5% of females of Northern European descent." That's around 4% of the population, not 0.001%.
  - mrleiter 9y ago
    Well, those 4% hold true if there is an equal amount of males and females of Northern European decent. But yeah, should be aroune 4%.
  - gsich 9y ago
    That's red-green color deficiency, not "colorblindness" as in "I only see grayscale". The english wikipedia says it's about 0.025% of the population [0]. So I'll take that instead of the german one. [0] https://en.wikipedia.org/wiki/Achromatopsia https://en.wikipedia.org/wiki/Achromatopsia
    - fao_ 9y ago
      > That's red-green color deficiency, not "colorblindness" from The Free Dictionary: "Noun. 'color blindness' - genetic inability to distinguish differences in hue" and from https://en.wikipedia.org/wiki/Color_blindness https://en.wikipedia.org/wiki/Color_blindness "Color blindness, also known as color vision deficiency, is the decreased ability to see color or differences in color.[2] [...] Red–green color blindness is the most common form, followed by blue–yellow color blindness and total color blindness.[2] Red–green color blindness affects up to 8% of males and 0.5% of females of Northern European descent.[2]" Your very specific definition of colour blindness (i.e. 'colour blindness' = 'Achromatopsia') does not seem to be represented in the colloquial usage. Thus the parent of you is correct.

vanderZwan 9y ago

I have protanomally and saw the original post, and I didn't even think about the rainbow map. It was very informative still. However, the pixels are so much easier to follow in the new version! Guess I am so used to being "deprived" of full information that I didn't even realise what I was missing!

minimaxir 9y ago

Here’s a good writeup on the benefits of using the viridis palettes for data visualization, using examples in R: https://cran.r-project.org/web/packages/viridis/vignettes/intro-to-viridis.html https://cran.r-project.org/web/packages/viridis/vignettes/in...

em3rgent0rdr 9y ago

Wouldn't the gif for Bogosort be humongous, because it has to try all possible permutations? Maybe this article is just using random noise gif instead for size concerns.

anyfoo 9y ago
Bogosorting an array of the given size would take much longer than the lifetime of our sun. You think the author might not have given us the full gif depicting that sort? I don't know!
- em3rgent0rdr 9y ago
  right, that is my point! I made my comment because I feel the author was being misleading about just how much a "long time" and by falsely suggesting that the animation he put up for it was real and not just random noise.
  - anyfoo 9y ago
    I feel like he made a joke.
SeanDav 9y ago
> "This is a very important sorting algorithm, though it takes a long time to sort this data." The author is clearly being tongue-in-cheek here and making a bit of a joke!

em3rgent0rdr 9y ago

Would be nice to see a visualization that took into account real computer performance concerns such as caching, branch prediction, and instruction-level parallelism.

josh_blum 9y ago

Really cool! Is the code available publicly?

Franciscouzo 9y ago
It's not OP's, but I made a this [0], and the code is available here [1] [0] https://franciscouzo.github.io/sort/ https://franciscouzo.github.io/sort/ [1] https://github.com/franciscouzo/franciscouzo.github.io/tree/master/sort https://github.com/franciscouzo/franciscouzo.github.io/tree/...
- josh_blum 9y ago
  Thank you!

mordechai9000 9y ago

This brings back something I had all but forgotten. The first ever assembly language program I got to run was a bubble sort implementation that sorted the text characters on the screen. I painstakingly typed it in from a book on 6809 assembly language programming. I didn't know what it was going to do, so I was blown away when I saw how it could actually manipulate and sort characters in video memory right before my eyes.

Edmond 9y ago

try: http://schoolnotez.com/ http://schoolnotez.com/ click on the computer science page to see the various sorting algos.

Sharlin 9y ago

Ahh, this is so much better. I'm red-green colorblind but I'd have thought that using the "rainbow" color wheel gradient wasn't very intuitive to people with normal color vision either. Given two hues it isn't intuitively obvious which hue is "greater" (as is evident from the fact that people have to memorize the order of the colors in a rainbow), plus the scale wraps around perceptually (as the term "color wheel" implies) so it isn't even a proper total order.

fastball 9y ago

Why is imgur so magnified on my desktop? It's horrible. I can't even see an entire gif at one time on my screen.

caspervonb 9y ago

Neat, made my own a few weeks back, It's in JavaScript tho so can't deal with huge datasets, oh and there's sound. - https://caspervonb.github.io/toneofsorting/ https://caspervonb.github.io/toneofsorting/ :-}

avyfain 9y ago

Every time something like this comes up, I think of Mike Bostocks wonderful Visualizing Algorithms[0]. The essay is not comprehensive, but shows more than just sorting. It also deals with sampling, and with maze generation. Truly worth your time. [0]: https://bost.ocks.org/mike/algorithms/ https://bost.ocks.org/mike/algorithms/

CyberDildonics 9y ago

One thing to remember with these is that they don't show the speed of the sorting algorithms because the movement of numbers is animated. If they are written further away, the square of that color travels further, which takes time.