Why so much attention to sorting? Sorting is the process of ordering a set of items. The two most common orderings are ascending order and descending order. In the context of data structures, it is the process of arranging nodes in an order based on the contents of one of the fields in the nodes.
For example, the nodes that comprise a collection of telephone listings are usually sorted in ascending order based on the contents of the name field, while the results of a weight-lifting contest would possibly be sorted in descending order based on the contents of the maximum weight lifted field.
Most often, nodes are sorted for one of two reasons:
When nodes are output in sorted order, not only are they more pleasant to read, but it is also much easier to find a particular listing from among the printed listings. Drawing conclusions based on the data presented in sorted order often becomes self-evident. Consider again the output listing of a weight-lifting contest that is sorted based on the maximum weight lifted field. It would be obvious who won the competition because the analysis necessary to determine the winner is the sorting process itself.
Often the speed of the fetch method can be improved if the data set is stored in a sorted order. Consider the binary search algorithm to locate a node which is an efficient, O(log2n), search algorithm. Thus, even if the data set is never output in sorted order, sorting algorithms are important because they can speed up one or more of the basic operations performed on a data set.
The additional time needed to sort can be held to acceptable levels through the use of efficient sorting algorithms and good sorting strategies. As an example of a sorting strategy, consider the following scenario.
When a data set is to be output in sorted order, two alternatives are available: sort the nodes just prior to outputting them, or store the nodes in the data set in a sorted order. The former approach is attractive if the nodes are rarely output in sorted order, or if the field on which the nodes are sorted changes often. If, however, the nodes are often output in sorted order, then it may be more efficient to store the nodes in sorted order, especially if the contents of the field on which they are sorted rarely changes.
You are studying several of the classic sorting algorithms and examine the advantages of each. Some of the algorithms require more memory than others, while some execute faster than others. It can be shown, however, that there is a theoretical minimum number of comparisons required to sort a set of n items. That's a fair standard for goodness when analyzing the performance of the algorithms presented in Chapter 8. Some data sets exhibit special characteristics that allow some sorting algorithms to perform faster than the theoretical minimum.
Aside from speed and memory differences, some of the algorithms are much easier to code than others. Thus, the selection of the best sorting algorithm for a particular application is usually based on the speed and memory constraints of the application, the nature of the data set being sorted, and the coding skills of the programmer.
When you work in the industry, you will sometimes deal with huge data sets. Examples from banking are easy to comprehend and are often used. Let's, however, consider the engineering world. Applications that work day and night, like traffic lights at the intersection, deal with just a few images from the cameras to calculate who will be giving green light at the next switch. On the other hand, a large automated weather-forecasting system (similar other real-time artificial intelligence systems) needs to quickly sort millions of values produced by radars and satellite cameras.
When this algorithm is presented with an array of primitive values or an array of object references, the primitive values or the references are swapped within the array. Thus, the only extra storage required to perform the algorithm is one extra memory cell (temp), used in the classic swapping algorithm, temp = items[t]; items[t] = items[b]; items[b] = temp;
The memory overhead of this algorithm is the lowest overhead of the sorting algorithms discussed in Chapter 8.
The memory overhead associated with this sorting algorithm is essentially the storage associated with the n element temporary array. Each of its elements stores either a primitive value (the items being sorted) or a reference to the objects being sorted. It means the overhead with be n times higher than that found for Bubble Sort.
Storage is required to keep track of the ends of the partitions. Considering the number of passes needed, as explained in your textbook, the storage amount would be in the order of O(log2n).
The sort classes to be used in this assignment are AT LEAST THREE of the following:
It should be clear from the names of your classes which sort classes you chose to use.
For each sort method, the output should clearly indicate the numbers of comparisons and exchanges.
Use the random number function to store a list of 1000 pseudorandom integer values in an array. Apply each of the sort classes described in this chapter to the array and determine the number of comparisons and exchanges. Make sure the same array is passed ot each sort method.
Investigate the effect of array size and initial element order on the number of comparisons and exchanges required by each of the sorting algorithms described in this chapter. Use arrays with 100 and 10,000 integers. Use three initial orderings of each array (randomly ordered, inversely ordered, and ordered). Be certain to sort the same six arrayx with each sort method.