For each of the 5

sorting applications below, provide

• a link to an authoritative website that illustrates a strong example of the sorting application

and

• the reason you picked that website in particular as a strong example of the sorting application

1. Commercial computing. Government organizations, financial institutions, and commercial enterprises organize much of this information by sorting it. Whether the information is accounts to be sorted by name or number, transactions to be sorted by time or place, mail to be sorted by postal code or address, files to be sorted by name or date, or whatever, processing such data is sure to involve a sorting algorithm somewhere along the way.
2. Search for information. Keeping data in sorted order makes it possible to efficiently search through it using the classic binary search algorithm.
3. Operations research. Suppose that we have N jobs to complete, where job j requires t_j seconds of processing time. We need to complete all of the jobs, but want to maximize customer satisfaction by minimizing the average completion time of the jobs. The shortest processing time first rule, where we schedule jobs in increasing order of processing time, is known to accomplish this goal. As another example, consider the load-balancing problem, where we have M identical processors and N jobs to complete, and our goal is to schedule all of the jobs on the processors so that the time when the last job completes is as early as possible. This specific problem is NP-hard (see Chapter 6) so we do not expect to find a practical way to compute an optimal schedule. One method that is known to produce a good schedule is the longest processing time first rule, where we consider the jobs in decreasing order of processing time, assigning each job to the processor that becomes available first.
4. Event-driven simulation. Many scientific applications involve simulation, where the point of the computation is to model some aspect of the real world in order to be able to better understand it. Doing such simulations efficiently can require appropriate algorithms and data structures. We consider a particle-collision simulation in Section 6.1 that illustrates this point.
5. Numerical computations. Scientific computing is often concerned with accuracy (how close are we to the true answer?). Accuracy is extremely important when we are performing millions of computations with estimated values such as the floating-point representation of real numbers that we commonly use on computers. Some numerical algorithms use priority queues and sorting to control accuracy in calculations.