A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạmNội dung chi tiết: A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 Bridge; bills and other piles of paper; jars of spices; and so on. And we have many intuitive strategics that we can use to do the sorting, depending on how many objects we have to sort and how hard they arc to move around. Sorting is also one of the most frequently performed computing tasks. We mig A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 ht sort the records in a database so that we can search the collection efficiently. We might sort the records by zip code so that we can print and maiA practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
l them more cheaply. We might use sorting as an intrinsic part of an algorithm to solve some other problem, such as when computing the minimum-cost sp____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 of these algorithms are straightforward adaptations of schemes we use in everyday life. Others are totally alien to how humans do things, having been invented to sort thousands or even millions of records stored on the computer. After years of study, there are still unsolved problems related to sort A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 ing. New algorithms are still being developed and relined for specialpurpose applications.While introducing this central problem in computer science,A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
this chapter has a secondary purpose of illustrating issues ill algorithm design and analysis. For example, this collection of sorting algorithms show____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 ort divides a list into big values anil small values; and Radix Sori divides the problem by working on one digil of the key al a time. Sorting algorithms can also illustrate a wide variety of analysis techniques. Weil find that il is possible for an algorithm to have an average case whose growth rat A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 e is significantly smaller than ils worse case (Quicksort). We’ll sec how it is possible to speed up sorting algorithms (both Shellsort and Quicksort)A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
by taking advantage of the best case behavior of another algorithm (Insertion sort). We’ll see several examples of how we can tune an algorithm for b____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 applications (Heapsort). Sorting provides an example of a significant technique for analyzing the lower bound for a problem. Sorting will also be used to motivate the introduction to tile processing presented in Chapter 8.The present chapter covers several standard algorithms appropriate for sorting A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 a collection of records that fit in the computer's main memory. It begins with a discussion of three simple, but relatively slow, algorithms requirinA practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
g 0(n2) time in the average and worst eases. Several algorithms with considerably better performance arc then presented, some with 0(n logn) worst-eas____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 t sorting in general requires Q(n logn) time in the worst ease.7.1 Sorting Terminology and NotationExcept where noted otherwise, input to the sorting algorithms presented in this chapter is a collection of records stored in an array. Records arc compared to one another by means of a comparator class A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 , as introduced in Section 4.4. To simplify the discussion we will assume that each record has a key field whose value is extracted from the record byA practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
the comparator. The key method of the comparator class is prior, which returns true when its first argument should appear prior to its second argumen____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 fscc the Appendix).Given a set of records rlt r’2.r„ with key values fcj. k2.A'„, the SortingProblem is to arrange the records into any order .s such that records ..... r*n have keys obeying the property fcj, < fc,2 < ... < In other words, the sorting problem is to arrange a set of records so that t A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 he values of their key fields arc in non-decreasing order.As defined, the Sorting Problem allows input with two or more records that have the same keyA practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
value. Certain applications require that input not contain duplicate key values. The sorting algorithms presented in this chapter and in Chapter 8 ca____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 ically based on their order of occurrence within the input. It might be desirable to maintain this initial ordering among duplicates. A sorting algorithm is said to be stable if it docs not change the relative ordering of records with identical key values. Many, but not all. of the sorting algorithm A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 s presented in this chapter arc stable, or can be made stable with minor changes.When comparing two sorting algorithms, the most straightforward approA practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
ach would seem to be simply program both and measure their running times. An example of such timings is presented in Figure 7.20. However, such a comp____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 ut values. In particular, the number of records, the size of the keys and the records, the allowable range of the key values, and the amount by which the input records arc "out of order” can all greatly affect the relative running times for sorting algorithms.When analyzing sorting algorithms, it is A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 traditional to measure the number of comparisons made between keys. This measure is usually closely related to the running time for the algorithm andA practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
has the advantage of being machine and datatype independent. However, in some eases records might be so large that their physical movement might take____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 In most applications we can assume that all records and keys arc of fixed length, and that a single comparison or a single swap operation requires a constant amount of time regardless of which keys arc involved. Some special situations "change the rules" for comparing sorting algorithms. For exampl A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 e, an application with records or keys having widely varying length (such as sorting a sequence of variable length strings) will benefit from a speciaA practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
l-purpose sorting technique. Some applications require that a small number of records be sorted, but that the sort be performed frequently. An example____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 in an asymptotic analysis now become crucial. Finally, some situations require that a sorting algorithm use as little memory as possible. We will note which sorting algorithms require significant extra memory beyond the input array.7.2 Three e(n2) Sorting AlgorithmsThis section presents three simple A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 sorting algorithms. While easy to understand and implement, we will soon see that they are unacceptably slow when there are many records to sort. NonA practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
etheless, there are situations where one of these simple algorithms is the best tool for the job.7.2.1 Insertion SortImagine that you have a stack of ____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing B A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 s and put them in order. Then take the third bill and put it into the right order with respect to the first two, and so on. As you take each bill, you would add it to the sorted pile that you have already made. This naturally intuitive process is the inspiration for our first sorting algorithm, call A practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2 ed Insertion Sort. Insertion Sort iterates through a list of records. Each record is inserted in turn at the correct position within a sorted list comA practical introduction to data structures and algorithm analysis (edition 3 2 c++ version) part 2
posed of those records already processed. The234Chap. 7 Internal Sortingi = 123456o20* 4217* 2013 1713 17*13 1413 141717 J4220 _201717*13 2813 2813—I ____________PA RT 111____________Sorting and Searching2297Internal SortingWc sort many things in our everyday lives: A handful of cards when playing BGọi ngay
Chat zalo
Facebook