gistfile1.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/timeb.h>
#include <string.h>

#define MAX_SIZE 10000000
#define ALG_NAME_SIZE 80

//#define SORT_DEBUG

__int64 gRefTime = 0;

__int64 GetMilliSecondTime(struct _timeb timeBuf);
void SetTime(void);
__int64 GetTime(void);

typedef enum {
	INSERTION_SORT,
	SELECTION_SORT,
	BUBBLE_SORT
} SORT_ALG;

void ReadInput(SORT_ALG& sortAlg, char* sortAlgName, int& size);
void GenerateSortedData(int data[], int size);
void GenerateReverselySortedData(int data[], int size);
void GenerateRandomData(int data[], int size);
void GenerateNearlySortedData(int data[], int size);
void Sort(int data[], int size, SORT_ALG alg, char* dataType);
bool IsSorted(int data[], int size);
void InsertionSort(int data[], int size);
void SelectionSort(int data[], int size);
void BubbleSort(int data[], int size);
void Swap(int& x, int& y);
void PrintData(int data[], int size, char* tilte);


int data[MAX_SIZE];

int main(void)
{
	int size;
	char sortAlgName[ALG_NAME_SIZE];
	SORT_ALG sortAlg;

	ReadInput(sortAlg, sortAlgName, size);

	printf("\n Sorting Algorithm: %s", sortAlgName);
	printf("\n Input Size = %d\n", size);

	GenerateSortedData(data, size);
	Sort(data, size, sortAlg, "Sorted Data");

	GenerateReverselySortedData(data, size);
	Sort(data, size, sortAlg, "Reversely Sorted Data");

	GenerateRandomData(data, size);
	Sort(data, size, sortAlg, "Random Data");

	GenerateNearlySortedData(data, size);
	Sort(data, size, sortAlg, "Nearly Sorted Data");

	printf("\n Program Completed Successfully\n");

	return 0;
}
/********************************************************************/

void GenerateSortedData(int data[], int size)
{
	int i;

	for (i = 0; i<size; i++)
		data[i] = i * 3 + 5;
}
/*****************************************************************************/

void GenerateReverselySortedData(int data[], int size)
{
	int i;

	for (i = 0; i < size; i++)
		data[i] = (size - i) * 3 + 5;
}
/*****************************************************************************/

void GenerateRandomData(int data[], int size)
{
	int i;

	for (i = 0; i < size; i++)
		data[i] = rand();
}
/*****************************************************************************/

void GenerateNearlySortedData(int data[], int size)
{
	int i;

	GenerateSortedData(data, size);

	for (i = 0; i<size; i++)
	if (i % 10 == 0)
	if (i + 1 < size)
		data[i] = data[i + 1] + 5;
}
/*****************************************************************************/

void Sort(int data[], int size, SORT_ALG alg, char* dataType)
{
	__int64 time;

	printf("\n %s:", dataType);

#ifdef SORT_DEBUG
	PrintData(data, size, "Data before sorting");
#endif

	SetTime();
	if (alg == INSERTION_SORT)
		InsertionSort(data, size);
	else if (alg == SELECTION_SORT)
		SelectionSort(data, size);
	else if (alg == BUBBLE_SORT)
		BubbleSort(data, size);
	else
	{
		printf("Invalid sorting algorithm\n");
		exit(1);
	}

	time = GetTime();

#ifdef SORT_DEBUG
	PrintData(data, size, "Data after sorting");
	printf("\n");
#endif

	if (IsSorted(data, size))
		printf(" Correctly sorted %d elements in %I64d ms.", size, time);
	else
		printf(" ERROR!: INCORRECT SORTING");
	printf("\n -------------------------------------------------------------");
}
/*****************************************************************************/

bool IsSorted(int data[], int size)
{
	int i;

	for (i = 0; i<(size - 1); i++)
	{
		if (data[i] > data[i + 1])
			return false;
	}
	return true;
}
/*****************************************************************************/

void InsertionSort(int data[], int size)
{
	int i, j, temp;

	for (i = 1; i<size; i++)
	{
		temp = data[i];
		for (j = i - 1; j >= 0&&data[j]>temp; j--)
			data[j + 1] = data[j];
		data[j + 1] = temp;
	}
}
/*****************************************************************************/

void SelectionSort(int data[], int size)
{
	int i, j, minIndex;

	for (i = 0; i<(size - 1); i++)
	{
		minIndex = i;
		for (j = i + 1; j<size; j++)
		if (data[j] < data[minIndex])
			minIndex = j;
		if (data[i] != data[minIndex])
			Swap(data[minIndex], data[i]);
	}
}
/*****************************************************************************/

void BubbleSort(int data[], int size)
{
	int i, j;
	bool is_sorted=false;
	for (i = 0; i<(size - 1)&&!is_sorted; i++)
	{
		is_sorted = true;
		for (j = size - 1; j > i; j--)
			if (data[j] < data[j - 1])
			{
				Swap(data[j], data[j - 1]);
				is_sorted = false;
			}
	}
}
/*****************************************************************************/

void Swap(int& x, int& y)
{
	int temp = x;
	x = y;
	y = temp;
}
/*****************************************************************************/

void PrintData(int data[], int size, char* title)
{
	int i;

	printf("\n %s: \n", title);
	for (i = 0; i<size; i++)
	{
		printf(" %d", data[i]);
		if (i % 10 == 9 && size > 10)
			printf("\n");
	}
}
/*****************************************************************************/

void ReadInput(SORT_ALG& sortAlg, char* sortAlgName, int& size)
{
	char algCode;

	printf("Enter sorting algorithm (I for Insertion, S for Selection, B for Bubble)\n");
	scanf("%c", &algCode);
	if (algCode == 'I')
	{
		sortAlg = INSERTION_SORT;
		strcpy(sortAlgName, "InsertionSort");
	}
	else if (algCode == 'S')
	{
		sortAlg = SELECTION_SORT;
		strcpy(sortAlgName, "SelectionSort");
	}
	else if (algCode == 'B')
	{
		sortAlg = BUBBLE_SORT;
		strcpy(sortAlgName, "BubbleSort");
	}
	else
	{
		printf("\nUnrecognized sorting algorithm %c", algCode);
		exit(1);
	}

	printf("Enter input size\n");
	scanf("%d", &size);
	if (size < 1 || size > MAX_SIZE)
	{
		printf("\n Invalid input size %d. Size should be between 1 and %d",
			size, MAX_SIZE);
		exit(1);
	}
}
/********************************************************************/

__int64 GetCurrentTime(void)
{
	__int64 crntTime = 0;

	struct _timeb timeBuf;
	_ftime(&timeBuf);
	crntTime = GetMilliSecondTime(timeBuf);

	return crntTime;
}
/********************************************************************/

void SetTime(void)
{
	gRefTime = GetCurrentTime();
}
/********************************************************************/

__int64 GetTime(void)
{
	__int64 crntTime = GetCurrentTime();

	return (crntTime - gRefTime);
}
/********************************************************************/

__int64 GetMilliSecondTime(struct _timeb timeBuf)
{
	__int64 mliScndTime;

	mliScndTime = timeBuf.time;
	mliScndTime *= 1000;
	mliScndTime += timeBuf.millitm;
	return mliScndTime;
}
/**********************************************************************/