Sorting Algorithms in C++

gistfile1.cpp

#ifndef SORTINGALGORITHMS_H_
#define SORTINGALGORITHMS_H_

#endif /*SORTINGALGORITHMS_H_*/

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

#define SWAP(type, x, y) type t; t = x; x = y; y = t;

//Function Headers;
template<class T>
void BubbleSort(T a[], int l, int r)
{
register T t_Val;

				for(register unsigned long i(0), j(0); i < (r - 1); i++)
					for(j=0 ; j < (r - 1 -i); j++)
						if(a[j] > a[j+1])
						{
							//SWAP(_T,(*this)[j],(*this)[j+1]);
							t_Val = a[j];
				 			a[j] = a[j+1];
							a[j+1] = t_Val;
						}
}

template<class T>
void ShellSort(T a[], int l, int r )
{
	register long i, j, incrmnt;
   	register T t_Val;
   			
    for(incrmnt = 1 ; incrmnt<r; incrmnt = (incrmnt*3)+1);
      	while (incrmnt > 0)
        {
            for (i = incrmnt; i < r; i++)
            {
				j = i;
                t_Val = a[i];

                while ((j >= incrmnt) && (a[j - incrmnt] > t_Val))
                {                                 			 
					a[j] = a[j - incrmnt];
						j = j - incrmnt;
                }
           		a[j] = t_Val;
            }
            incrmnt /= 2;
        }

}


template<class T>
void SelectionStack(T a[], int l, int r)
{
	std::stack<T> temp ;

	for (register unsigned long i(0),j(0),iMin(0), ulSize = r; iMin = i, i < ulSize; i++)	
	{		
					
		for (j = 0 ; j < r;((a[j] > a[iMin]) && (a[j] != 0)) ? iMin = j : 0 , j++)			
			(void)0;;

		temp.push(a[iMin]);
		a[iMin] = 0;
	}

	for (register unsigned long k(0); k < r; temp.pop(), k++)
		a[k] = temp.top();
		

}

template<class T>
void SelectionSort(T a[], int l, int r)
{
register T t_Val;

				for (register unsigned long i(0),j(0),iMin(0); iMin = i, i < (r - 1); i++)	
				{		
					/*
					for (j = i + 1; j < (*this).getSize(); j++)			
						if ((*this)[j] < (*this)[iMin])			
							iMin = j;	*/
						
					for (j = i + 1; j < r; a[j] < a[iMin] ? iMin = j : 0 , j++)
						0;

					SWAP(T,a[i],a[iMin]);
					/*t_Val = (*this)[i];		
					(*this)[i] = (*this)[iMin];		
					(*this)[iMin] = t_Val;	*/
				}
}

template<class T>
void InsertionSort(T a[], int l, int r)
{
		register T t_Val;
		register unsigned long ulMin = 0;
		
		
		/*for(register unsigned long centinell(0); centinell < r-1; centinell++)
			if (a[ulMin] < a[centinell])
				ulMin = centinell;

		
		SWAP(T,a[0],a[ulMin]);*/
		
				
		for(register unsigned long i(0),j(0);t_Val = a[i],(i < r);a[j] = t_Val, i++)
		{
			for(j = i; (j > 0) && (a[j-1] > t_Val); a[j] = a[j-1],j--)
				(void)0;
		}
			//PrintArray(a,r);
				return;
}



template<class T>
void QuickSort(T a[], int lb, int ub)
{
	register unsigned long i, j;
	register unsigned char t_ucFlag = 0;
	register T t_Pivot;

	if (lb < ub)
	{
		i = lb;
		j = ub + 1;

		t_Pivot = a[i];
		register T t_Val;

		while(t_ucFlag != 1)
		{
			for ( i++; a[i] < t_Pivot ; i++)
				(void)0;

			for ( j--; a[j] > t_Pivot ; j--)
				(void)0;

			if (i < j)
			{
				SWAP(T,a[i],a[j]);
							/*t_Val = (*this)[i];
							(*this)[i] = (*this)[j];
							(*this)[j] = t_Val;*/
			}
			else
			{
				t_ucFlag = 1;
				SWAP(T,a[lb],a[j]);
							/*t_Val = (*this)[lb];
							(*this)[lb] = (*this)[j];
							(*this)[j] = t_Val;*/
				}
			}
			QuickSort(a,lb, j-1);
			QuickSort(a,j+1, ub);
			//std::cout << i << std::endl;
		}
}

template<class T>
void radixSort(T a[] , int size)
{
	register unsigned long ulNPasses = 0, ulLargest, i,j , k;

	ulLargest = a[0];

	for(i = 1; i < size ; (a[i] > ulLargest) ? ulLargest = a[i] : (void)0 , i++)  
		(void)0;

	for( ; ulLargest > 0; ulNPasses++, ulLargest /= 10)
		(void)0;

	
	int power = 1;

	queue<T> digitQueue[10];

	for (i=0;i < ulNPasses;i++)
	{
		for (k = 0; k < size; k++)
			digitQueue[(a[k] / power) % 10].push(a[k]);


		int digit;
		j = 0;

		for (digit = 0; digit < 10; digit++)
			while (!digitQueue[digit].empty())
			{
				a[j] = digitQueue[digit].front();
				digitQueue[digit].pop();
				j++;
			}
		
		power *= 10;
	}
}


/********************Misc Functions*********************/
template<class T>
void swap(T &A, T &B)
{
	T tmp = A;
	A = B;
	B = tmp;
}

template<class T>
void compEx(T &A, T &B)
{
	if(B < A)
	{
		T tmp = A;
		A = B;
		B = tmp;
	}
}

template<class T>
void PrintArray(T a[], int size)
{
	for(int i = 0; i < size; i++)
	{
		std::		cout<<a[i]<<" ";
	}
	std::	cout<<endl;
}

template<class T>
void WriteFile(const char* szName, T a[], long size)
{
	std::ofstream myfile;

	myfile.open (szName);
	

	for(int i = 0; i < size; i++)
	{
		myfile << a[i] << std::endl;
	}

	myfile.close();
}

template<class T>
void OpenFile(const char* szName, T a[], long size)
{
	std::ifstream myfile;

	myfile.open (szName);
	
	unsigned long i(0);
	while(i<size)
	{
		myfile >> a[i];
		std::cout << a[i] << std::endl;
		i++;
	}

	myfile.close();
	std::cout << "sorted" << std::endl;
}

template<class T>
int sortedInput(T a[], int l, int size)
{
	for(int i = l; i < size - 1; i++)
	{
		if(a[i] > a[i+1])
			return 0;
	}
	return 1;
}