/*****************************************************************************************************************
 
SAS file name: quicksort.sas
File location: 
__________________________________________________________________________________________________________________
 
Purpose: To demonstrate the wuicksort algorithm and the qsort macro in SAS
Author: Peter Clemmensen
Creation Date: 04/02/2020
 
This program supports the blog post "A Closer Look at the Quicksort Algorithm in SAS" on SASnrd.com

*****************************************************************************************************************/

/* quicksort */
proc fcmp outlib=work.f.f;

   subroutine partition (low, high, i, arr[*]);
      outargs low, high, i, arr;

      pivot = arr [high];

      put / "Pivot: " pivot;;
      put "Before Partition: " arr;

      i = low-1;

      do j = low to high-1;
         if arr [j] < pivot then do;
            i       = i+1;
            t       = arr [i];
            arr [i] = arr [j];
            arr [j] = t;
         end;
      end;

      t          = arr[i+1];
      arr [i+1]  = arr[high];
      arr [high] = t;

      i=i+1;
      
     put "After Partition:  " arr /;
         
   endsub;

   subroutine quicksort (low, high, arr[*]);
      outargs arr;

      if low < high then do;
         call partition (low, high, i, arr);

         call quicksort (low, i-1,  arr);
         call quicksort (i+1, high, arr);
      end;
   endsub;

run;quit;

options cmplib=(work.f);
data _null_;
   array x {10} _temporary_ (8 10 4 7 2 5 1  9 3 6);

   call quicksort(lbound(x), hbound(x), x);
run;

options cmplib=(work.f);
data _null_;
   array x {30000000} _temporary_;

   do _N_=1 to dim(x);
      x [_N_] = rand('integer', 1, 100000);
   end;

   t = time();
   call quicksort (lbound(x), hbound(x), x);
   _t = time()-t;

   put _t=;
run;


data _null_;
   array x {30000000} _temporary_;

   do _N_=1 to dim(x);
      x [_N_] = rand('integer', 1, 100000);
   end;

   t = time();
   %qsort (Arr=x);
   _t = time()-t;

   put _t=;
run;