tailieunhanh - Thuật toán Algorithms (Phần 18)

Tham khảo tài liệu 'thuật toán algorithms (phần 18)', 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ả | EXTERNAL SORTING 163 exactly after the sort phase is completed The best choice between these two alternatives of the lowest reasonable vaiue of P and the highest reasonable value of P is obviously very dependent on many systems parameters both alternatives and some in between should be considered. Polyphase Merging One problem with balanced multiway merging for tape sorting is that it requires either an excessive number of tape units or excessive copying. For P-way merging either we must use 2P t ipes P for input and P for output or we must copy almost all of the file from a single output tape to P input tapes between merging passes which effectively doubles the number of passes to be about tape-sorting algorithms have been invented which eliminate virtually all of this copying by changing the way in which the small sorted blocks are merged together. The most prominent of these methods is called polyphase merging. The basic idea behind polyphase merging is to distribute the sorted blocks produced by replacement selection somewhat unevenly among the available tape units leaving one empty and then to apply a merge until empty strategy at which point one of the output tapes and the input tape switch roles. For example suppose that we have just three tapes and we start out with the following initial configuration of sorted blocks on the tapes. This comes from applying replacement selection to our example file with an internal memory that can only hold two records. Tape 1 A 0 R S T Tape 2 E G X A M Tape S IN AGN DEMR GIN PEL After three 2-way merges from tapes 1 and 2 to tape 3 the second tape becomes empty and we are left with the configuration T ape l DEMR G IN Tape Tape 3 AEG0RSTXAIMNP AEGLN Then after two 2-way merges from tapes 1 and 3 to tape 2 the first tape becomes empty leaving Tape 1 Tape ODEEGMORRSTXAGIIMNNP Tape 5 A E G L N 164 CHAPTER 13 The sort is completed in two more steps. First a two-way merge from tapes 2 and 3 to tape 1 leaves one file on tape 2 one