tailieunhanh - Ebook Data structures and algorithm analysis in C++ (4th edition): Part 2

(BQ) Part 2 book "Data structures and algorithm analysis in C++" Programming: Sorting, the disjoint sets class, algorithm design techniques, amortized analysis, advanced data structures and implementation. | C H A P T E R 7 Sorting In this chapter, we discuss the problem of sorting an array of elements. To simplify matters, we will assume in our examples that the array contains only integers, although our code will once again allow more general objects. For most of this chapter, we will also assume that the entire sort can be done in main memory, so that the number of elements is relatively small (less than a few million). Sorts that cannot be performed in main memory and must be done on disk or tape are also quite important. This type of sorting, known as external sorting, will be discussed at the end of the chapter. Our investigation of internal sorting will show that. . . r There are several easy algorithms to sort in O(N2 ), such as insertion sort. r There is an algorithm, Shellsort, that is very simple to code, runs in o(N2 ), and is efficient in practice. r There are slightly more complicated O(N log N) sorting algorithms. r Any general-purpose sorting algorithm requires (N log N) comparisons. The rest of this chapter will describe and analyze the various sorting algorithms. These algorithms contain interesting and important ideas for code optimization as well as algorithm design. Sorting is also an example where the analysis can be precisely performed. Be forewarned that where appropriate, we will do as much analysis as possible. Preliminaries The algorithms we describe will all be interchangeable. Each will be passed an array containing the elements; we assume all array positions contain data to be sorted. We will assume that N is the number of elements passed to our sorting routines. We will also assume the existence of the “” operators, which can be used to place a consistent ordering on the input. Besides the assignment operator, these are the only operations allowed on the input data. Sorting under these conditions is known as comparison-based sorting. This interface is not the same as in the STL sorting algorithms. In the STL, sorting .