Not sure if anyone is familiar with column sort. I have this very close to working, but there are a few instances where the numbers are out of order. They occur at the beginning of each new column. I am looking for bugs in my transpose(), reverse_transpose(), shift(), and reverse_shift() functions. I think these are most likely where the problem would be.
If anyone spots a problem, please let me know!
#include "utility.h"
#define s 10 // Number of Columns
#define r 10000 // Number of rows
/*******************TIMER CLASS*******************/
class Timer
{
//Timer class taken from from Kruse and Ryba,
//Data Structures and Program Design in C++,
//Prentice-Hall, 1999
public:
Timer();
//constructor - turns on the timer
double elapsed_time();
//compute elapsed time between start and stop
void reset();
//restarts the timer
private:
clock_t start_time;
//type of value returned by system function clock()
};
/*****************END TIMER CLASS DEFINITION********/
/**************Implementation Timer class functions************/
Timer::Timer()
//constructor - turns on the timer
{
start_time = clock();
}
double Timer::elapsed_time()
//compute elapsed time between start and stop
{
clock_t end_time = clock();
return ((double) (end_time - start_time))/((double) CLOCKS_PER_SEC);
}
void Timer::reset()
//restarts the timer
{
start_time = clock();
}
void insertion_sort(short array1[s][r], int size);
void write_file(short array1[s][r], int size);
void transpose(short array1[s][r]);
void reverse_transpose(short array1[s][r]);
void shift(short array1[s][r], short shifted_array1[s + 1][r]);
void reverse_shift(short array1[s][r], short shifted_array1[s + 1][r]);
bool SortCheck(short array1[s][r]);
int main()
{
const short column = 10;
const short row = 10000;
const string fileName = "Lab9.txt";
int matrix_size = column*row;
//vector< vector<short> > matrix;
short (*matrix) [row]= new short [column][row];
// Open the data file
ifstream fin(fileName.c_str());
if (!fin.is_open())
{
cout << endl << "Unable to open input file " << fileName << endl;
return 1;
}// End if (!fin.is_open())
// Fill up matrix
//int temp = 0; //was being used for vector
for(int t = 0; t < column ; t++)
{
for(int i = 0; i < row; i++)
{
fin >> matrix[t][i];
}// End for(int i = 0; i < r; i++)
}// End for(int t = 0; t < s ; t++)
//Timer time;
insertion_sort(matrix, matrix_size); // Step 1
transpose(matrix); // Step 2
insertion_sort(matrix, matrix_size); // Step 3
reverse_transpose(matrix); // Step 4
insertion_sort(matrix, matrix_size); // Step 5
// New array with column + 1
short (*matrix_shifted) [row]= new short [column + 1][row];
shift(matrix, matrix_shifted); // Step 6
insertion_sort(matrix, matrix_size); // Step 7
reverse_shift(matrix, matrix_shifted); // Step 8
//double t = time.elapsed_time;
SortCheck(matrix);
write_file(matrix, matrix_size);
}
void insertion_sort(short array1[s][r], int size)
/*
Post: The entries of the Sortable_list have been rearranged so that
the keys in all the entries are sorted into nondecreasing order.
*/
{
int first_unsorted; // position of first unsorted entry
int position; // searches sorted part of list
short current; // holds the entry temporarily removed from list
int count = size;
for (int column = 0; column < s; column++)
{
for(first_unsorted = 1; first_unsorted < r; first_unsorted++)
{
if (array1[column][first_unsorted] < array1[column][first_unsorted - 1])
{
position = first_unsorted;
current = array1[column][first_unsorted]; // Pull unsorted entry out of the list.
do
{ // Shift all entries until the proper position is found.
array1[column][position] = array1[column][position - 1];
position--; // position is empty.
} while (position > 0 && array1[column][position - 1] > current);
array1[column][position] = current;
}
}
}
}
// Sort values in each column using sorting method of choice
// "Transpose" the matrix by reading s values at a time in
// column-major order and putting them back into the matrix in row-major order.
void transpose(short array1[s][r])
{
int temp = 0;
short transpose_array[s][r];
for(int column = 0; column < s; column++)
{
for(int x = 0; x < r; x++)
{
transpose_array[x%10][temp/10] = array1[column][x];
temp++;
}
}
for(int column = 0; column < s; column++)
{
for(int x = 0; x < r; x++)
{
array1[column][x] = transpose_array[column][x];
}
}
}
void reverse_transpose(short array1[s][r])
{
int temp = 0;
short temp_array[s][r];
for(int column = 0; column < s; column++)
{
for(int x = 0; x < r; x++)
{
temp_array[column][x] = array1[x%10][temp/10];
temp++;
}
}
for(int column = 0; column < s; column++)
{
for(int x = 0; x < r; x++)
{
array1[column][x] = temp_array[column][x];
}
}
}
// sort_columns()
// Rvs step "Transpose"
// sort_columns()
//
void write_file(short array1[s][r], int size)
{
string file_name = "Results.txt";
ofstream out_file;
out_file.open(file_name.c_str());
for(int column = 0; column < s; column++) //s+1 when writing shifted array
{
for(int row = 0; row < r; row++)
{
out_file << array1[column][row] << endl;
}//end of for i < size
}
}
void shift(short array1[s][r], short shifted_array1[s + 1][r])
{
queue<short> tempQueue;
for(int column = 0; column < s+1; column++)
{
for(int row = 0; row < r; row++)
{
tempQueue.push(array1[column][row]);
}
}
for(int column = 0; column < (s + 1); column++) // 1 should be 's'
{
for(int row = 0; row < r; row++) // 3000 should be 'r'
{
if(column == 0 && row < r/2)
{
shifted_array1[column][row] = -32767;
}
else if(column == s && row >= r/2)
{
shifted_array1[column][row] = 32767;
}
else
{
shifted_array1[column][row] = tempQueue.front();
tempQueue.pop();
}
}
}
}
void reverse_shift(short array1[s][r], short shifted_array1[s + 1][r])
{
queue<short> tempQueue;
for(int column = 0; column < (s + 1); column++)
{
for(int row = 0; row < r; row++)
if(column == 0 && row <r/2)
{
continue;
}
else if(column == (s + 1) && row >= r/2)
{
continue;
}
else
{
tempQueue.push(shifted_array1[column][row]);
}
}
for(int column = 0; column < s; column++)
{
for(int row = 0; row < r; row++)
{
array1[column][row] = tempQueue.front();
tempQueue.pop();
}
}
}
bool SortCheck(short array1[s][r])
//precondition: items have supposedly been sorted
//postcondition: returns true if sorted, false if not
{
bool answer = 0;
queue<short> tempQueue;
for(int column = 0; column < s; column++)
{
for(int row = 0; row < r; row++)
{
tempQueue.push(array1[column][row]);
}
}
short a,b;
//while(!tempQueue.empty())
for(int i = 0; i < s*r-1; i++)
{
a = tempQueue.front();
tempQueue.pop();
b = tempQueue.front();
if((b-a) < 0)
{
answer = 1;
cout << i << ") " << "a: " << a << " " << "b: " << " " << b << endl;
}
}
cout << "answer is: " << answer << endl;
return answer;
}