Click on FTP to download from the FTP archives.
![[FTP]](http://www2.encompassus.org/hidedecus/graphics/i_ftp.gif)
Instructional Package to Animate
Various Sorting Algorithms
Timothy Rolfe
Dakota State University
Madison, SD 57042
e-mail: ROLFE@SDNET.BITNET
Introduction
This program package is intended for students in Computer
Science courses up through Data Structures, with some possible
use for students later in their undergraduate studies.
The program uses ANSI-terminal graphics to animate
intermediate array states during the sorting of an array. The
user specifies whether the array is to be filled with values at
random, sorted in correct order, or sorted in reversed order.
Given the initial state for the array, the program applies each
sorting algorithm, which the user can pause through the ^S option
on his/her terminal. The program has built-in pauses between
sorting algorithms, where the program waits for entry of a
carriage return.
Algorithms to be animated (where the user is allowed to skip
the first four, the O(n^2) algorithms):
(1) Bubble Sort.
(2) Shaker Sort (alternating direction bubble).
(3) Selection Sort.
(4) Insertion Sort.
(5) Shell's Sort (diminishing increment sort).
(6) Heap Sort. Animation will show the generation of the heap,
then successive removals of maximal element and heap correction.
(7) Merge Sort.
(8) Natural Merge Sort --- I. The array-oriented iterative
merge sort, where the merged segments are those found at run-time
to be in order.
(9) Natural Merge Sort --- II. A list-oriented merge sort
taking advantage of existing order in the initial data.
(10) Quick Sort.
(11) Radix Sort, using radix=3.
This document comprises three sections intended to be
readable by an undergraduate student in the second year or later
of a computer science degree program:
A. User Notes, to aid the student in understanding what one sees
when running this demonstration package.
B. Implementation Notes, to aid the student in his or her
reading of the demonstration package programs. Since the
programs contain extensive internal documentation this is a
fairly short section.
C. Short display of some actual algorithm performances.
User Notes for the Sorting Demonstration Package
(0) Preliminary Notes
The data set sorted by each of the sorting algorithm is a
set of 79 integer numbers ranging from 1 to 21 with approximately
equal probability (in the random data case). Because there are
necessarily multiple occurrences of data values, the reverse
ordered data end up grouped into successive regions with the same
value --- which for most algorithms will appear to be regions
already in forward order. Hence, where reversed data constitute
the worst case input, this package will not in fact show absolute
worst case behavior.
The screen display of data points gives the array cell index
via the column in which an asterisk is printed and the cell
values via the row number, where the top of the screen has the
lowest row number and the bottom has the highest. This has the
effect of inverting the Y-axis: while the data are sorted in a
non-decreasing fashion, the display of such an order shows up as
a diagonal display from the top left corner to the bottom right
corner of the screen.
These user notes refer to the Pascal implementation of the
sorting demonstration package. A Fortran implementation is
available for code comparison purposes; that implementation
differs in behavior from this Pascal implementation only in the
Merge Sort (due to the non-recursive nature of Fortran) and in
the omission of the second Natural Merge Sort.
In discussions of algorithm order, "lg n" denotes the base-2
logarithm of n.
References are given at the end of the discussion on each
sorting algorithm in lieu of detailed references in the body of
each discussion.
(1) Bubble Sort
As Sedgewick notes, there is scarcely anything good one can
say about the Bubble Sort algorithm: it is an O(n^2) algorithm;
it is not intuitive, and it has a large inner loop. For some
reason, though, it is the sorting algorithm to which many
introductory programming texts subject their readers.
As the algorithm runs, you will see the asymetric nature of
the algorithm: data elements moving in the same direction as the
inner loop move quickly towards their proper place, while those
moving in the opposite direction move only one location at a
time. Thus the screen below the diagonal fairly quickly empties
out, and intermediate stages begin to look like snap-shots of a
drop-off in a lake with bubbles above.
References: [DEK, 106ff] [NW, 81-82] [RS, 99]
(2) Shaker Sort
The Shaker Sort is an optimization of the Bubble Sort. The
direction of the inner loop alternates forward and backward, thus
removing the asymmetry in the algorithm's behavior. Other
optimizations seen on examining the code itself remove extraneous
comparisons, so that the comparison count for random data is
appreciably smaller than that seen with the Bubble Sort itself.
As the algorithm runs you will see central elements moving
back and forth with the alternating direction for the inner loop.
Also, both the lower and upper triangle clear of elements so that
the data move closer and closer to a single band down the
diagonal.
References: [DEK, 110-111] [NW, 82-83]
(3) Selection Sort
The easiest way to motivate the Selection Sort algorithm is
to examine the way a poker player (five-card draw) arranges a
hand: all cards are picked up and fanned in one hand; then the
player successively removes cards with the other hand so that the
other hand ends up holding a sorted hand. Similarly with the
Selection Sort, the data are partitioned into an unsorted and
sorted section. Then the algorithm successively finds the
element in the unsorted section that belongs in the cell adjacent
to the sorted section, followed by an interchange of elements to
put the proper element into place. As implemented in this
package, the sorted section is the bottom of the array.
This algorithm, though O(n^2), is optimal in cases in which
the major expense for sorting is data movement rather than
comparisons --- though even then an indirect sort [RS, 94] using
an O(n lg n) algorithm would probably be better.
As the algorithm runs you will see very little change in the
top portion of the array at each step since only a single cell is
being altered. This will appear to be the fastest of all the
sorts in the package. That is because the bottle-neck in the
animation is data movement, and Selection is the optimal sort in
those circumstances. Note, however, that we end up with a very
large comparison count, as large or larger than the comparison
count for Bubble Sort above (1).
References: [DEK, 139ff] [NW, 79-81] [RS, 94-95]
(4) Insertion Sort
The easiest way to motivate the Insertion Sort algorithm is
to examine the way a bridge player arranges a hand: 13 cards
make the Selection Sort strategy unwieldy. Instead the player
picks up the cards one at a time, inserting each into its proper
location in the hand picked up so far. Similarly with the
Insertion Sort, the data are partitioned into a sorted and
unsorted section. In this case, however, the element in the
unsorted section adjacent to the sorted section is moved aside
and elements in the sorted section are moved down until the cell
is opened up where that element belongs.
This algorithm is optimal in cases either where the number
of elements to be sorted is small or where the data are already
sorted or nearly sorted.
As the algorithm runs you will see the unsorted portion
remaining basically unchanged, while the sorted portion will
undergo shifts to the right making room for the element being
inserted.
References: [DEK, 80ff] [H&S, 135-37] [NW, 76-78] [RS, 95-96]
(5) Shell's Sort (diminishing increment sort)
Shell's Sort is an optimization of Insertion Sort. As noted
above, Insertion Sort is optimal for small data sets and for data
sets nearly in order. Shell considers the data set as an
interleaved collection of data sets based on a step size or
increment. For some increment h, consider the array as a set of
h different arrays: 1,1+h,1+2h,1+3h; 2,2+h,2+2h,2+3h,...; etc.
(That is, each set contains all cells that have indices with the
same remainder on division by h.) Initially h is fairly large.
In this case, the data sets are small and Insertion Sort is
optimal --- and elements move quickly towards where they belong.
Then h is repeatedly decreased until finally h=1; in each pass,
though the size of the data sets is increasing, each data set is
closer and closer to being sorted, so that Insertion Sort remains
optimal.
Theoreticians have not been able to characterize the
behavior of Shell's Sort, in part because it depends strongly on
the sequence of increments used. Empirically it appears to be
O(n^k) where k=1.2 to 1.3 or some combination of O(n lg^2 n) and
O(n lg n). This algorithm often runs faster than some of the
pure O(n lg n) algorithms for values of n less than a thousand.
As the algorithm runs you will initially see changes
occurring fairly widely separated --- at first it is rather easy
to see the increment being used. With each pass, you will see
the array becoming closer and closer to a diagonal band while the
increment becomes smaller and smaller.
References: [DEK, 84ff] [NW, 85-86] [RS, 97-99]
(6) Heap Sort
There is, unfortunately, no simple analogy for the Heap
Sort. The basis for this algorithm is the "heap" data structure,
in which a heap is made up of a root and two (possibly empty)
subheaps. A heap is distinguished from a general binary tree in
that the data value attached to the root is an extremum with
respect to the data values in the two subheaps. As used for a
non-decreasing sort, the heap root contains a value larger than
or equal to data values in the two "child" subheaps. (See the
references for details on how the heap binary tree is represented
in an array.)
The basic operation in working with a heap is the heap
correction: given a particular element within the heap, the
child subheaps are properly ordered heaps while the element
itself (in root position for this (sub)heap) is possibly invalid.
If the element is invalid, it is swapped with the value at the
top of the subheap with the larger value. Then that heap is
itself corrected. This is the "down-heap" operation since the
data value moves down the heap until it finds its proper place.
Heap sort progresses in two phases: (1) the initial heap is
generated by beginning at the middle of the array and working
towards the front, using the down-heap operation to generate
successively larger subheaps until the down-heap at cell 1 gives
a single heap; (2) repeatedly the value at the root of the heap
(the largest element in the heap) is swapped with the value at
the very end, followed by a decrement of the heap size and a
down-heap operation on the smaller heap.
As the algorithm runs you will first see the generation of
the initial heap. This is finished when the screen display shows
a wedge with fairly wide base at the upper right corner of the
screen narrowing down to a point at the lower left corner. You
will then see swaps of the heap root with the end heap element
followed by the heap correction. Thus the sorted portion will
grow from the lower right corner towards the upper left. If you
watch carefully you will also see that each heap correction step
is O(lg n), where n is the (decreasing) heap size.
References: [DEK, 145ff] [H&S, 349-52] [NW, 87-91] [RS, 135-37]
(7) Merge Sort
The Merge Sort is a natural one for data in lists, and the
Pascal code actually performs this sort by generating a list of
data values. The algorithm is also a natural one for recursion:
if the list received for sorting contains a single element it is
returned as already sorted; if is contains more than one, the
list is broken into two sublists of equal size, which are then
recursively sorted themselves followed by the merge of the two
sorted sublists.
As the algorithm runs you will see short ordered sequences
appear which grow by merging. You will also see the recursive
nature of the algorithm: the entire left half of a screen
section is sorted before any changes are made on the right half;
then when the right half has been sorted both halves are merged
into a single sorted section.
References: [DEK, 165ff] [H&S, 346-49] [RS, 148-49]
(8) Natural Merge Sort --- I
It is also possible to use the Merge Sort idea while moving
data back and forth between two arrays, generating successively
longer sorted sections in the movement. See [H&S, 343-46] for a
discussion of such an implementation which ignores the initial
data organization. The Natural Merge Sort represents an attempt
to take advantage of existing order within the data as received.
The basic strategy for the Natural Merge is to treat the
array as a sequence of sorted sections. The algorithm repeatedly
goes through the array merging pairs of adjacent sorted sections
into single sorted sections while moving the data values back and
forth between the two arrays. Eventually there is only one
sorted section in the entire array.
As the algorithm runs you will see the sorted sections
become larger and larger with each iteration. When the number of
sorted sections is odd, the right-most section is not changed
since it does not have another section with which to merge.
References: [DEK, 161ff] [NW, 105ff]
(9) Natural Merge Sort --- II
The basic strategy of the Natural Merge Sort above can also
be applied in a list-oriented implementation: the data as
received are transformed not into a single list (as in the Merge
Sort above) but into a set of lists, each of which is already
sorted. One advantage that the list implementation has over the
array implementation is that we can add data elements both to the
front and to the back of the list being generated, while in the
array implementation we simply find the break-points within the
array for the sorted sequences.
This algorithm terminates right after initial set-up when
the data are sorted either in a forward fashion or in a reverse
fashion (the latter because the list can also grow at the front).
Unfortunately, with other than ordered data this algorithm does
not perform much better than the straight Merge Sort above (7).
The slight performance improvement reflects the replacement in
this algorithm of the O(n lg n) list traversal (required for the
successive splittings of lists) by a simple O(n) operation in
generating the initial queue of sorted lists --- the observed
comparison count is actually higher here.
As this algorithm runs you will see behavior nearly
identical with what you observed for the first Natural Merge,
except that the initial sorted sections will probably be larger.
References: None -- this extension of Natural Merge is my own.
(10) Quick Sort
If a computer professional were restricted to a single
sorting algorithm, that would probably be the Quick Sort. The
basic strategy here is a clever one: position a single array
element (called the partitioning element) to its proper place,
then do the same thing to the array portion before and after that
element. This is done by scanning the array portion from both
sides looking for left elements that belong to the right of the
partitioning element and right elements that belong on the left:
such elements are then swapped --- unless the scan pointers have
passed each other. Then the partitioning element is moved to its
proper place and the left and right array subportions are
recursively sorted.
As the algorithm runs you will see the partitioning
dramatically displayed: the screen display will change to one
with two rectangular regions containing data, the upper left and
the lower right. This implementation then recursively sorts the
shorter segment first before sorting the larger segment.
References: [DEK, 114ff] [H&S, 338-41] [NW, 91-98] [RS, 103-13]
(11) Radix Sort (Radix 3)
The Radix Sort algorithm is unlike all the preceeding ones:
they are "comparison-based sorts" which operate by comparing data
values with each other. The Radix Sort is one based on
decomposing the data into fields and grouping items based on
those fields without doing any explicit comparison of data values
with each other. The easiest analogy would be setting data into
alphabetical order, based on the individual character fields.
See the references given below for a detailed description of this
algorithm, which is perhaps even more obscure than the Heap Sort.
In this implementation, the data values are considered as
base-three numbers and are sorted from least-significant digit to
most-significant digit. Since the data range is 1-21, all data
values are representable with at most three digits; hence the
algorithm requires three passes.
As the algorithm runs you will see that data are first set
into an organization with more adjacent elements; the second pass
leaves three clear horizontal regions of ordered data; and the
third pass leaves the data completely sorted.
References: [DEK, 170ff] [H&S, 152-56] [RS, 115-24]
Bibliography
DEK: Donald E. Knuth, The Art of Computer Programming: Sorting
and Searching (Addison-Wesley, 1973).
H&S: Ellis Horowitz and Sartaj Sahni, Fundamentals of Data
Structures in Pascal (Computer Science Press, 1984).
NW: Niklaus Wirth, Algorithms and Data Structures
(Prentice-Hall, 1986).
RS: Robert Sedgewick, Algorithms (Addison-Wesley, 1983).
Implementation Notes for the Sorting Demonstration Package
Both the Pascal implementation and the Fortran
implementation of this package contain extensive internal
documentation which provides most of the implementation
information. These notes presume that the reader also has the
program code available.
To the best of my knowledge, the Pascal implementation does
not depend on any non-standard Pascal features and so should be
transportable without any problems. The Fortran implementation,
though, does violate the ANSI standard in using variable and
subprogram names longer than six characters and in being
developed for UNIX Fortran, which does not implement column-one
carriage control on output to the terminal. (This latter
deviation is, of course, easily remedied.)
Unless otherwise indicated, each subprogram, sorting and
auxiliary, is my own implementation rather than a version or
revision of a subprogram found in one of the references.
Specifically, Shaker Sort is based on code from Wirth
[NW, 82-83]; Heap Sort is based on code from Sedgewick's
Chapter 11 [RS, 134-36]; Quick Sort is based on code and ideas in
Sedgewick's Chapter 9 [RS, 103-13].
Because of experience with a Pascal which treats DISPOSE as
a null operation, I always implement lists of records with a
program-controlled free-space list to allow for the "recycling"
of records; hence the inclusion of the NewCell and DisposeList
procedures, even though this program will not exhaust available
heap space even on an 128K Apple-II family computer.
To allow the generation of comparison counts, I have
separated out item comparisons into a function. Such an
implementation would also prove useful should the comparisons
actually involve multiple keys: the sorting subprogram itself
remains general, with the details of comparisons removed to the
Compare function. Indeed I first encountered this approach in a
local Fortran library sorting subroutine (a tree sort) at the
University of Chicago, which achieved complete generality by
requiring the user to pass two external subprograms: a KOMPAR
function to compare data associated with two indices, and a MOVE
subroutine to accomplish the movement of data associated with one
index to another index, where index N+1 is available for scratch
use.
The implementation of comparison counting is hidden behind
the procedure ZComp to zero out the comparison count and the
function NComp to return the current comparison count. Were one
to be compulsively correct, the Compare function would contain
the invocation of a CountComp procedure to increment the count.
Screen handling has been isolated to a minimal number of
subprograms and is handled slightly differently in the Pascal and
Fortran implementation based on Pascal's ability to have multiple
WRITE statements to generate a single output line. The basic
operations are ClearScreen and GotoXY. The present code reflects
the use of ANSI-standard terminal directives for these functions.
Should one desire to drive a non-ANSI-standard terminal, these
are the only subprograms that would require modification. (The
Fortran implementation combines the GotoXY operation with the
text to be positioned into a single TextXY subroutine.)
The Bubble, Shaker, and Select Sort implementations require
no further comment.
Insertion Sort and Shell's Sort have been implemented in a
fashion to display their close relationship: both depend on an
auxiliary subprogram to perform an Insertion Sort based on a
parameter giving the increment to be used. The straight
Insertion Sort invokes this with an increment of one, while
Shell's Sort invokes it with a sequence of diminishing increments
ending at one. Because of the use of this auxiliary subprogram
with increments other than one, the inner insertion-sort loop
does not depend on a sentinel value to force exit but contains
two separate exit determinations implemented via a boolean flag.
Merge Sort is implemented differently in Pascal and Fortran.
The Pascal version shows a straight-forward list-oriented
recursive version. The Fortran version represents an iterative
implementation of the two-way merge discussed in [H&S, 343-46].
The Pascal implementation of Merge Sort contains code
specific to the demonstration package environment: the nested
Merge procedure receives an extra parameter that contains the
array index associated with the first element in the list passed.
This allows the array to be updated during each recursive call to
the Merge procedure for display purposes. In a realistic sorting
environment the array should not be updated until after the list
is completely sorted.
The first Natural Merge implementation is based strongly on
the Fortran implementation of Merge Sort. Its present
implementation generates a large number of comparison counts
because it determines sequence breaks by explicit searches in
every merge pass. These could probably be eliminated by
inclusion of an additional auxiliary array to contain indices of
sequence breaks.
The second Natural Merge is a list-oriented one and hence is
found only in the Pascal package. It represents an application
of the natural merge idea to the list-oriented merge sort. The
separate sorted lists are maintained in a circular queue of
sorted lists. These are then paired and merged until only a
single list remains in the queue. To retain the stability of the
merge sort, the procedure marks the last list to insure that it
is used only on the right of a merge. As in the Merge Sort
above, the implementation contains code specific to the
demonstration package environment: each queue entry also
contains the array index associated with the first element of its
list to allow in-progress updating of the array for display
purposes.
The Quick Sort implementation requires no further comment.
The Radix Sort is implemented differently in Pascal and
Fortran. The Pascal implementation is a list-oriented one, and
the "bins" for the sorting are generated as an array of pointer
pairs (to front and back). The Fortran implementation requires
that the user provide scratch arrays to function as the bins.
While clarity is best achieved by having three scratch arrays for
the bins in a RADIX=3 case, a little reflection will convince one
that the source array can itself function as the first bin in the
distribution of elements.
Observed Algorithm Performance
Since in the animation the major expense is data movement,
it is appropriate to make available explicit performance figures
for these algorithms as they run on a computer.
The timing program handles arrays of length up to 8192, with
a data range of 0 to 32767. Only the comparison-based sorts were
run (thus omitting the Radix Sort), and the O(n^2) sorts were
dropped when they became excessively lengthy. The sort
implementations drop the animation calls and contain the
modifications mentioned in MergeSort and NatMerge2 below.
The following tables show comparison counts and CPU times in
CPU seconds on the University of Minnesota Computer Science
computer (network name umn-cs.cs.umn.edu), a Sequent Symmetry
S27, of the program as compiled by Pascal with no compiler
options requested.
Comparison counts
Nat. Nat.
N Bubble Shaker Select Insert Shell Heap Merge Merge1 Merge2 Quick
-----+------+------+------+------+------+------+------+------+------+------
64 1845 1366 2016 1042 386 567 308 718 364 564
128 8050 5752 8128 4333 995 1383 740 1558 875 1165
256 32562 22352 32640 16853 2384 3281 1735 3887 1992 2783
512 130606 87119 130816 65954 5691 7602 3974 8305 4512 6291
1024 522551 362364 523776 271823 13572 17250 8961 19693 10030 13433
2048 33390 38635 19978 41473 22093 32394
4096 80468 85651 44050 95232 48358 67188
8192 170173 187660 96299 222852 105152 140843
CPU times on a Sequent Symmetry S27 computer
Nat. Nat.
N Bubble Shaker Select Insert Shell Heap Merge Merge1 Merge2 Quick
-----+------+------+------+------+------+------+------+------+------+------
64 0.040 0.040 0.030 0.030 0.010 0.010 0.010 0.020 0.010 0.010
128 0.190 0.150 0.130 0.080 0.020 0.020 0.030 0.030 0.020 0.030
256 0.740 0.570 0.550 0.320 0.050 0.060 0.050 0.080 0.040 0.050
512 2.960 2.220 2.170 1.280 0.120 0.140 0.100 0.180 0.090 0.120
1024 12.040 9.260 8.790 5.320 0.280 0.320 0.220 0.410 0.200 0.250
2048 0.700 0.710 0.480 0.860 0.430 0.590
4096 1.650 1.560 1.030 1.980 0.930 1.220
8192 3.520 3.430 2.230 4.650 2.070 2.570
Acknowledgements
The Pascal version of this program was developed in part
while the author was at Gonzaga University, with the final
revisions and amplifications done at the University of Minnesota.
The Fortran code included for comparison purposes was entirely
developed at the University of Minnesota.
This write-up is taken from the University of Minnesota
Computer Science Department Technical Report TR 89-72
(October 1989).
Click on FTP to download from the FTP archives.