Write your own collection of sorting programs to implement the algorithms described in this chapter, and compare their running times. Be sure to implement optimized versions, trying to make each program as fast as possible.

Do you get the same relative timings as shown in Figure 7.13? If not, why do you think this happened? How do your results compare with those of your classmates? What does this say about the difficulty of doing empirical timing studies?

Transcribed Image Text:

Sort 10 10K 1M 100 1K Insertion .00023 .007 0.66 Up 100K 64.98 7381.0 674420 0.04 .00035 .020 2.25 277.94 27691.0 2820680 70.64 Selection .00039 .012 0.69 72.47 7356.0 Shell Bubble 780000 69.76 .00034 .008 0.14 1.99 0.44 Shell/O .00034 .008 0.12 1.91 0.36 Merge 1.61 0.83 .00050 .010 0.12 Merge/O .00024 .007 0.10 1.31 0.47 Quick 1.37 0.37 .00048 .008 0.11 .00031 .006 0.09 Quick/O 1.14 143 0.32 .00050 .011 0.16 2.08 391 1.57 334 1.01 808 7.97 404 4.00 Heap Heap/O .00033 .007 0.11 Radix/4 .00838 .081 0.79 Radix/8 .00799 .044 0.40 1.61 7.99 3.99 30.2 29.0 19.3 17.2 15.7 13.6 26.7 20.8 79.9 40.0 554 530 219 197 162 Down 129.05 108.69 69.58 0.79 0.64 0.79 0.66 0.40 0.36 1.56 1.04 7.97 3.99