Tham khảo tài liệu 'thuật toán algorithms (phần 11)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | ELEMENTARY SORTING METHODS 93 small index to each key before sorting or by lengthening the sort key in some other way. It is easy to take stability for granted people often react to the unpleasant effects of instability with disbelief. Actually there are few methods which achieve stability without using significant extra time or space. The following program for sorting three records is intended to illustrate the general conventions that we ll be using. In particular the main program is a peculiar way to exercise a program that is known to work only for N 3 the point is that most of the sorting programs we ll consider could be substituted for sort3 in this driver program. program threesort input output const maxN- 100- var a array of integer N i integer procedure sort3 var integer begin if a t a 2 then begin t a l a l a 2 a 2 t end if then begin t a t a l a 3 a 3 t end if then begin end end begin readin N for i l to N do read a i if then for to N do wri end. The three assignment statements following each if actually implement an exchange operation. We ll write out the code for such exchanges rather than use a procedure call because they re fundamental to many sorting programs and often fall in the inner loop. In order to concentrate on issues we ll work with algorithms that simply sort arrays of integers into numerical order. It is generally straightforward to adapt such algorithms for use in a practical application involving large keys or records. Basically sorting programs access records in one of two ways either keys are accessed for comparison or entire records are accessed 94 CHAPTER 8 to be moved. Most of the algorithms that we will study can be recast in terms of performing these two operations on arbitrary records. If the records to be sorted are large it is normally wise to do an indirect sort here the records themselves are not necessarily rearranged but rather an array of pointers or indices is rearranged so that the first pointer points to the .
