%!PS
% PostScript Improved array bubble sort
% ====================================
% by  Don Lancaster

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Copyright c 2018 by Don Lancaster & Synergetics, Box 809, Thatcher, AZ, 85552

% (928) 428-4073 Email: don@tinaja.com Website: http://www.tinaja.com

% Consulting services available
 
% All commercial rights and all electronic media rights ~fully~ reserved.
% Linking usually welcome. Reposting expressly forbidden. Version 2.5
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%  Astoundingly, "they" have newly figured out how to  dramatically speed up 
%  most users of a classic bubble sort most of the time. With this simple change...

%      --->  When the inner loop makes no swaps exit the outer loop! <---

%  This works well with random data and spectacularly well with "partially presorted" 
%  stuff such as our new Apache web log file analyzer you can find at 
%  https://www.tinaja.com/psutils/log_an1.psl . 

%  But worse case does remain stuck at n squared. Here's some sample code...

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Array bubble sort utility. Insert near beginning of your PostScript code...
% sorts counts on an array of [[stuff count1 ][stuff2 count2 ].... [stuffn countn]]
% additional inside array elements or even subarrays permitted.

/bubsort2a {/curmat1 exch store
             curmat1 length 1 sub -1 1                  % start outer loop
                {/done true store                       % short exit marker
                 /maxposition exch store
                 0 1 maxposition 1 sub 
                   {/posn exch store                    % inner loop  
                    curmat1 posn get 1 get              % find current count
                    curmat1 posn 1 add get 1 get        % compare to next higher
                    lt{curmat1 posn get                 % swap only if needed
                       curmat1 posn 1 add get  
                       curmat1 exch posn exch put
                       curmat1 exch posn 1 add exch put
                       /done false store                % a swap was needed
                       }if   
                     } for                              % inner loop 
                  done {exit} if                        % stop on no swaps
                  } for                                 % outer loop 
                       curmat1                          % update sorted array
                } bind store

% Should you want to sort on a different array position, replace the
% 1 get pair in "find current count" with an appropriate value. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% demo -- remove or alter before reuse %%%%%     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% ( view as log file )

/curmat1 [[(a) 200][(b) 3452][(c) 27][(d) 1][(e) 2][(f) 17 ][(g) 1 ][(h) 1][(i) 2 ]] store

(\n starting with \n) print curmat1 {==} forall

curmat1 bubsort2a      % this actually does it!

(\n should give a sorted result of \n) print curmat1 {== }forall
(\n) print

% see https://www.tinaja.com/psutils/log_an1.psl for a more detailed example.

% EOF