Diminishing Gap Sort

August 19, 2016

Today’s exercise comes from my friend Dan:

I don’t have time to think about this now (very busy these days), so I’m just throwing the idea at you. I’m sure there’s some sort of mathematical theorem that relates, but I’m sure you’ll probably know off the top of your head.

I was fascinated not too long ago by the consulting firm we’ve hired to re-vamp our website. I think they were given a tip-off that the color selection for the website theme could be a sticky wicket. So their plan was to pull the colors dynamically from the main picture selected on the home page (and/or departmental pages), which could be changed easily or automatically. They were going to develop something that would pick out the most prominent 6 to 10 colors — even if there wasn’t much contrast (and even black & white photos would supposedly work) — which would be then used for the menus and general color scheme.

Anyway, all this got me thinking about sorting a list of numbers (if these were color codes, there could be lots) such that the greatest gaps would float to the top. I’m sure you get the idea, but I’ll give an example anyway — which I figured out in Excel (below):

Given a number set of 5, 12, 14, 15, 80, 121, 134, 144, 256 the descending-by-highest-difference sort would yield: 256, 80, 121, 134, 144, 12, 14, 15, 5. So in this case, the top 3 biggest gaps would be between 80, 121, and 256.

     Num  Diff              Num  Diff
    ----  ----             ----  ----
     256   112              256   112
     144    10               80    65
     134    13              121    41
     121    41              134    13
      80    65              144    10
      15     1               12     7
      14     2                5     5
      12     7               14     2
       5     5               15     1

I have no idea if this makes sense for the colors thing — it just seemed like the type of problem you frequently do on Programming Praxis.

Hope all is well with you and your family!

-Dan-

Your task is to write a program that sorts a set of points in order by the diminishing gaps between them. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2 3