Tham khảo tài liệu 'lập trình c# all chap "numerical recipes in c" part 6', công nghệ thông tin phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chapter 8. Sorting Introduction This chapter almost doesn t belong in a book on numerical methods. However some practical knowledge of techniques for sorting is an indispensable part of any good programmer s expertise. We would not want you to consider yourself expert in numerical techniques while remaining ignorant of so basic a subject. In conjunction with numerical work sorting is frequently necessary when data either experimental or numerically generated are being handled. One has tables or lists of numbers representing one or more independent or control variables and one or more dependent or measured variables. One may wish to arrange these data in various circumstances in order by one or another of these variables. Alternatively one may simply wish to identify the median value or the upper quartile value of one of the lists of values. This task closely related to sorting is called selection. Here more specifically are the tasks that this chapter will deal with Sort . rearrange an array of numbers into numerical order. Rearrange an array into numerical order while performing the corresponding rearrangement of one or more additional arrays so that the correspondence between elements in all arrays is maintained. Given an array prepare an index table for it . a table of pointers telling which number array element comes first in numerical order which second and so on. Given an array prepare a rank table for it . a table telling what is the numerical rank of the first array element the second array element and so on. Select the Mth largest element from an array. For the basic task of sorting N elements the best algorithms require on the order of several times N log2 N operations. The algorithm inventor tries to reduce the constant in front of this estimate to as small a value as possible. Two of the best algorithms are Quicksort invented by the inimitable . Hoare and Heapsort invented by . Williams. For large N say 1000 Quicksort is .
