Page 251 - Programming Microcontrollers in C
P. 251
236 Chapter 5 Programming Large 8-Bit Systems
If it is, max_depth is replaced by depth. depth is reset to zero
prior to returning through the end of the quick_sort() routine.
The result of this program is as follows:
3 18 23 27 77 81 99 128 360 550 808
calls=15
max_depth=4
To sort the above 11 element array, the program called
quick_sort() 15 times and the maximum number of stack frames
that were created at one time was four. Each stack frame consists of
four bytes for data and two bytes for the return address. Therefore, at
one time in the execution of this program, the sort routine required
24 bytes of stack space in addition to the memory area required to
hold the array being sorted. This is distressing when you remember
that the array is 22 bytes long!
Careful analysis of the program will show that the expected
maximum number of stack frames for the quick sort is proportional to
ln n. Therefore, the stack frame performance will get better when the
2
size of the array is larger. The main problem with the use of any recursive
routine is that you do not know exactly the number of stack frames
needed and therefore you must always analyze the maximum stack
frame depth and allow that amount of stack for execution of the function.
The quick sort is faster than the Shell sort under most—but not
all—circumstances. Let’s take the example of having a quick sort and
a Shell sort compiled to run under the same host computer. If larger
arrays are used to do the measurement and random arrays are used, we
will find that the sort time for both quick sort and Shell sort depends
on the array. The reason for this difference is the number of swap
routines that must be executed during the sort operation. Therefore,
there will be some arrays that the Shell sort will sort quicker that the
quick sort. However, the quick sort is usually faster than the Shell sort.
The Shell sort is every bit as flexible as the quick sort and can be
used to sort different types, character strings, and swap pointers rather
than swap the objects being sorted. Therefore, in a microcontroller
application where memory is always limited, you should use a Shell
sort rather than a quick sort because the Shell sort has no funny
memory requirements that will always occur with a recursive routine
like the quick sort.