Page 245 - Programming Microcontrollers in C

230 Chapter 5 Programming Large 8-Bit Systems

optimization operation to skip over all variables that can be changed
by the hardware portion of the system without knowledge of the
program.

Sorting Programs

You might not expect that sorting routines would be important when
programming microcontrollers, but there have been several instances in
my experience where sorting of a list of data was needed in a
microcontroller application. Therefore, let’s examine some sorting
routines that can be used with a microcontroller and determine which of
several popular approaches is best for use in a microcontroller program.
There are several sorting routines that are popular with program­
mers. The three most-used routines are named the entry sort, the
Shell sort, and the quick sort. The entry sort is a routine that is thor­
oughly discredited because it is extremely slow when compared with
the other routines. An entry sort orders the contents of an array in
place. The first entry in the array is compared with the remaining
entries and, if any array entry is smaller than the first, these values
are swapped. This operation is then repeated for the second entry in
the array followed by the third entry in the array until all entries in
the array are compared with all others. When this sequence is com­
pleted, the array is sorted. If there are n entries in the array, the first
scan involves n compares, the second involves n-1 compares, the
third n-2 and so forth. Therefore, the total number of compares is

n+(n-1)+(n-2)+...1
The value of this sum is n*(n-1)/2. In other words, the entry sort
2
requires on the order of n compares.
The Shell sort was discovered in 1959 by D. L. Shell. Like the
entry sort, the Shell sort orders the contents of an array in place. The
Shell sort splits the n-element array into two halves. The contents of
these two halves are compared entry-by-entry and, if the value in the
one half is larger than that in the other, the entries are swapped. These
arrays are then split again, and the contents of the four arrays are
scanned and ordered two at a time as above. Then the four arrays are
split into eight arrays and the scan and ordering operation is repeated
again. This operation of splitting the arrays and ordering the contents
is repeated until there are n/2 arrays of 2 elements each. After this
last scan and sort operation, the array is ordered.