2

Was playing with some Ruby code to re-order pixels of an image and came across a weird effect.

The code below loads up an image, reads the pixels into an array, re-orders the pixels (using Array.sort in an unintended, but apparently valid way) and then creates another image to which it writes out the re-ordered pixels, using the same dimensions from the original image.

According to this: How does Ruby's max function order duplicates? not-stable means the result is unpredictable. However every time I run the code with the same input, I get the same output, so in that sense the result of the sorting in this case is predictable.

What does it mean that the sorting algorithm is not stable and how does it apply in this case?

The code has only been tested on a Mac using: ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-darwin16].

require 'rmagick'

include Magick

img = ImageList.new("images/test-image.jpg")
pixels = img.get_pixels(0,0,img.columns,img.rows)

# https://apidock.com/ruby/Array/sort
# The block must implement a comparison between a and b and
# * <0 when b follows a,
# * 0 when a and b are equivalent, 
# * >0 when a follows b

# The result is not guaranteed to be stable.
# When the comparison of two elements returns 0, the order of the elements is unpredictable.

pixels = pixels.sort {|p| 1 }

out_img = Magick::Image.new(img.columns, img.rows)
out_img.store_pixels(0,0, img.columns, img.rows, pixels)
out_img.write("images/test-image-out.jpg")

Input image: enter image description here

Output image: enter image description here

Also, here's a related question: https://dsp.stackexchange.com/questions/60106/how-would-you-interpret-the-pattern-in-this-picture-generated-by-re-sorting-pi

Nico Brenner
  • 690
  • 7
  • 11
  • 1
    I recommend reading [Sorting algorithm / Stability](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability) I would argue that stability does not apply to your script unless you sorted in three loops, one for each color. – spickermann Aug 15 '19 at 06:25
  • 1
    Stability means that if you have in your original array two different objects `x` and `y`, with `x==y`, and `x` is in the array before `y`, then `x` will be before `y` in the sorted array too. – user1934428 Aug 15 '19 at 07:02
  • 1
    For example, sorting `%w(John Jim Jane Jo Jackie)` by length could end up as `%w(Jo Jim Jane John Jackie)` or `%(Jo Jim John Jane Jackie)`. An unstable algorithm can pick either, since both `Jane` and `John` have the same length (which makes them equal-according-to-length, but not identical), it doesn't matter which goes first. A stable sort would always give you the latter one, since in the original list, `John` was before `Jackie`, and the result should not swap them unnecessarily. When you sort pixels, though, there is no way for two pixels to be equal but not identical. – Amadan Aug 15 '19 at 08:02

1 Answers1

6

Non stability isn’t that the sort will give different results with the same input list. It’s that when you sort an input list by some order, elements that are equivalent according to the order are not guaranteed to be in the same positions relative to each other in the output as the input.

Say, sorting a line of people by increasing integer age. For people of the same age in the line, there isn’t a way to pick who should be first, second etc: they are equivalent. A stable sort’s output would preserve their relative positions as they were in in the input line. Say, Alice and Bob are both 43, and Bob was ahead of Alice in the original line. A stable sort guarantees that Bob would be ahead of Alice in the output line. An unstable sort would not.

The comment of “unpredictable” is slightly misleading. Given enough information about the algorithm, or how it behaved with the same input, it is predictable. However, if all you know is that it’s an unstable sort, it’s not. Specifically, how equivalent elements are sorted is not predictable.

Michal Charemza
  • 25,940
  • 14
  • 98
  • 165
  • 5
    Might be worth noting that you can get stable results from an unstable sorting algorithm by incorporating the items original indices as an additional sorting criteria. – Stefan Aug 15 '19 at 07:29