ece368/Spring 2014/PA01/sorting.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sorting.h"

long *Load_File(char * Filename, int *Size){

	// num ints in file
	int val0 = 0;

	// open file for reading
	FILE * fptr = NULL;
	fptr = fopen(Filename, "r");
	if (fptr == NULL){ // check for error
      printf("File name error.\n");
      return NULL;
    }
  	if(fscanf(fptr, "%d", &val0) == 0){ // check for error
		printf("File read error.\n");
		return NULL;
	}

	// scan values into buffer (return value)
	long *buffer = malloc(sizeof(long) * val0);	 // malloc return value
	if (buffer == NULL){
		printf("Buffer malloc error.\n");
		return NULL;
	}
	int i;
	for (i = 0; i < val0; i++){
		if(fscanf(fptr, "%ld", &buffer[i]) == 0){
			printf("File read error.\n");
			return NULL; // stop on error
		}
    }
	
	// clean up
	*Size = val0; // assign size
	if(!fclose(fptr) == 0){ // close file
		printf("File close error.");
		return NULL; // return NULL on file close error
	}
	return buffer;
}

int Save_File(char *Filename, long *Array, int Size){

	// count of successful writes (return value)
	int count = 0;
	
	// write to file
	FILE * fptr = NULL;
	fptr = fopen(Filename, "w");
	if(fprintf(fptr, "%d\n", Size) == 0){
		return EXIT_FAILURE;
	}
	int i;
	for(i = 0; i < Size; i++){
		count = fprintf(fptr, "%ld\n", Array[i]);
	}

	// close file
	if(!fclose(fptr) == 0){ 
		printf("File close error.");
		return EXIT_FAILURE; // return NULL on file close error
	}
	return count;
}

void Shell_Insertion_Sort(long *Array, int Size, double *N_Comp, double *N_Move){

	// generate sequence
	int maxInd = 0;
	int * pratt = genSequence(Size);
	while(pratt[maxInd] != 0){ 	// calculate length of sequence
		maxInd++;
	}

	// declare and initialize variables
	int cCount = 0; // comp count
	int mCount = 0; // move count
	long value = 0; // temp value
	int gapInc = 0;
	int i = 0;
	int j = 0;
	int gap = 0;

	// increment through sequence array
	for(gapInc = maxInd; gapInc >= 0; gapInc--){
		gap = pratt[gapInc]; // makes code simpler
		for(i = gap; i < Size; i++){ // create subarrays
			j = i;

			// insertion sort
			value = Array[i];
			mCount++; // value = Array[i]
			cCount++; // value < Array[j - gap]
			while (j >= gap && value < Array[j - gap]){
				cCount++; // value < Array[j - gap]
				Array[j] = Array[j - gap];
				mCount++; // Array[j] = Array[j - gap]
				j = j - gap;
			}
			Array[j] = value;
			mCount++; // Array[j] = value

		}
	}

	// clean up
	free(pratt); // free resources
	*N_Comp = cCount; // set counters
	*N_Move = mCount;
}

void Shell_Selection_Sort(long *Array, int Size, double *N_Comp, double *N_Move){

	// generate sequence
	int maxInd = 0;
	int * pratt = genSequence(Size);
	while(pratt[maxInd] != 0){ 	// calculate length of sequence
		maxInd++;
	}

	// declare and initialize variables
	int cCount = 0; // comp count
	int mCount = 0; // move count
	long value = 0; // temp value
	int gapInc = 0;
	int i = 0;
	int j = 0;
	int gap = 0;
	int minIndex = 0;

	// increment through sequence array
	for(gapInc = maxInd; gapInc >= 0; gapInc--){
		gap = pratt[gapInc]; // makes code simpler
		for(i = gap; i < Size - 1; i++){ // create subarrays

			// selection sort
			minIndex = i;
		    for (j = i + 1; j < Size; j++){ // find global minimum
		        if (Array[minIndex] > Array[j]){
		            minIndex = j; // new min
				}
				cCount++; // Array[minIndex] > Array[j]
			}
		    // swap values with temp
		    value = Array[i];
			mCount++; // value = Array[i]
		    Array[i] = Array[minIndex];
			mCount++; // Array[i] = Array[minIndex]
		    Array[minIndex] = value;
			mCount++; // Array[minIndex] = value

		}
	}

	// clean up
	free(pratt); // free sequence
	*N_Comp = cCount; // set counter
	*N_Move = mCount;
}

// (2^p * 3^q)
int * genSequence(int maxVal){

	// count number of rows needed (space required for allocation)
	int numRows = 0; // number of triangle rows needed
	int val = 1; // used to count num rows
	while(val < maxVal){
		numRows++;
		val = val * 3; // right side of triangle
	}

	// memory allocation
	int arraySize = 0; // space to alloc for sequence
	int i;
	for(i = numRows; i > 0; i--){
		arraySize = arraySize + i; // num values in each row
	}
	int * pratt = calloc(arraySize + 1, sizeof(int)); // add 1 for safety

	// initialize values
	int currInd = 0; // track current index of array
	int currRow = 0; // track row of triangle
	int j; // incrementor
	for(currRow = 0; currRow < numRows; currRow++){
		for(j = 0; j <= currRow; j++){
			pratt[currInd] = 1 * genHelp(2, currRow - j) * genHelp(3, j);
			currInd++; // cycle through array with proper numbers
		}
	}
	return pratt; // return array
}


// helper function for sequence generation
// raises base to exponent power, returns only positive integers
int genHelp(int base, int exponent){

	if(exponent <= 0){
		return 1;
	}
	if(exponent == 1){
		return base;
	}

	int retval = 1;
	int i;
	for(i = 0; i < exponent; i++){
		retval = retval * base;
	}
	return retval;
}

int Print_Seq(char *Filename, int maxVal){
	
	// generate sequence
	int * sequence = genSequence(maxVal);
	
	// open file for writing
	FILE * fptr = NULL;
	fptr = fopen(Filename, "w");

	// calculate length of array
	int length = 0;
	while(sequence[length] != 0){
		length++;
	}
	fprintf(fptr, "%d\n", length); // print length first

	// print values to file
	int i;
	for(i = 0; i < length; i++){
		fprintf(fptr, "%d\n", sequence[i]);
	}

	// close file
	if(!fclose(fptr) == 0){ 
		printf("File close error.");
		return EXIT_FAILURE; // return NULL on file close error
	}
	
	// clean up
	free(sequence); // release memory
	return length; // return specified value
}