%!
% ************************************************************************
% ************************************************************************
% POSTSCRIPT BUBBLE SORT UTILITIES
% ************************************************************************
%
% SUMMARY: A short tutorial and two utilities that apply a classic bubble
% sort to PostScript arrays of 5000 or fewer elements. One sorts
% high to low, while the other sorts high absolute value to low
% absolute values. Demos are included.
%
% Copyright c 1991, 1996 by Don Lancaster. All rights fully reserved.
% Free help line and additional info: (520) 428-4073.
%
% ************************************************************************
% Name of textfile: BUBLSORT.PS
% Source: SYNERGETICS
% Author: Don Lancaster
% Desc: Classic PS bubble sort utilities
% Date: July 19, 1991
% Release: 1.0
% Approx length: 10K
% Status: Copyright 1991, 1996 by Don Lancaster and Synergetics.
% 3860 West First Street, Thatcher, AZ. (520) 428-4073.
% All commercial rights and all electronic media rights
% fully reserved. Reposting expressly forbidden. Personal
% use permitted so long as this status message stays
% present and intact.
%
% POSTSCRIPT SECRETS book+disk package $39.50 VISA/MC.
%
% Keywords: PostScript, bubble, sort, absolute
%
% NTX timing: 67 milliseconds to sort 20 valued arrays. Time is
% approximately proportional to (n^2)/2.
%
% Consulting services available via www.tinaja.com
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% IMPORTANT NOTE: Two way comm REQUIRED for this demo to run. Be
% ABSOLUTELY CERTAIN to use Serial, AppleTalk,
% bidirectional parallel or Shared SCSI comm.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CLASSIC BUBBLE ARRAY SORTS:
% ===========================
% By Don Lancaster
% While very klutzy and crude, the classic bubble sort can often be the
% "best" method for sorting a few to a few dozen values in an array.
% The algorithm is obvious. Start with the final array value. Compare
% it against the previous value, and exchange the values if the final
% value is larger, thus "bubbling" largest values to the left.
% On the first pass, the largest value will end up at the left. You
% then repeat the process for all the remaining UNSORTED values. To
% sort n items requires n + (n-1) + (n-2) + ... comparisons, or
% (n)(n+1)/2 or roughly (n^2)/2 comparisons.
% To reverse the final order of either version, change lt to gt.
% Note that PS level I has a 500 element stack limit. On PS level II
% stack limit depends upon implementation and is normally much
% higher (15,000 or so) than you would care to bubble sort on.
% THE BUBBLESORT UTILITIES:
% =========================
% bubblesort accepts an array of up to 5000 elements on the stack top
% and does a classic bubble sort, replacing it with a similar array
% whose LARGEST value is first and SMALLEST value is last.
/bubblesort {mark exch aload pop counttomark /idx exch def { 0 1 idx
1 sub {pop 2 copy lt {exch} if idx 1 roll} for idx 1 roll /idx idx 1
sub def idx 0 eq {exit} if} loop ] } def
% bubbleabssort accepts an array of up to 500 elements on the stack top
% and does a classic bubble sort, replacing it with a similar array
% whose LARGEST absolute value is first and left, while the SMALLEST
% absolute value is last and to the right.
% Thus larger positive or negative numbers come earlier than smaller
% positive or negative numbers.
/bubbleabssort{mark exch aload pop counttomark /idx exch def { 0 1 idx
1 sub {pop 2 copy abs exch abs exch lt {exch} if idx 1 roll
} for idx 1 roll /idx idx 1 sub def idx 0 eq {exit} if} loop ] } def
% DEMOS:
% ======
% //// demo - remove or alter before reuse ////
1000 {37 sin pop} repeat % optional response delay
([ 1 2 -5 3 9 4 -6 5 7 6 8 -9 7 5 4 3 3 -4 2] bubblesort provides \r) print
[ 1 2 -5 3 9 4 -6 5 7 6 8 -9 7 5 4 3 3 -4 2] bubblesort ==
(\r) print
([ 1 2 -5 3 9 4 -6 5 7 6 8 -9 7 5 4 3 3 -4 2] bubbleabssort provides \r)
print
[ 1 2 -5 3 9 4 -6 5 7 6 8 -9 7 5 4 3 3 -4 2] bubbleabssort ==
(\r) print flush
% A REALLY OFF-THE-WALL EXAMPLE:
% ==============================
% Accumulating the sums of products is often used in solving linear
% equations and in digital signal processing. If, in the process of
% accumulation, large values are added to smaller ones, the accuracy
% can decrease, leading to subtle but serious errors during advanced
% PostScript work.
% for instance, summing these numbers IN THIS ORDER with PostScript...
% 4500.1 - 4502.1 + 43 - 43 + 15.3 - 9.9
% + 3.3 - 6 + 1.3 + 0.0042 + 0.0052 = 2.0094 (The CORRECT result)
% But summing these SAME numbers IN THIS ORDER with PostScript...
% 4500.1 + 0.0042 -4502.1 + 0.0052 + 1.3
% -9.9 + 3.3 + 15.3 - 6 + 43 - 43 = 2.00928 (The WRONG result)
% In the second case, accuracy is lost because of roundoffs that occur
% when very small values are subtracted from very large values.
% To get the best possible results in any PostScript accumulation,
% presort your array by absolute values, so that the LARGEST values
% are added to each other first, followed by progressively SMALLER values.
% For instance...
% [ -4502.1 0.0042 4500.1 0.0052 1.3 -9.9 3.3 15.3 -6 43 -43 ] bubbleabssort
% sorts to [ -4502.1 4500.1 43 -43 15.3 -6 -9.9 3.3 1.3 0.0052 0.0042]
% Summing the first array gives a WRONG answer, while summing the
% presorted array gives you the RIGHT answer.
quit
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Related GEnie PSRT Downloads: (PostScript as language)
%
% #294 - ACCURACY.TXT Understanding/Improving PS acuracy
% #293 - FUZZYCON.PS PS fuzzy data smoothing contest
% #290 - FUZZYFIT.PS PS fuzzy data smoother & plotter
% #289 - LINEAREQ.PS PS linear equation solver
% #270 - GUTIL13A.PTL Guru Utility PowerTools
% #219 - GENIEVST.PS PS Stock Investment Analyzer
% #190 - BEZLENGTH.PS Finding length of Bezier curve
% #146 - HISTOGRAM.PS Powerful histogram generator
% #109 - RAWPS.TXT Working with raw PostScript
%
% #270 - GUTIL13A.PTL Guru Utility Power Tools
% #219 - GONZO13A.PTL Guru Gonzo Justification Power Tools
% #245 - PSRTXREF.TXT PSRT Xref & planner (Text only)
% #246 - PSRTXREF.PS PSRT Xref & planner (Hard copy)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Portions reprinted from Don Lancaster's ASK THE GURU III.
% Now available via don@tinaja.com email from SYNERGETICS.
% Write, call, or don@tinaja.com email for your new and free PostScript
% insider secrets brochure. Or for your free Hardware Hacker brochure
% chock full of hard-to-find and unusual supply sources.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% FREE VOICE HELPLINE AND ADDITIONAL INFO: (520) 428-4073
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%