Sort only part of a _temporary_ Array

[yabwon]

100% agree, pure gold! Like all from the man.

Bart

[AndersS]

Hi!

(Perhaps stupid question)

Is the SAS code for the macro %QSORT avaiable, as SAS code than can be included directly in the Data-step?

I am using SAS ODA .
I do not know proc fcmp. (Would be nice to learn, but I am writing a paper, and do not have the time).

Does anyone have a good version of  %QSORT, that I can download?

MANY THANKS in advance!

/Br Anders

(Age and IQ are 76+. Trying to understand quantile confidence interval estimates).

[KachiM]

Here is a FCMP based Quick Sort Routine just for your reference. 

proc fcmp outlib = work.cmpar.lib;
   subroutine qsort(v[*], left, right); 
   outargs v; 
   if left >= right then return; 
   call swap(v, left, ceil((left + right) / 2));
   last = left;
   do i = left to right;
      if v[i] < v[left] then call swap(v, last, i);
   end;
   call swap(v, left, last);
   call qsort(v, left, last - 1);
   call qsort(v, last + 1, right);
   endsub;
   subroutine swap(v[*], i, j); 
     outargs v;
     temp = v[i];
     v[i] = v[j];
     v[j] = temp;
   endsub;
quit;

options cmplib = work.cmpar;
/* Sort values from 2 to end of the Array k[*] */
data _null_;
   array k[5] _temporary_ (100, 2, 70, 12, 50); 
   call qsort(k, 2, dim(k)); 
   SORTED = catq('d',' ', of k[*]);
   put SORTED =; /* SORTED=100 2 12 50 70 */
run;

[AndersS]

Hi! Very nice!   I will try it in SAS ODA. /Br Anders

[AndersS]

Hi! This solution using PROC FCMP works nicely in SAS ODA.

/Br AndersS

[hashman]

Hi, @KachiM :

Have you tested this recursive implementation against even a modestly sizeable array - let's say, N=10000? For me, it hits a fatal exception both under Linux 64 and Windows 64 already at N=5000.

Frankly, I can quite understand how this can work for teh quick sort algorithm since I don't see the fundamental quick sort "burn the candle from both ends" loop in it. Typically, it would look like so:

    p = a[l] ;
    i = l ;
    j = h + 1 ;
    do until (i >= j) ;
      do until (a[i] ge    p) ; i ++ 1 ; end ;
      do until (p    ge a[j]) ; j +- 1 ; end ;
      if i < j then call swap (a, i, j) ;
    end ;
    call swap (a, l, j) ;

 Also, there is no provision against the quick sort's worst case scenario - i.e., its O(N) time when the array in question is already sorted. 

I do have proper FCMP quick sort implementations, both recursive and iterative (shared circa 2018 on SAS-L). However, the straight iterative implementation used in my old QSORT macro works somewhat faster than either - most likely, because it avoids the overhead of internally buiding up and unrolling the recursion. It would be interesting to see how recursion implemented via the LINK routine would fare compared to the rest (just occurred to me, will try, time permitting). 

Kind regards

Paul D.  

[yabwon]

Cześć Pavle,

When I was implementing QuickSort in BasePlus package as a mix of FCMP and PROTO C routines (e.g. qsortincbyprocproto(), quicksorthash(), or quicksortlight()) I also had problem with "stack overflow" in case of recursive implementation. Than I went to iterative and everything worked as a charm.

I remember we had a "recursive vs. iterative" discussion some time ago at SAS-L. Is far as I remember, in all test cases we talked about the iterative was faster.

Bart

[hashman]

Cześć Bartku,

Frankly, I had no problems with my recursive FCMP implementation at any N, except having to use the quick sort all the way without switching to the straight insertion sort at some M => 9 point (you can find it in the SAS-L archives; or alternatively I can send it to you if you're interested).

Any purely SAS "external" array sort implementation I've tried runs about twice or more the time compared to SORTN - not surprising since it's internal, even though based on the heap sort, not quite the fastest sorting scheme. For the sake of curiosity, I've implemented the heap sort "externally" (i.e. in DATA step code using the LINK routine for heap-rebuilding recursion), and it's about 4 times slower than SORTN. However, PROTO C quick sort coupled with FCMP (Matt Kastin posted it on SAS-L circa 2017-18, IIRC) is almost on par with SORTN speed-wise (not surprising, either).    

OTOH, external array-sorting routines are much more functionally flexible than SORTN/C in terms of ascending/descending, handling dupes, sorting parallel arrays, etc. All these options are the simplest to implement using the hash object, particularly when more than one array is used as the key, even though it comes at the expense of losing some speed compared to the hard-core implementations like quick sort.   

Serdeczne pozdrowienia,

Pavlo

[KachiM]

Hi, Paul D.

I have had no problem with a large array. I have tested on an array sized to 1E7 with no fatal exception. Here is the log. I am giving spec. of my Desktop and SAS version used.

98   options fullstimer;
99   data _null_;
100     array k[10000000] _temporary_ ;
101     do i = 1 to 10000000;
102        k[i] = ceil(ranuni(123) * 1e8);
103     end;
104     call qsort(k, 2, 10);
105     do i = 1 to 20;
106        put k[i]=;
107     end;
108  run;

k[1]=75039609
k[2]=12466523
k[3]=17838965
k[4]=18768585
k[5]=22111402
k[6]=32091203
k[7]=35711708
k[8]=39808191
k[9]=78643830
k[10]=90603339
k[11]=77618419
k[12]=43607415
k[13]=96750024
k[14]=26370295
k[15]=71393449
k[16]=55485760
k[17]=53125006
k[18]=86134461
k[19]=14207808
k[20]=86042479
NOTE: DATA statement used (Total process time):
      real time           0.25 seconds
      user cpu time       0.18 seconds
      system cpu time     0.01 seconds
      memory              79715.28k
      OS Memory           96800.00k
      Timestamp           02/14/2024 12:13:10 PM
      Step Count                        10  Switch Count  0

My Desktop has the following specs:
Processor: Intel core i5-10400 CPU @ 2.90 GHz
Ram: 8.00 GB
System Type: 64-bit OS, x64-based processor

SAS 9.4 M6 was used.

[hashman]

Hi, KachiM:

I understand that but you're sorting only a few elements. What happens if you try:

call qsort (k, 1, 10000) ; 

or many more than 10000?

Best regards

Paul D. 

[KachiM]

Hi, Paul D.

The recursive quicksort for the entire array fails for large N but for the sliced array like the one the original poster asked can work for smaller N.

With regards,

KachiM

[hashman]

Hey Peter,

Thanks 1E6 for your generous plug. 

😀

Kind regards

Paul D.