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 < 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--];

}

delete [] temp;
temp = 0;

}

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

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

Transcribed Image Text:

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

Answer rating: 100% (QA)

Based on the problem statement and the codedirections provided you need to implement a quasiexternal ... View the full answer