Java Reference
In-Depth Information
4096 bytes in size, with the first 4 bytes used to store the block ID corre-
sponding to that buffer. Use the first
BufferPool
abstract class given in
Section 8.3 as the basis for your implementation.
8.4 Implement an external sort based on replacement selection and multiway
merging as described in this chapter. Test your program both on files with
small records and on files with large records. For what size record do you
find that key sorting would be worthwhile?
8.5 Implement a Quicksort for large files on disk by replacing all array access in
the normal Quicksort application with access to a virtual array implemented
using a buffer pool. That is, whenever a record in the array would be read or
written by Quicksort, use a call to a buffer pool function instead. Compare
the running time of this implementation with implementations for external
sorting based on mergesort as described in this chapter.
8.6 Section 8.5.1 suggests that an easy modification to the basic 2-way mergesort
is to read in a large chunk of data into main memory, sort it with Quicksort,
and write it out for initial runs. Then, a standard 2-way merge is used in
a series of passes to merge the runs together. However, this makes use of
only two blocks of working memory at a time. Each block read is essentially
random access, because the various files are read in an unknown order, even
though each of the input and output files is processed sequentially on each
pass. A possible improvement would be, on the merge passes, to divide
working memory into four equal sections. One section is allocated to each
of the two input files and two output files. All reads during merge passes
would be in full sections, rather than single blocks. While the total number
of blocks read and written would be the same as a regular 2-way Mergesort, it
is possible that this would speed processing because a series of blocks that are
logically adjacent in the various input and output files would be read/written
each time. Implement this variation, and compare its running time against
a standard series of 2-way merge passes that read/write only a single block
at a time. Before beginning implementation, write down your hypothesis on
how the running time will be affected by this change. After implementing,
did you find that this change has any meaningful effect on performance?
