Diminishing Gap Sort
August 19, 2016
Dan and I met as programmers supporting an ERP system written in Oracle. Dan and I have both moved to new employers since then, but both of us still work on the same ERP. Since we both program databases, I decided to write my solution in SQL:
$ sqlplus username@sid/password
SQL*Plus: Release 11.2.0.3.0 Production on Thu Aug 18 08:07:47 2016
Copyright (c) 1982, 2011, Oracle. All rights reserved.
Connected to:
Oracle Database 11g Enterprise Edition Release 11.2.0.3.0 - 64bit Production
With the Partitioning, OLAP, Data Mining and Real Application Testing options
SQL> create table dan (val number(4,0), gap number(4,0));
Table created.
SQL> insert into dan values (80,null);
1 row created.
SQL> insert into dan values (256,null);
1 row created.
SQL> insert into dan values (144,null);
1 row created.
SQL> insert into dan values (5,null);
1 row created.
SQL> insert into dan values (12,null);
1 row created.
SQL> insert into dan values (134,null);
1 row created.
SQL> insert into dan values (15,null);
1 row created.
SQL> insert into dan values (14,null);
1 row created.
SQL> insert into dan values (121,null);
1 row created.
SQL> commit;
Commit complete.
SQL> update dan a
2 set gap = val - (
3 select nvl(max(val),0)
4 from dan b
5 where b.val < a.val );
9 rows updated.
SQL> commit;
Commit complete.
SQL> select * from dan order by gap desc;
VAL GAP
---------- ----------
256 112
80 65
121 41
134 13
144 10
12 7
5 5
14 2
15 1
9 rows selected.
SQL> drop table dan;
Table dropped.
SQL> exit
The solution creates a table of value/gap tuples, then enters the data into the table. The update statement computes the gaps, and the final select displays the output in decreasing order by gap: 256, 80, 121, 134, 144, 12, 5, 14, 15.
A Scheme solution appears on the next page.
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!):
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 1In 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]
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.
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)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: