% ************************************************************************
% ************************************************************************
% POSTSCRIPT INSERTION SORT UTILITIES
% ************************************************************************
%
% SUMMARY: A short tutorial and two utilities that apply an insertion
% sort to marked PostScript stack values of 5000 or fewer
% elements. One sorts low to high, while the other sorts low
% absolute value to high absolute values. Demos are included.
%
% Copyright c 1991, 1996 by Don Lancaster. All rights fully reserved.
% Free help line and additional info: (6520) 428-4073.
%
% ************************************************************************
% Name of textfile: INSORT.PS
% Source: SYNERGETICS
% Author: Don Lancaster
% Desc: PostScript insertion sort utilities
% Date: July 29, 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.
% Consulting support via www.tinaja.com
%
% Keywords: PostScript, insertion, sort, absolute
%
% Timing: NTX execution time: 100 values in 1 second.
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% IMPORTANT NOTE: Two way comm REQUIRED for this demo to run. Be
% ABSOLUTELY CERTAIN to use Serial, AppleTalk,
% bidirectional parallel or Shared SCSI comm.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% POSTSCRIPT INSERTION SORTS:
% ===========================
% By Don Lancaster
% An insertion sort is usually MUCH faster than a classic bubble sort.
% Values are placed one at a time into an already presorted array.
% Let's call the pile of marked and presorted numbers on the stack a
% HEAP. Here is one algorithm for a true insertion sort...
% (1) Find the HALF of the heap the new value belongs in.
% (2) Find the QUARTER of the heap the new value belongs in.
% (3) Find the EIGHTH of the heap the new value belongs in.
%
% (n) Repeat this process until you know exactly where the
% value belongs. n times for values less than 2^n.
%
% (n+1) Roll over the needed values to do the correct insertion.
%
% A true insertion sort theoretically takes (n)log(n) time units to
% sort, compared to the ridiculously longer (n)^2 of a bubble sort.
% Insertions sorts are theoretically among the fastest possible.
% Unfortunately, overhead can cut into the efficiency of a true
% insertion sort, especially when working with fewer values. For
% instance, a dozen "easy" comparisons inside a loop might execute
% considerably faster than one "hard" comparison outside of a loop.
% Two working insertion sorts are shown below that seem to be a useful
% compromise between overhead and efficiency. While they certainly can
% be further improved, they are fast, useful, and understandable as is.
% Here is the current algorithm used...
% (1) If there are zero values presorted, insert the value.
%
% (2) If there is only one value presorted, compare values
% and exchange if needed.
%
% (3) Do the following steps ONLY if there are two or more
% presorted values...
%
% (a) Compare the new value against the MIDDLE value of
% the heap.
%
% (b) Compare the new value against sequential values
% in the heap, starting either at the bottom or in
% the middle, per the results of (a).
%
% (c) Roll the new value into the appropriate heap position.
%
%
% The utilities shown below can certainly be improved and fine tuned. I
% stopped here because they were "good enough' for what I wanted.
% Stack limited to 500 values with PostScript level I. Level II
% limit depends upon implementation, but is typically >15,000.
% A free INCREDIBLE SECRET MONEY MACHINE for any faster code.
% INSERTION SORT UTILITIES
% ========================
% /insort does an insertion sort, placing the top stack object in the
% appropriate position in a mark delimited set of stack values. The
% LOWEST value is just above the mark, as in mark -6 -4 0 2 73.
/insort { counttomark dup 3 lt {2 eq {2 copy gt {exch}if}if }
{1 sub /numvalues exch def /newvalue exch def numvalues dup 2
div cvi dup 2 add index newvalue lt {exch} if pop /numvalues
exch def 0 numvalues -1 0 { index newvalue lt {1 add}{exit}
ifelse} for numvalues sub neg 1 add newvalue exch 1 roll}
ifelse} bind def
% /abinsort does an absolute insertion sort, placing the top stack
% object in the appropriate position in a mark delimited set of stack values.
% The LOWEST ABSOLUTE value is just above the mark: mark 0 2 -4 -6 73.
/abinsort { counttomark dup 3 lt {2 eq {2 copy abs exch abs exch gt
{exch}if}if}{1 sub /numvalues exch def /newvalue exch def numvalues
dup 2 div cvi dup 2 add index abs newvalue abs lt {exch} if pop /numvalues
exch def 0 numvalues -1 0 { index abs newvalue abs lt {1 add}{exit}
ifelse} for numvalues sub neg 1 add newvalue exch 1 roll}
ifelse} bind def
% //// demo - remove or alter before reuse. ////
% simple insertion sort example...
mark
45 insort
-99 insort
22 insort
-6 insort
15 insort
]
/mygreatvalues exch def
mygreatvalues == flush
% simple absolute sorting example
mark
45 abinsort
-99 abinsort
22 abinsort
-6 abinsort
15 abinsort
]
/mygreatabsvalues exch def
mygreatabsvalues == flush
% sorting an existing array...
/unsortedarray [ 23 -56 73 41 -98 -22 85 34 -2 -2 6 71] def
mark
unsortedarray {insort} forall
]
/sortedresult exch def
sortedresult == flush
quit
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%