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.

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
    It didn’t post the link…sorry.

  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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: