C++ only. Need .h, implementation.cpp and maindrive.cpp files

PROBLEM STATEMENT: A review and extension of cs132:sort a file with 120 records. However, due to memory restrictions only 20 records may be placed into memory. You are to implement "quasi" external sort

CODE/DIRECTIONS: For the sake of simplicity, and without much loss of generality, we will say for this lab are records are just ints : thus sort a file with 120 ints where only 20 ints maybe placed into memory at any one time

general idea: break data into blocks, sort blocks into runs, merge runs

less general idea: Call inFile1 our source file ( the one with the initial 120 records to be sorted.)

You will also need an inFile2, and 2 other files outFile1 and outFile2.

Break the file into blocks of size 20: in this case there will be 6 blocks ( 120/20 )

Sort the blocks by read a block, sort it, store in outFile1 read a block, sort it, store in outFile2 read a block, sort it, store in outFile1 ( in other words, sort a block and alternately place in the files outFile1, outFile2 )

By definition, a run is a sorted block Note that each file outFile1 and outFile2 will have half of the runs

Merge the runs:

Merge data from outFile1 and outFile2 to inFile1 and inFile2.

Merge the first run on outFile1 and the first run on outFile2, and store the result on inFile1: Read two records in main memory, compare, store the smaller on inFile1

Read the next record from either outFile1 or outFile2 the file that had its record moved/stored to inFile1

Similarly, merge the second run on outFile1 and the second run on outFile2, store the result on inFile2. Merge the third run on outFile1 and the third run on outFile2, store the result on inFile1... etc, merging each run and storing the result alternatively on inFile1 and inFile2.

At the end inFile1 and inFile2 will contain sorted runs twice the size of the previous runs on outFile1 and outFile2 Now merge data from inFile1 and inFile2 to outFile1 and outFile2. Merge the first run on inFile1 and the first run on inFile2, and store the result on outFile1. Merge the second run on inFile1 and the second run on inFile2, store the result on outFile2 Etc, merge and store alternatively on inFile1 and inFile2. Repeat the process until only one run is obtained. This would be the sorted file

Must use above algorithm.

MUST use algorithms from sort_algorithms.t:

the algorithms may not be modified. - but you may assume an overloaded < operator exists. Thus you may remove the pointer to the function cmp ( obviously, the code will have to replace any reference to cmp, no puns intended, with < ) It is permissible to copy/paste any algorithms from sort_algorithms.t that you use to your own sort_alg.t Declare a variable MAX_MEM_SIZE, of type size_t. Initialize to 20 If you are really paying attention to the directions, you will realize that 2 arrays of 20 cannot both be in memory at the same time depending on how you implement the above algorithm and which sort you use, you may need to break into blocks of size 10 a sample file to be sorted is provided.

data.txt

15437 5579 30403 20723 15051 1275 31856 3192 20446 26400 2346 1804 20246 10454 24880 5574 5060 26748 22640 28586 8296 26589 3486 19567 21101 16655 23428 24710 32276 25244 29849 23127 1711 5856 23764 17614 18191 6834 13762 29462 24127 1863 4311 22948 13427 4946 15362 30840 19515 28528 15491 15007 13308 16836 27649 28413 11169 1246 27607 15945 21134 19938 25264 16985 29141 15846 14419 8864 13997 8859 17344 23029 28960 2608 8059 2453 11011 20083 6184 32108 11051 23354 26968 17808 14558 13313 15523 2319 13192 31956 7927 30186 21167 2672 24623 29281 8745 15781 4327 29553 3725 11774 4751 7324 5607 26532 28095 3304 28848 16512 25290 32042 18173 2208 26774 4996 17910 6620 3499 1

template void swap( T &a, T &b ) { T temp = a;

a = b; b = temp; }

template void selectSort( T* arrayptr, int arraySize, bool ( *cmp )( T &baseData1, T &baseData2 ) ) { int smallindex; // index of smallest element in the sublist int pass, j;

// pass has the range 0 to n-2 for ( pass = 0; pass < arraySize - 1; pass++ ) { // scan the sublist starting at index pass smallindex = pass;

// j traverses the sublist arrayptr[pass+1] to aarrayptr[n-1] for ( j = pass + 1; j < arraySize; j++ ) // update if smaller element found if ( cmp ( arrayptr[j], arrayptr[smallindex] ) ) smallindex = j;

// when finished, exchange smallest item with arrayptr[pass] swap( arrayptr[pass], arrayptr[smallindex] ); } }

template void doubleSeletcSort( T* arrayptr, int arraySize, bool ( *cmp )( T &baseData1, T &baseData2 ) ) { // index of smallest and largest elements in a sublist int smallIndex, largeIndex; int i, j, k; T temp;

// start indices i = 0; j = arraySize - 1; // as long as i < j while (i < j) { // scan the sublist {arrayptr[i], ..., arrayptr[j]} smallIndex = i; largeIndex = i;

// k traverses the sublist {arrayptr[i+1], ..., arrayptr[j]} for (k = i+1; k <= j; k++) // update if smaller element found if ( cmp( arrayptr[k], arrayptr[smallIndex] ) ) smallIndex = k; // update if larger element found else if ( cmp( arrayptr[largeIndex], arrayptr[k] ) ) largeIndex = k;

// if smallIndex and i are not the same location, // swap smallest item in the sublist with arrayptr[i] if (smallIndex != i) { swap( arrayptr[i], arrayptr[smallIndex] );

// at index i, arrayptr[i] maybe largest element // if so, swap moves the largest value to index smallIndex if (largeIndex == i) largeIndex = smallIndex; }

// if largeIndex and j are not the same location, // swap largest item in the sublist with arrayptr[j] if (largeIndex != j) { swap( arrayptr[j], arrayptr[largeIndex] ); }

// move i forward and j backward i++; j--; } }

template void insertionSort( T* arrayptr, int arraySize, bool ( *cmp )( T &baseData1, T &baseData2 ) ) { int i, j; T target;

// place arrayptr[i] into the sublist // arrayptr[0] ... arrayptr[i-1], 1 <= i < n, // so it is in the correct position for (i = 1; i < arraySize; i++) { // index j scans down list from arrayptr[i] looking for // correct position to locate target. assigns it to // arrayptr[j] j = i; target = arrayptr[i]; // locate insertion point by scanning downward as long // as target < arrayptr[j-1] and we have not encountered the // beginning of the list while (j > 0 && target < arrayptr[j-1]) { // shift elements up list to make room for insertion arrayptr[j] = arrayptr[j-1]; j--; } // the location is found; insert target arrayptr[j] = target; } }

template void bubbleSort( T* arrayptr, int arraySize, bool ( *cmp )( T &baseData1, T &baseData2 ) ) { register int i,j; // index of last exchange bool did_swap = true;

// i is the index of last element in the current sublist i = arraySize - 1;

// continue the process until we make no exchanges or // we have made n-1 passes while ( i > 0 && did_swap ) { // assume no exchange occurs did_swap = false;

// scan the sublist arr[0] to arr[i] for ( j = 0; j < i; j++ ) // exchange a pair and assign true to exchangeOccurs if ( cmp( arrayptr[j + 1], arrayptr[j] ) ) { swap( arrayptr[ j ], arrayptr[ j+1 ] ); did_swap = true; } // move i downward one element i--; } }

template void basicBubbleSort( T* arrayptr, int arraySize, bool ( *cmp )( T &baseData1, T &baseData2 ) ) { register int i,j;

for ( i = 1; i < arraySize; i++ ) { for ( j = arraySize - 1; j >= i; j-- ) { if ( cmp( arrayptr[ j ], arrayptr[ j - 1 ] ) ) swap( arrayptr[ j -1 ] , arrayptr[ j ] ); }

}

}

template void mergesort1(T* arrayptr, const int& arraySize ) { sortmerge1( arrayptr, arraySize, 0, arraySize - 1 ); }

template void sortmerge1( T* arrayptr, const int& arraySize, int l, int r ) {

int mid, i, j, k;

if ( l < r ) { mid = (r + l)/2;

sortmerge1( arrayptr, arraySize, l, mid ); sortmerge1( arrayptr, arraySize, mid + 1, r );

T* temp = new T[ arraySize ];

for ( i = mid + 1; i > l; i-- ) temp[ i - 1 ]= arrayptr[ i - 1 ];

for ( j = mid; j < r; j++ ) temp[ r + mid - j ] = arrayptr[ j + 1 ];

for ( k = l; k <= r; k++) arrayptr[k] = ( temp[i] < temp[j] ) ? temp[i++] : temp[j--];

}

temp = 0; delete [] temp; }

template void msSort( T* arrayptr, const int& arraySize ) {

T* copy = new T[ arraySize ]; int i; for ( i = 0; i < arraySize; i++ ) copy[i] = arrayptr[i];

mergesort2( copy, arrayptr, 0, arraySize - 1 );

}

template void mergesort2( T* source, T* dest, int l, int r ) {

if ( l != r ) { int mid = ( l + r )/2; mergesort2( dest, source, l, mid ); mergesort2( dest, source, mid + 1, r ); merge2( source, dest, l, mid, r ); }

}

template void merge2( T* source, T* arrayptr , int l, int mid, int r ) {

int i = l; int j = mid + 1; int k = l;

while ( ( i <= mid ) && ( j <= r ) ) // Compare current item from each list if ( source[ i ] < source[ j ] ) // Then i item comes first arrayptr[ k++ ] = source[ i++ ]; else // j item comes first arrayptr[ k++ ] = source[ j++ ]; // Move what is left of remaining list if ( i > mid ) while ( j <= r ) arrayptr[ k++ ] = source[ j++ ]; else while (i <= mid ) arrayptr[ k++ ] = source[ i++ ]; }

#endif