// 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. // Third in a series of three programs. // This version implements a k-way mergsort on an external file. // Like exmrg2 it begins by building a large initial run using quicksort. // After the initial run has been created (with working memory size // determined by a command line parameter), a series of k-way merge // passes is used to combine the runs together. #include using std::fstream; using std::ifstream; using std::ios; #include "book.h" #define BIGKEY 600000000L // HACK!! #include "compare.h" const int THRESHOLD=0; template void inssort(E A[], int n) { // Insertion Sort for (int i=1; i0) && (Comp::prior(A[j], A[j-1])); j--) swap(A, j, j-1); } template inline int findpivot(E A[], int i, int j) { return (i+j)/2; } template inline int partition(E A[], int l, int r, E& pivot) { do { // Move the bounds inward until they meet while (Comp::prior(A[++l], pivot)); // Move l right and while ((l < r) && Comp::prior(pivot, A[--r])); // r left swap(A, l, r); // Swap out-of-place values } while (l < r); // Stop when they cross return l; // Return first position in right partition } template void qsort(E array[], int i, int j) { if ((j-i) <= THRESHOLD) return; // Don't sort short list int pivotindex = findpivot(array, i, j); swap(array, pivotindex, j); // stick pivot at end int k = partition(array, i-1, j, array[j]); swap(array, k, j); // Put pivot value in place qsort(array, i, k-1); qsort(array, k+1, j); } // Return 2^x int pow2(int x) { int val = 1; for (int i=0; i(array, 0, n-1); inssort(array, n); // Cleanup sort } // First pass of merge sort. // Split input into two files. void pass1(char* inname, int numruns, E* BigArray, int memsize) { int memblocks = memsize/(sizeof(E) * RecsPerBlock); fstream infile; fstream outfile; infile.open(inname, ios::in | ios::binary); if (!infile) cout << "Error opening " << infile << endl; outfile.open("temp", ios::out | ios::binary); if (!outfile) cout << "Error opening " << "temp" << endl; for (int i=0; i1; i=i/numblocks) numpass++; // Now do the passes char* onename = "temp"; char* twoname = outname; // Space to store the current run positions int* Posit = new int[numblocks]; // Which record of this block we are on int* Count = new int[numblocks]; // Which block of the run we are on for(int i=0; i .\n"; cout << "Numblocks is the size of the file in blocks.\n"; cout << "Blocksize is " << RecsPerBlock * sizeof(E) << " bytes.\n"; cout << "Memsize is the size of working memory, measured in blocks.\n"; exit(-1); } // Check the file size. It must be a multiple of the block size. 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] << " 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); } // There must be at least two blocks in the working memory, and the // number of blocks in the file must be a power of the number of blocks // in the working memory. int numrecs = size/sizeof(E); int workingblocks = atoi(argv[3]); int memsize = workingblocks * RecsPerBlock * sizeof(E); if (workingblocks < 2) { cout << "Error: Working memory size must be at least two blocks\n"; exit(-1); } if (size < memsize) memsize = size; int fileblocks = numrecs/RecsPerBlock; cout << "workingblocks is " << workingblocks << ", fileblocks is " << fileblocks << endl; for (mycnt=workingblocks; mycnt