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.
   246   247   248   249   250   251   252   253   254   255   256