Quicksort in SAS for sorting datasets

Question

As a challenge for my own amusement, I decided to write a SAS macro for sorting datasets, deliberately avoiding all of the built-in methods (e.g. proc sort / proc sql / ordered hash object).

Remarks:

I've kept as much of the logic as possible in data step code, but inevitably there's still quite a bit of macro logic.
link is more or less equivalent to goto, and return is more or less equivalent to comefromlast link - this was the most convenient way I could find of executing sections of code multiple times with the main data step.
The code is not recursive - instead, I've used an array to store the ranges for queued up quicksort passes.
Obviously performance is terrible compared with proc sort - for any reasonably large dataset this is several orders of magnitude slower - but as far as I can tell the output is at least correct.

Code:

option mprint source spool;

%macro quicksort(DSN,OUT,BY, DEBUG=N);

%let KEEP_SYNTAX_HIGHLIGHTING = %nrstr(%mend);

%let LIB = %upcase(%scan(&DSN,1,.));
%let DS  = %upcase(%scan(&DSN,-1,.));
%let BY  = %upcase(%trim(%sysfunc(compbl(&BY))));
%let BYVARS = %eval(%sysfunc(countc(&BY,%str( )))+1);

%put Sorting &LIB..&DS by &BY into output dataset &OUT;

%if &LIB = &DS %then %let LIB = WORK;

proc sql noprint;
    select upcase(NAME), LENGTH, COUNT(*)
        into    :NNAMES     separated by ' ',
                    :NLENGTHS separated by ' ',
                    :NCOUNT
        from sashelp.vcolumn
        where LIBNAME = "&LIB" and MEMNAME = "&DS" and TYPE = 'num'
        ;
    select upcase(NAME), LENGTH, COUNT(*), max(LENGTH)
        into    :CNAMES     separated by ' ',
                    :CLENGTHS separated by ' ',
                    :CCOUNT,
                    :MAXCLENGTH
        from sashelp.vcolumn
        where LIBNAME = "&LIB" and MEMNAME = "&DS" and TYPE = 'char'
        ;
    select NAME
        into    :LISTNAMES separated by '--'
        from sashelp.vcolumn
        where LIBNAME = "&LIB" and MEMNAME = "&DS"
        having varnum = min(varnum) or varnum = max(varnum)
        ;
    select NLOBS
        into    :NOBS
        from sashelp.vtable
        where LIBNAME = "&LIB" and MEMNAME = "&DS"
        ;
quit;

%put NNAMES         = &NNAMES;
%put NLENGTHS   = &NLENGTHS;
%put NCOUNT     = &NCOUNT;

%put CNAMES         = &CNAMES;
%put CLENGTHS   = &CLENGTHS;
%put CCOUNT     = &CCOUNT;
%put MAXCLENGTH = &MAXCLENGTH;

%put LISTNAMES  = &LISTNAMES;
%put NOBS       = &NOBS;


/*Define macro vars for names and positions of by variables*/
%do i = 1 %to &BYVARS;
    %let NPOS = 0;
    %let CPOS = 0;
    %let BYVAR&i = %scan(&BY,&i);
    %do j = 1 %to &NCOUNT;
        %if &&BYVAR&i = %scan(&NNAMES,&j) %then %let NPOS = &j;
    %end;
    %do j = 1 %to &CCOUNT;
        %if &&BYVAR&i = %scan(&CNAMES,&j) %then %let CPOS = &j;
    %end;
    %let BYVAR&i._POS = %sysfunc(max(&NPOS,&CPOS));
    %if &NPOS %then %let BYVAR&i._TYPE = N;
                        %else %let BYVAR&i._TYPE = C;

    %put BYVAR&i                = &&BYVAR&i;
    %put BYVAR&i._POS       = &&BYVAR&i._POS;
    %put BYVAR&i._TYPE  = &&BYVAR&i._TYPE;
%end;

data &OUT(keep = &LISTNAMES);
    /*Construct PDV for output dataset*/
    if 0 then set &DSN;

    %if &NCOUNT %then %do;
        /*Define 1-d array for each var with nobs entries (to assign correct lengths)*/
        %do i = 1 %to &NCOUNT;
            array N&i._{&NOBS} %scan(&NLENGTHS,&i);
        %end;
        /*Define 2-d array containing the above 1-d arrays - use these for the actual sorting*/
        array _N{&NCOUNT,&NOBS} 
        %do i = 1 %to &NCOUNT; 
            %do j = 1 %to &NOBS;
                N&i._&j
            %end;
        %end;;
        /*Array to use for input / output*/
        array nums{*} &NNAMES;
    %end;

    /*Repeat the above steps for character vars*/
    %if &CCOUNT %then %do;
        %do i = 1 %to &CCOUNT;
            array C&i._{&NOBS} $%scan(&CLENGTHS,&i);
        %end;
        array _C{&CCOUNT,&NOBS} $
        %do i = 1 %to &CCOUNT; 
            %do j = 1 %to &NOBS;
                C&i._&j
            %end;
        %end;;
        array chars{*} $ &CNAMES;
    %end;

    /*Array to hold quicksort parameters low and high for each branch, plus whether or not it's run*/
    array _branch[2,&NOBS];

    /*Populate the 2-d arrays ready for sorting*/
    do _n_ = 1 by 1 until(eof);
        set &DSN end = eof;
        %if &NCOUNT %then %do;
            do i = 1 to &NCOUNT;
                _N[i,_n_] = nums[i];
            end;
        %end;
        %if &CCOUNT %then %do;
            do i = 1 to &CCOUNT;
                _C[i,_n_] = chars[i];
            end;
        %end;
    end;

    /*Sort logic goes here!*/

    /*First-time setup*/
    call streaminit(2);

    row1 = 1;
    row2 = &NOBS;
    link queue;

    link quicksort;

    /*A routine for queueing up runs of quicksort*/
    queue:
        if row1 < row2 then do;
            max_branch + 1;
            _branch[1,max_branch] = row1;
            _branch[2,max_branch] = row2;
            %if &DEBUG = Y %then %do;
                put "Queueing branch " max_branch "from row " row1 "to row " row2;
            %end;
        end;
    return;


    /*A routine for swapping 2 rows*/
    swaprows:
        if row1 ne row2 then do;
            %if &DEBUG = Y %then %do;
                put "Swapping rows " row1 " and " row2;
            %end;
            length  row1 row2 8 
                            %if &NCOUNT %then %do; t_n 8 %end;
                            %if &CCOUNT %then %do; t_c $ &MAXCLENGTH %end;
                            ;
            /*This is called within an i-loop, so use j as index*/
            %if &NCOUNT %then %do;
                do j = 1 to &NCOUNT;
                    t_n                 = _N[j,row1];
                    _N[j,row1]  = _N[j,row2];
                    _N[j,row2]  = t_n;
                end;
            %end;
            %if &CCOUNT %then %do;
                do j = 1 to &CCOUNT;
                    t_c                 = _C[j,row1];
                    _C[j,row1]  = _C[j,row2];
                    _C[j,row2]  = t_c;
                end;
            %end;
        end;
    return;

    /*A routine for printing the by variables of the selected row to the log for debugging*/
    %if &DEBUG = Y %then %do;
        byvars:
            if row1 = high  then t_c = "pivot";
                                            else t_c = "row";
            put "BYVARS for " t_c row1 @;

            %do i = 1 %to &BYVARS;
                %if &&BYVAR&i._TYPE = C %then %do;
                    t_c = _&&BYVAR&i._TYPE[&&BYVAR&i._POS,row1];
                    put "&&BYVAR&i=" t_c @;
                %end;
                %else %do;
                    t_n = _&&BYVAR&i._TYPE[&&BYVAR&i._POS,row1];
                    put "&&BYVAR&i=" t_n @;
                %end;
            %end;
            put;
        return;
    %end;

    /*Let's try quicksort!*/
    quicksort:
    branch = 0;

    do until(branch = max_branch);
        branch + 1;
        low     = _branch[1,branch];
        high    = _branch[2,branch];

        %if &DEBUG = Y %then %do;
            put "Quicksorting range " low " to " high branch=;
        %end;
        /*Choose a pivot*/
        store_index = low;
        pivot_index = low + floor(rand('uniform')*(high - low));
        %if &DEBUG = Y %then %do;
            put "Pivoting on row " pivot_index;
        %end;

        /*Swap the high and pivot rows*/
        row1 = high;
        row2 = pivot_index;
        link swaprows;

        %if &DEBUG = Y %then %do;
            link byvars;
        %end;

        /*Partition based on selected pivot*/
        do i = low to (high - 1);
            swap_flag = 0;
            /*If byvar1(row1) < bybar1(row2), trigger a swap*/
            if _&BYVAR1_TYPE[&BYVAR1_POS,i] < _&BYVAR1_TYPE[&BYVAR1_POS,high] then swap_flag = 1;
            /*For all subsequent byvars, only trigger a swap if byvar(n-1)(row1) = byvar(n-1)(row2)*/
            %do i = 1 %to &BYVARS;
                %if &i > 1 %then %do;
                    %let j = %eval(&i - 1);
                    else if _&&BYVAR&j._TYPE[&&BYVAR&j._POS,i] = _&&BYVAR&j._TYPE[&&BYVAR&j._POS,high] 
                            and _&&BYVAR&i._TYPE[&&BYVAR&i._POS,i] < _&&BYVAR&i._TYPE[&&BYVAR&i._POS,high] 
                            then swap_flag = 1;
                %end;
            %end;

            %if &DEBUG = Y %then %do;
                put "Partition:" i= Store_index= swap_flag=;

                row1 = i;
                link byvars;
            %end;

            if swap_flag then do;
                row1 = i;
                row2 = store_index;
                link swaprows;
                store_index + 1;
            end;
        end;

        /*Move pivot to final place*/
        row1 = high;
        row2 = store_index;
        link swaprows;

        /*Queue up next two runs of quicksort*/
        row1 = low;
        row2 = store_index - 1;
        link queue;

        row1 = store_index + 1;
        row2 = high;
        link queue;
    end;

    /*Ouput the contents of the 2-d arrays now that they've been sorted*/
    do _n_ = 1 to _n_;
        %if &NCOUNT %then %do;
            do i = 1 to &NCOUNT;
                nums[i] = _N[i,_n_];
            end;
        %end;
        %if &CCOUNT %then %do;
            do i = 1 to &CCOUNT;
                chars[i]= _C[i,_n_];
            end;
        %end;
        output;
    end;

run;

%mend quicksort;

Test case:

data class;
    set sashelp.class;
run;

%quicksort(class,sorted,sex age name);

proc sort data =class out = target;
    by sex age name;
run;

Jamal · Answer 1 · 2015-09-15 16:41:46Z

As far as overall, it looks like a good way to approach this. It's probably not how I would approach it, but given your choices at the start it looks good overall, and it does work. It's very slow, but it's not impossibly slow, and for most uses it's perfectly reasonable.

So, here are my initial critiques. I have peeked around your code some, but haven't done a proper thorough review yet; I'll add those over time.

Looking at the macro definition line itself:
```
%macro quicksort(DSN,OUT,BY, DEBUG=N);
```
I tend to prefer to require named parameters rather than permitting positional parameters, particularly with a complicated call that has a list in it. It's very easy to get this one wrong otherwise.

Also, if this will be used by others, it's good practice to include some information about the parameters.

Example:
```
%macro quicksort(dsn /*Input Dataset Name (including libname if needed) */,
             out /*Output Dataset Name (including libname if needed) */,
             By  /*By Variables */,
             Debug=N /* Debug flag, set to Y to get additional debugging information to the log */)
```
Doing it this way will allow Enterprise Guide to show the notes inline in the syntax tips, and also allows readers to more easily see exactly what the macro parameters mean.

I would also recommend using data instead of dsn, unless your site always uses dsn, for the input name: that's what people will expect it to be named, since that's what it is on most procs.

Finally, I would not require OUT. This can either be done by adding a default for it to IN, or by some code in the macro. This is, again, the default behavior in SAS, and as such the expectation of the user will likely be that it still behaves this way.
Parameter checking

You should always check your parameters for presence/absence, if they're mandatory parameters (as IN and BY are), and for being legal values for those parameters. Otherwise it can be very hard to know why something doesn't work properly. What if IN has a three level name for some reason?
Debug flag usage

Much, much more of the output from this should be included as optional based on DEBUG=Y. Right now you get a huge amount of output that's not needed. Almost everything you %put other than perhaps that first note that you're actually quicksorting should be in a &debug=Ygroup.
PROC SQL notes

You should definitely always have a clean log in macros like this. That means not doing things like your PROC SQLs that generate NOTE: The query requires remerging summary statistics back with the original data.. Split those queries such that you don't have to remerge - or do it a different way.

Also, your LISTNAMES query is not truly safe: while it will almost always work properly, you are actually counting on the min being before the max, which is technically not guaranteed by SQL. Select these independently, in two queries; or use a data step, where you are guaranteed order (or, you can at least enforce it with by).
Arrays

I would use temporary arrays here. You don't really need names for your array variables, do you? You're effectively using temporary arrays, so just make them that in actuality.
Do loop iterator names

Using i and j and such for do loops is common, but a bad idea. It's very easy to get into a mess - and hard to tell exactly what an iterator is doing.

It's also very easy to have a variable name collision with those. It's not uncommon (for example) for someone to not drop i after using it as an iterator - which could then cause undesired behavior (as you'll overwrite their i, which they might want).

Instead, practice name safety. Use __ at the beginning of all created variable names, for one; or even safer, __qs_ or similar. For iterator variables, use something that describes the loop or function of the iterator: do __nswap = 1 to ... for the numeric-swapping loop, do __cswap = 1 to ... for the character-swapping loop, etc. That makes it easier for you to know what an iterator variable is supposed to be doing when reading the code - and less likely you will have a name collision with your own variables.
Links

While I'm not an anti-goto extremist, I do think in a macro you can do better than this: you can just write these as their own macros. (Or as FCMP calls, if that's your preference, but since this is already written in the macro language, why not keep it there.) That would simplify your code significantly and make it easier to read the actual datastep, plus avoid link/return which are not that common nowadays.

Thank you for the feedback! I certainly had my doubts about the link / return structure of the data step, but I couldn't think of any way of completely eliminating this aspect of it. I need to repeatedly queue up and execute sections of code within the one iteration of the main data step, which I don't think is possible with macros alone - FCMP is a good suggestion. — user3490, yesterday

asked	7 months ago
viewed	82 times
active	yesterday

current community

your communities

more stack exchange communities

Quicksort in SAS for sorting datasets

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged sorting quick-sort sas or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Quicksort in SAS for sorting datasets

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged sorting quick-sort sas or ask your own question.

Related

Hot Network Questions