## Diminishing Gap Sort

### August 19, 2016

Here’s the input:

(define xs (list 80 256 144 5 12 134 15 14 121))

Our objective is to contort the problem to fit as closely as possible the functions in the Standard Prelude:

(define (gaps xs) (let ((ys (append (cdr xs) (list 0)))) (zip (map - xs ys) xs)))

Function `gaps`

returns a list of pairs with the input number in the `cdr`

and the gap to the next smallest number in the `car`

:

> (gaps xs) ((112 256) (10 144) (13 134) (41 121) (65 80) (1 15) (2 14) (7 12) (5 5))

Function `car>`

compares two lists on their `car`

s, which is where we have stored the gaps:

(define (car> xs ys) (> (car xs) (car ys)))

The function `diminishing-gap-sort`

assembles the pieces:

(define (diminishing-gap-sort xs) (map cadr (sort car> (gaps (sort > xs)))))

And here’s the output:

> (diminishing-gap-sort xs) (256 80 121 134 144 12 5 14 15)

A simple solution to a silly little problem. You can see the contributions from the Standard Prelude and run the program at http://ideone.com/rTBgP1.

Advertisements

Ok, Phil. We had a major VMWare outage this afternoon that impacted a bunch of stuff, so I was C-drive-bound for a while (plus your email shamed me into writing this). When I was finally able to connect to our databases, we still had no shared drives and the application servers were mostly out to lunch. So I decided to see if I could implement the color-sort idea, with red/green/blue values – 3 values instead of just one. I sorted by red/green/blue, but I needed to get the absolute values of the aggregated gaps, since the sort yielded green and blue values going up and down. (I don’t know if that sort makes sense color-wise, but it seems logical to me.) I also took a minute to research the “Gnome sort” – or “Stupid sort”, which sounded like something made for me! So that’s what I implemented here (I can’t remember the last time I actually coded a sort algorithm!). Oracle PL/SQL code and output pasted below, which I hope is formatted so it’s readable. Like when we worked together, I fully expect you to find a bug or recommend an improvement! Take care, Phil.

Well, that turned out to be a bit more fun than I expected! Your straight-SQL solution is (as usual) both elegant and straight-forward. Here’s my output (I always like to see the starting point, interim state, and final results!):

In D…probably not suitable for large arrays due to Bubble Sort

Output:

Num: [5, 12, 14, 15, 80, 121, 134, 144, 256]

Diff: [5, 7, 2, 1, 65, 41, 13, 10, 112]

Num: [256, 80, 121, 134, 144, 12, 5, 14, 15]

Diff: [112, 65, 41, 13, 10, 7, 5, 2, 1]

Written in Common Lisp

This is my first public answer to a question. Fingers crossed I did good :D

http://paste.lisp.org/display/323870

It didn’t post the link…sorry.

In Python.

A solution in Racket.

> “They were going to develop something that would pick out the most prominent 6 to 10 colors…”

One approach to that problem is to use a clustering algorithm on points of RGB values. For example:

http://charlesleifer.com/blog/using-python-and-k-means-to-find-the-dominant-colors-in-images/

Back to the problem…

Here’s a solution in matlab.

Output: