Fun With SAS ODS Graphics: "Bublé Sort"

[tc]

Donald Knuth's The Art of Computer Programming: Volume 3: Sorting and Searching is amazing and all, but I must confess that the day I was introduced to SYNCSORT was pretty much the last day I gave a thought to the details of sorting algorithms.

But then @HomesAtMetacoda had to go and tweet out this nifty visualization of 8 fundamental sorting algorithms.

And before you know it, I was using (abusing?) SAS ODS Graphics to come up with "Bublé Sort" (code below, apologies for the bad pun!), an animated GIF that attempts to illustrate how a simple Bubble Sort works by showing how its paired comparisons put unsorted song track listings from Michael Bublé's Let it Snow EP back into their proper order.

Oh well, enough sorting nostalgia - back to PROC SORT and SQL ORDERED BY on Monday!

* Animated bubble sort of tracks from Michael Bublé's Let It Snow EP;

data LetItSnow;                             * Read unsorted EP tracks;       
input Song $char50.;
cards;
5 White Christmas
3 Grown-Up Christmas
1 Let It Snow
6 Let It Snow (Live)
2 The Christmas Song
4 I'll Be Home For Christmas
;
proc sql noprint;                           * How many rows to sort?;
select count(*) into :n from LetItSnow;

data ChartData;                             * Read songs into array and bubble sort;
array songs(&n) $ 50. _temporary_;          * Generate frames at key points for animated GIF;
set LetItSnow end=eof;
songs(_n_)=song;
if eof;
do d=1 to 5;                       
  link GenerateFrame;                       * Frames at start of sort;
end;
do i=1 to &n;                               * Bubble sort: en.wikipedia.org/wiki/Bubble_sort;
  do j=2 to &n-i+1;
    adjY=0;
     do d=1 to 2;
       link GenerateFrame;                  * Frames of current comparison (beginning);
    end;
    if songs(j)<songs(j-1) then do;         * Swap elements, generate swap frames; 
       adjY=.3333;                          * Move 1/3rd of way to destination;
       link GenerateFrame;
       adjY=.6666;                          * Move 2/3rd of way to destination;
       link GenerateFrame;
       adjY=0;
       temp=songs(j-1);
       songs(j-1)=songs(j);
       songs(j)=temp;
       end;
     do d=1 to 2;
       link GenerateFrame;                  * Frames of current comparison (ending);
     end;
  end;       
end;

j=.;   
do d=1 to 7;
  link GenerateFrame;                       * Frames at end of sort;
end;
stop;

GenerateFrame:
chartnum+1;                                 * Generate frame data for animated GIF;
do k=1 to &n;
  if j-1=k then r=k-.4;                     * Reference lines hightlight value being compared;
  else if j=k then r=k+.4;
  else r=.;
  if j-1<=k<=j then color=1; else color=0;  * Color also used to highlight compared values;
  x=0;
  y=k;
  if j-1=k then y+adjY;                     * Adjust y-values of swapped elements;
  if j=k then y+(-adjY);
  song=songs(k);
  invisibleY=-10;                           * Off-plot y-value, used for "blank" EP image frame;
  output;
end;
return; 
run;

ods _all_ close;                            * Use generated data to produce animated GIF;
options papersize=('5 in', '5 in') printerpath=gif animation=start 
        nodate nonumber animduration=.25 animloop=YES NOANIMOVERLAY;
ods printer file='/folders/myfolders/sort/BubleBubbleSort.gif';
ods graphics / border=off width=5in height=5in imagefmt=GIF;
title  height=18pt """Bublé Sort""";
title2 height=12pt "Bubble Sorting Tracks From Michael Bublé's " italic "Let It Snow" ;
title3 " ";
                                            * Image of Let It Snow EP; 
data EP;                                    * Credit: michaelbuble.com/album/let-it-snow-ep;
function='image'; Image="/folders/myfolders/LetItSnow.gif"; layer='front';

option nobyline;                            * Generate 5 leader frames with EP image;
proc sgplot data=ChartData(where=(chartnum<=5)) noautolegend sganno=ep;
by chartnum;
text x=x y=invisibleY text=song;
yaxis reverse min=0 max=%eval(&n+1) display=none;
xaxis display=none;

proc sgplot data=ChartData noautolegend;    * Generate frames from bubble sort data;
by chartnum;
text x=x y=y text=song / textattrs=(size=22pt) colorresponse=color colormodel=(green green red);
yaxis reverse min=0 max=%eval(&n+1) display=none;
xaxis display=none;
refline r / axis=y;
run;

options printerpath=gif animation=stop;     * Wrap it up;
ods printer close;

[Jay54]

Very interesting visual implementation of the "Bubble Sort" algorithm using TEXT plot statement. 

[MichelleHomes]

Impressive Bublé Bubble sort - I prefer your SASsy sort! (Love the pun too) 

[rogerjdeangelis]

Very neat