#include <iostream>
#include <limits>
#include <cmath>
#include <cstdlib>
#include <cstddef>
#include <fstream>
#include <cctype>
#include <ctime>
#include <string>
#include <list>
#include <algorithm>
#include "iomanip"
using namespace std;


enum Error_code { success, fail, exceeds_range, 
underflow, overflow, fatal, not_present, 
duplicate_error, entry_inserted, entry_found, 
internal_error };

class Timer {
	public:
		Timer();
		double elapse_time();
		void reset();

	private:
		clock_t start_time;
};

Timer::Timer()
{
	start_time = clock();
}

double Timer::elapse_time()
{
	clock_t end_time = clock();
	return ( ((double)(end_time - start_time))/(double)CLK_TCK);
}

void Timer::reset()
{
	start_time = clock();
}


void SwapValue(short int& num1, short int& num2)
{
	short int temp;

	temp = num1;
	num1 = num2;
	num2 = temp;

	return;		// optional in a void function
}

void matrixTranspose(short int SortArray[][21])
{
	int i = 0;
	int j = 0;
	short int SortArrayT[100000];
	for(i=0; i<20; i++)
	{
		for(j=0; j<5000; j++)
		{
			SortArrayT[((5000*i)+j)]= SortArray[j][i];
		}
	}
	for(i=0; i<5000; i++)
	{
		for(j=0; j<20; j++)
		{
			SortArray[j][i] = SortArrayT[((5000*j)+i)];
		}
	}
	


}






int newGap(int gap) 
{
	gap = (gap * 10) / 13;
	if (gap == 9 || gap == 10)
    gap = 11;
	if (gap < 1)
	{
		gap = 1;
	}
	return gap;
}

void combsort(short int a[][21], int aSize, int col) 
{
	int gap = aSize;
	for (;;) 
	{
		gap = newGap(gap);
		bool swapped = false;
		for (int i = 0; i < aSize - gap; i++) 
		{
			int j = i + gap;
			if (a[i][col] > a[j][col]) 
			{
				SwapValue(a[i][col], a[j][col]);
				swapped = true;
			}
		}
		if (gap == 1 && !swapped)
		{
			break;
		}
	}
}


void ColumnSort(short int sortArray[][21])
{
	int t = 0;
	short int SortArrayShift[105000];
	short int temp, newPos = 0;
	short int Rrow = 5000;
	short int Rcol = 21-1; 

	Timer *ti = new Timer();
	double time = 0.0;
	ti->reset();
	for(int i = 0; i < 20; i++) // Step 1
	{
		combsort(sortArray, 5000, i);
	
	}

	matrixTranspose(sortArray); // Step 2

	for(int i = 0; i < 20; i++) // Step 3
	{
		combsort(sortArray, 5000, i);
	}

	matrixTranspose(sortArray); // Step 4
	for(int i = 0; i < 20; i++) // Step 5
	{
		combsort(sortArray, 5000, i);
	}


	// STEP 6
	t = 0;
	for (int i = 0; i < 2500; i++)
	{
		SortArrayShift[t] = -32767;
		t++;
	}
		
	for(int i = 0; i < 20; i++)  // ROW
	{
		for (int j = 0; j < 5000; j++) // COL
		{
			SortArrayShift[t] = sortArray[j][i];
			t++;	
		}
	}
	t = t;
	for (int i = 0; i < 2500; i++)
	{
		SortArrayShift[t] = +32767;
		t++;
	}

	

	t = 0;


	for(int i = 0; i < 21; i++)  // ROW
	{
		for (int j = 0; j < 5000; j++) // COL
		{
			sortArray[j][i] = SortArrayShift[t];
			t++;	
		}
	}
	


	// END STEP 6



	t =t;



	for(int i = 0; i < 21; i++) // Step 7
	{
		combsort(sortArray, 5000, i);
	}




	// STEP 8


	t = 0;

	for(int i = 0; i < 21; i++)  // ROW
	{
		for (int j = 0; j < 5000; j++) // COL
		{
			SortArrayShift[t] = sortArray[j][i];
			t++;	
		}
	}

	t = 2500;
	
	for(int i = 0; i < 21; i++)  // ROW
	{
		for (int j = 0; j < 5000; j++) // COL
		{
			sortArray[j][i] = SortArrayShift[t];
			t++;
			if (t == 102500)
			break;
		}
			if (t == 102500)
			break;
		t =t;
	}
	t = t;
	// END STEP 8, This is where the piece of shit crashes.

	time = ti->elapse_time(); 
	cout << "R = 5000 \t\t S = 20" << endl;
	cout << "time elapsed=" << time << endl;
	cout << "Sort: FAILED" << endl;
}



void main()
{

	short int	sortArray[5000][21];
	int k = 0;
	char file[] = "Lab7.txt";
	ifstream file_in;
	file_in.open(file);

	for(int i = 0; i < 20; i++)  // ROW
	{
		for (int j = 0; j < 5000; j++) // COL
		{
			file_in >> sortArray[j][i];
		}
	}
	file_in.close();
	ColumnSort(sortArray);
	


	system("Pause");
}