// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // Simple external merge demonstration. // First in a series of three programs. // This version implements a standard 2-way mergsort on an external file. // Runs start at length 1 and double each time until the file is sorted. // This program only works if the number of records is a power of 2. #include #include using std::fstream; using std::ifstream; using std::ios; #include "book.h" // Return 2^x int pow2(int x) { int val = 1; for (int i=0; i= RecsPerBlock) { // page fault FS[fpindex].read((char*)&Array[fpindex], sizeof(E)*RecsPerBlock); if (!FS[fpindex]) { cout << "Error reading file!\n"; cout << readcnt << " blocks were read, and " << writecnt << " blocks were written\n"; exit(-1); } readcnt++; Posit[fpindex] = 0; } val = Array[fpindex][Posit[fpindex]++]; } // Write a record (in val) to the output file fpindex. // This supports buffered writing to the output file, one block at a time. void putout(int fpindex, E val) { Array[fpindex][Posit[fpindex]++] = val; if (Posit[fpindex] == RecsPerBlock) { // page fault FS[fpindex].write((char*)Array[fpindex], sizeof(E)*RecsPerBlock); writecnt++; Posit[fpindex] = 0; } } // First pass of merge sort. // Split input into two files. void pass1(int inindex, int outindex1, int outindex2, int numrecs) { E val; Posit[inindex] = RecsPerBlock; // Prime a read for (int i=0; i passrecs) { // exhausted first run putout(out1, val2); count2++; if (count2 <= passrecs) getnext(in2, val2); } else if (count2 > passrecs) { // exhausted second run putout(out1, val1); count1++; if (count1 <= passrecs) getnext(in1, val1); } else // Got records from each run still if (val1 < val2) { putout(out1, val1); count1++; if (count1 <= passrecs) getnext(in1, val1); } else { putout(out1, val2); count2++; if (count2 <= passrecs) getnext(in2, val2); } } swap(out1, out2); } // Done this pass, so flush output FS[in1].clear(); FS[in1].close(); FS[in2].clear(); FS[in2].close(); FS[out1].clear(); FS[out1].close(); FS[out2].clear(); FS[out2].close(); } rename(Name[out2], outname); } // Main routine. Get everything ready int main(int argc, char** argv) { if (argc != 3) { cout << "Usage: exmrg1 .\n"; exit(-1); } // Check the file size. It must be a multiple of the block size, // and a power of 2. long size; ifstream file (argv[1], ios::in|ios::binary); file.seekg (0, ios::end); size = file.tellg(); file.close(); cout << "size of " << argv[1]; cout << " is " << size << " bytes.\n"; if ((size % (sizeof(E)*RecsPerBlock)) != 0) { cout << "Error. File size must be a multiple of the block size.\n"; exit(-1); } int numrecs = size/sizeof(E); int i; for (i=1; i