MUST USE C++ AND ONLY USE THE ALGORITHMS LISTED

sort_algorithms.t

#ifndef SORT_ALGORITHMS_T__ #define SORT_ALGORITHMS_T__

#include #include #include using std::fstream; using std::streampos;

#include using std::ios; using std::endl;

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

// j traverses the sublist arrayptr[pass+1] to aarrayptr[n-1] for ( j = pass + 1; 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

// k traverses the sublist {arrayptr[i+1], ..., arrayptr[j]} for (k = i+1; 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 0 && 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

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

for ( i = 1; i = 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

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

for ( k = l; k

}

delete [] temp; temp = 0; }

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

T* copy = new T[ arraySize ]; int i; for ( i = 0; 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 ) while ( j

#endif

infile1.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

PROBLEM STATEMENT: sort a file with 120 records. However, due to memory restrictions only 20 records may be placed into memory. You are to implement a "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 more detailed idea: Call inFilel our source file ( the one with the initial 120 records to be sorted.) You will also need an inFile2, and 2 other files outFilel 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 outFilel read a block, sort it, store in outFile2 read a block, sort it, store in outFilel (in other words, sort a block and alternately place in the files outFilel, outFile2 ) By definition a run is a sorted block Note that each file outFilel and outFile2 will have half of the runs Merge the runs Merge data from outFilel and outFile2 to inFilel and inFile2. Merge the first run on outFilel and the first run on outFile2, and store the result on inFilel: Read two records in main memory, compare, store the smaller on inFilel Read the next record from either outFilel or outFile2 the file that had its record moved/stored to inFilel Similarly merge the second run on outFilel and the second run on outFile2, store the result on inFile2. Merge the third run on outFilel and the third run on outFile2, store the result on inFilel... etc merging each run and storing the result alternatively on inFilel and inFile2 At the end inFilel and inFile2 will contain sorted runs twice the size of the previous runs on outFilel and outFile2 Now merge data from inFilel and inFile2 to outFilel and outFile2. Merge the first run on inFilel and the first run on inFile2, and store the result on outFilel. Merge the second run on inFilel and the second run on inFile2, store the result on outFile2 Etc, merge and store alternatively on inFilel 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