## 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.

Pages: 1 2 3

### 8 Responses to “Diminishing Gap Sort”

1. -Dan- said

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.

```declare
type val_rec is record (
red     number(3),
green   number(3),
blue    number(3),
gap     number(6));
type tblnum_type is table of val_rec index by pls_integer;
tbl    tblnum_type;
rectmp val_rec;
pos    pls_integer;
diff   pls_integer;

procedure prttbl(hdg in varchar2) is
begin
dbms_output.put_line(chr(10)||'*** '||hdg);
dbms_output.put_line('red green  blue   gap');
dbms_output.put_line('--- -----  ----   ---');
for i in 1..tbl.count loop
dbms_output.put_line(
to_char(tbl(i).red,'fm000')||
'   '||to_char(tbl(i).green,'fm000')||
'   '||to_char(tbl(i).blue,'fm000')||
'   '||to_char(tbl(i).gap,'fm000'));
end loop;
end prttbl;

begin
dbms_output.enable(1000000);

-- randomly generate colors
for i in 1..10 loop
tbl(tbl.count+1).red := trunc(dbms_random.value(0, 256));
tbl(tbl.count).green := trunc(dbms_random.value(0, 256));
tbl(tbl.count).blue  := trunc(dbms_random.value(0, 256));
tbl(tbl.count).gap   := 0;
end loop;
-- seed bottom value (assume black always included)
tbl(tbl.count+1).red := 0;
tbl(tbl.count).green := 0;
tbl(tbl.count).blue  := 0;
tbl(tbl.count).gap   := 0;
prttbl('initial state');

-- sort by red, green, blue
pos := 1;
loop
exit when pos >= tbl.count;
if pos = 1 or (to_char(tbl(pos-1).red,'fm000')||to_char(tbl(pos-1).green,'fm000')||to_char(tbl(pos-1).blue,'fm000') >=
to_char(tbl(pos).red,'fm000')||to_char(tbl(pos).green,'fm000')||to_char(tbl(pos).blue,'fm000')) then
pos := pos+1;
else
rectmp := tbl(pos);
tbl(pos) := tbl(pos-1);
tbl(pos-1) := rectmp;
pos := pos-1;
end if;
end loop;

-- calculate gaps
for i in 1..tbl.count-1 loop
tbl(i).gap := (abs(tbl(i).red-tbl(i+1).red) + abs(tbl(i).green-tbl(i+1).green) + abs(tbl(i).blue-tbl(i+1).blue));
end loop;
prttbl('sorted by red, green, blue with gaps calculated');

-- diminishing gap sort
pos := 1;
loop
exit when pos >= tbl.count;
if pos = 1 or tbl(pos-1).gap >= tbl(pos).gap then
pos := pos+1;
else
rectmp := tbl(pos);
tbl(pos) := tbl(pos-1);
tbl(pos-1) := rectmp;
pos := pos-1;
end if;
end loop;
prttbl('sorted by gap');
end;
```

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!):

```*** initial state
red green  blue   gap
--- -----  ----   ---
153   251   231   000
049   117   172   000
041   202   192   000
226   189   051   000
122   044   103   000
217   239   017   000
052   149   102   000
011   072   196   000
140   151   070   000
105   243   027   000
000   000   000   000

*** sorted by red, green, blue with gaps calculated
red green  blue   gap
--- -----  ----   ---
226   189   051   093
217   239   017   290
153   251   231   274
140   151   070   158
122   044   103   292
105   243   027   222
052   149   102   105
049   117   172   113
041   202   192   164
011   072   196   279
000   000   000   000

*** sorted by gap
red green  blue   gap
--- -----  ----   ---
122   044   103   292
217   239   017   290
011   072   196   279
153   251   231   274
105   243   027   222
041   202   192   164
140   151   070   158
049   117   172   113
052   149   102   105
226   189   051   093
000   000   000   000
```
2. Rainer said
```with data (n) as (values
(256),(144),(134),(121),(80),(15),(14),(12),(5)),
neighbour (n,next) as
(select d.n, coalesce((select max(x.n)
from   data x
where  x.n < d.n), 0) as nxt
from   data d)
select n,n - next as diff
from   neighbour
order  by diff desc

==>

N            DIFF
256             112
80              65
121              41
134              13
144              10
12               7
5               5
14               2
15               1
```
3. Milbrae said

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

```import std.algorithm;
import std.stdio;

void main()
{
uint i, len;

/* create arrays, sort, and get diffs */
uint[] num = [5, 12, 14, 15, 80, 121, 134, 144, 256];
num.sort();
len = cast(uint)num.length;

uint[] diff = new uint[](num.length);
diff[0] = num[0];
for (i = 1; i < len; i++) {
diff[i] = num[i] - num[i-1];
}

writefln("Num:  %s", num);
writefln("Diff: %s", diff);
writeln;

/* slow bubble sort of both arrays in parallel */
bool sorted;
do {
sorted = true;
for (i = 0; i < len-1; i++) {
if (diff[i] < diff[i+1]) {
swap(diff[i], diff[i+1]);
swap(num[i], num[i+1]);
sorted = false;
}
}
} while (!sorted);

writefln("Num:  %s", num);
writefln("Diff: %s", diff);
}
```

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]

4. Josh said

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

5. Josh said

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

6. Paul said

In Python.

```from util.itert import pairwise  # from itertools doc
from operator import itemgetter

def dgs(seq):
gaps = [(a, a - b) for a, b in pairwise(sorted(seq, reverse=True) + [0])]
return sorted(gaps, key=itemgetter(1), reverse=True)
```
7. r. clayton said

A solution in Racket.

8. Daniel said

> “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.

```l = [5, 12, 14, 15, 80, 121, 134, 144, 256];
sorted = sort([l, 0]);
[~,I] = sort(diff(sorted), 'descend');
l(I)
```

Output:

```>> diminishing_gap_sort

ans =

256    80   121   134   144    12     5    14    15
```