Programming Praxis

8 Responses to “Diminishing Gap Sort”

1. -Dan- said

   August 19, 2016 at 8:32 PM

   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

   August 20, 2016 at 6:09 AM

   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

   August 21, 2016 at 2:21 PM

   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

   August 21, 2016 at 10:13 PM

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

   August 21, 2016 at 10:15 PM

   http://paste.lisp.org/display/323870
   It didn’t post the link…sorry.
6. Paul said

   August 22, 2016 at 8:01 AM

   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

   August 22, 2016 at 4:47 PM

   A solution in Racket.
8. Daniel said

   September 1, 2016 at 12:29 AM

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