ece368/Spring 2014/PA01/sorting (macbuntu's conflicted copy 2014-02-18).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
	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
	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){

	int cCount = 0; // comp count
	int mCount = 0; // move count

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

	long value = 0; // temp yvalue
	int i, j, k;
	for(i = length - 1; i >= 0; i--){
		for(j = pratt[i]; j < Size; ++j){
			mCount++; // j = pratt[i]
		    value = Array[j];
			mCount++; // value = Array[j]
		    for (k = j - pratt[i]; k >= 0 && Array[k] > Array[k + pratt[i]; k = k - pratt[i]){
				cCount++; // Array[k] > Array[k + pratt[i]
		        Array[k + pratt[i]] = Array[k];
				mCount++; //  Array[k + pratt[i]] = Array[k]
		    }
		}
	}
	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){

	int cCount = 0; // comp count
	int mCount = 0; // move count

	int * pratt = genSequence(Size); // generate sequence
	// calculate length of sequence
	int length = 0;
	while(pratt[length] != 0){
		length++;
		cCount++; // pratt[length] != 0
	}
	long minVal = 0; // minimum value
	int min = 0; // minimum index
	int i, j, k;
	for(i = length - 1; i >= 0; i++){
		for (j = 0; j < Size - 1; j++){
		    /* find the minimum */
		    min = j;

		    for (k = j + 1; k < Size; k++){
		        if (Array[k] < Array[min]){
		            min = k;
					cCount++; // Array[k] < Array[min]
				}
			}
		    minVal  = Array[min];
	 		mCount++; // minVal = Array[min]
		    /* move elements to the right */
		    for (k = min; k > j; k--){
		        Array[k] = Array[k - 1];
				mCount++; // Array[k] = Array[k - 1]
			}
		    Array[j] = minVal;
			mCount++; // Array[j] = minVal
		}
	}
	free(pratt); // free sequence
	*N_Comp = cCount; // set counter
	*N_Move = mCount;
}

// (2^p * 3^q)
int * genSequence(int maxVal){
	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
	}

	int arraySize = 0;
	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
}

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
	}
	
	free(sequence); // release memory

	return length; // return specified value
}

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;
}