We have consistently viewed the record as the basic unit of data. Collections of records usually appear in problems, and their processing typically reduces to traversing through the records of the collection, inserting or deleting records, randomly accessing records, accessing records in sorted order, or searching the collection for a given record. The basic data structures are available for storage of the collection, and each supports some operations well at the expense of others. Arrays are excellent for random access and traversal but poor for general insertions and deletions. Lists support traversal, insertions, and deletions well but are poor for random access.
Linear searches of arrays and binary searches of sorted arrays can be performed, respectively, in O(n) and O(1g n) time. Under special conditions, linear searches can be fast.
Simple sorting algorithms such as the bubble and insertion sort have worst-case time O(n2) but are O(n) when dealing with almost sorted data. Quicksort gives very fast average times and heapsort does sorting in worst-case time O(n 1g n).
* These results were produced by Sharon Doherty.
It is important to recognize that in this chapter we have been considering comparative searches and sorts. This means that we have assumed no special knowledge of the key values involved and have used only comparisons between key values in each search or sort algorithm. It is possible to prove that such searches and sorts have worst-case times O(lg n) and O(n lg n), respectively.
Other kinds of search and sort algorithms are possible. Some may take significantly less time. For example, suppose you must sort n distinct keys whose values are known to be integers between 1 and 1,000. Simply store the record with key value i as the ith record in an array of records. This places the records in the array in (decreasing) sorted order and takes O(n) time. Sorts that place records in groups, depending on their actual key values, and then attempt to sort further within the groups, are called distributive sorts. These are not considered in this text. We will, however, consider a very important noncomparative search in Section 9.3.
Simulation is a basic tool for the analysis of the storage and timing requirements of algorithms although we have used it only for analyzing sorts.
As searching as this chapter may have been, it is hoped that it didn't leave you out of sorts!
Table 8.1 Simulation Results in Actual Execution Time (milliseconds)*
n Bubble Sort Insertion Sort Modified Insertion Sort
-----------------------------------------------------------------------------------------------------------
10 1 2 6 8 9 1 2 5 7 7 0 2 4 6 9
20 1 8 23 33 36 1 5 16 28 30 1 6 17 25 30
40 2 31 101 138 148 2 16 67 110 121 5 16 65 107 120
100 4 217 646 863 923 7 89 412 678 761 6 87 402 660 744
200 8 966 2653 3463 3724 12 364 1657 2706 3058 11 354 1612 2639 2993
400 17 3933 11277 14732 15858 24 1583 7645 12489 14595 20 1373 6352 10581 12157
-----------------------------------------------------------------------------------------------------------
srt'd half rnd'm half rev srt'd half rnd'm half rev srtd half rndm half rev
srt'd rev srt'd srt'd rev srt'd srt'd rev srt'd
half srt'd half srt'd half srt'd
rnd'm half rnd'm half rnd'm half
rnd'm rnd'm rnd'm
n Heapsort Iterative Quicksort Recursive Quicksort
-----------------------------------------------------------------------------------------------------------
10 9 9 8 8 7 10 9 9 8 10 5 5 3 3 4
20 18 19 18 18 15 21 19 15 17 23 13 11 10 11 14
40 43 43 41 40 37 51 47 33 38 55 35 31 21 25 36
100 130 126 122 119 115 196 171 94 106 202 156 133 65 74 158
200 291 282 277 264 256 626 521 202 231 633 581 484 149 169 602
400 640 624 610 587 572 2175 1750 432 492 2195 2042 1644 318 372 2056
-----------------------------------------------------------------------------------------------------------
srt'd half rnd'm half rev srt'd half rnd'm half rev srtd half rndm half rev
srt'd rev srt'd srt'd rev srt'd srt'd rev srt'd
half srt'd half srt'd half srt'd
rnd'm half rnd'm half rnd'm half
rnd'm rnd'm rnd'm
-----------------------------------------------------------------------------------------------------------