coolbeanbob 17 Junior Poster

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;
	
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.