ece368/ece368-proj1/sorting.c

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

/*
load specified file
returns array of longs and sets Size
*/
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;

}

/*
function to save an array of specified size to specified file
returns the number of successful writes (or failure)
*/ 
int Save_File(char *Filename, long *Array, int Size){

	// count of successfully written values (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++){
		fprintf(fptr, "%ld\n", Array[i]);
		count++;
	}

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

}

/*
runs Shell insertion sort on Array
counts the number of comparisons and moves (directly involving the array) required to do so
*/
void Shell_Insertion_Sort(long *Array, int Size, double *N_Comp, double *N_Move){

	// declare and initialize variables
	int cCount = 0; // comp count
	int mCount = 0; // move count
	long temp = 0; // temp value
	int * pratt = genSeqOne(Size);
	int gapInd = 0; // index to cycle through sequence
	int gap = 0; // current gap in loop sequence
	int i = 0; // incrementor variable
	int j = 0; // incremontor variable

	// increment through pratt sequence, starting with largest value
	while(pratt[gapInd] > 0){
		gap = pratt[gapInd]; // current gap
		// insertion sort
		for(i = gap; i < Size; i++){
			temp = Array[i];
			mCount++; // temp = Array[i]
			for (j = i; j >= gap && temp < Array[j - gap]; j = j - gap){
				cCount++; // temp < Array[j - gap]
				Array[j] = Array[j - gap];
				mCount++; // Array[j] = Array[j - gap]
			}
			cCount++; // for loop comparison runs once more than the code it contains
			Array[j] = temp;
			mCount++; // Array[j] = temp;
		}
		gapInd++;
	}

	// clean up
	free(pratt); // free resources
	*N_Comp = cCount; // set number of comparisons
	*N_Move = mCount; // set number of moves

}

/*
use Shell's principle of dividing the array by diminishing gaps with bubble sort on Array
counts the number of comparisons and moves (directly involving the array) required to do so
*/
void Improved_Bubble_Sort(long *Array, int Size, double *N_Comp, double *N_Move){

	// declare and initialize variables
	int cCount = 0; // comparison count
	int mCount = 0; // move count
	long temp = 0; // temp value
	int * sequence = genSeqTwo(Size); // generate sequence
	int gapInd = 0; // index to cycle through sequence
	int gap = 0; // current gap in loop sequence
	int i = 0; // incrementor variable
	int j = 0; // incremontor variable

	// increment through defined sequence, starting with largest value
	while(sequence[gapInd] > 0){
		gap = sequence[gapInd]; // current gap
		// bubble sort
		for(i = gap; i < Size; i++){
			for (j = i; j >= gap; j = j - gap){
				if(Array[j] < Array[j - gap]){
					temp = Array[j];
					mCount++; // temp = Array[j]
					Array[j] = Array[j - gap];
					mCount++; // Array[j] = Array[j - gap]
					Array[j - gap] = temp;
					mCount++; // Array[j - gap] = temp;
				}
				cCount++; // Array[j] < Array[j - gap]
			}
		}
		gapInd++;
	}

	// clean up
	free(sequence); // free resources
	*N_Comp = cCount; // set number of comparisons
	*N_Move = mCount; // set number of moves}

}

/*
generates Sequence 1 up to maxVal
returns an int array ending with 1, with a zero appended at the last index
*/
int * genSeqOne(int maxVal){
	// variable declarations
	int * sequence = calloc(maxVal, sizeof(int));
	sequence[0] = 1; // start with one
	int i = 0; // incrementor starts on first index
	// to keep sequence in proper order
	int twoInd = 0; // last index multiplied by two
	int threeInd = 0; // last index multiplied by three
	
	// generate values
	while(sequence[i] < maxVal) { // don't meet exceed maxVal
		i++; // always increment i (always add a value to sequence)
		if(sequence[twoInd] * 2 < sequence[threeInd] * 3){
			sequence[i] = sequence[twoInd] * 2;
			twoInd++; // update two's last index
		}
		else if(sequence[twoInd] * 2 > sequence[threeInd] * 3){
			sequence[i] = sequence[threeInd] * 3;
			threeInd++; // update three's last index
		}
		else{ // if sequence[twoInd] * 2 == sequence[threeInd] * 3
			sequence[i] = sequence[twoInd] * 2;
			twoInd++;   // update last index
			threeInd++; // of both values
		}
	}
	sequence[i] = 0; // exceded maxVal on last pass, clean that up

	// reverse the generated values
	int * reverse = calloc(i + 1, sizeof(int)); // last value is 0
	i--; // move to penultimate index of sequence
	int j = 0; // start at first index of reverse
	while(sequence[i] != 1){ // stop at first value (sequence[0] = 1)
		reverse[j] = sequence[i];
		j++;
		i--;
	}
	reverse[j] = 1; // penultimate value is 1

	// clean up
	free(sequence); // free inital sequence
	return reverse; // return reversed sequence (smaller)

}

/*
generates Sequence 2 based on n
returns an int array ending with 1, with a zero appended at the last index
*/
int * genSeqTwo(int n){
	
	// initalize
	int * sequence = calloc(n, sizeof(int)); // large array
	sequence[0] = n / 1.3; // set first value
	int i = 1; // set second index first
	while(sequence[i - 1] > 1){ // stop if n is one or two
		sequence[i] = sequence[i - 1] / 1.3; // value set based on last index
		if(sequence[i] == 9 || sequence[i] == 10){
			sequence[i] = 11;
		}
		i++;
	}

	// make smaller array
	int * smaller = calloc(i + 1, sizeof(int));
	int j = 0;
	while(sequence[j] != 0){
		smaller[j] = sequence[j];		
		j++;
	}
	free(sequence);
	return smaller;

}

/*
writes Sequence 1 to Filename
the largest value in the sequence will be less than N
*/
void Save_Seq1(char *Filename, int N){
	
	// generate sequence
	int * sequence = genSeqOne(N);
	
	// open file for writing
	FILE * fptr = NULL;
	fptr = fopen(Filename, "w");

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

	// clean up
	if(!fclose(fptr) == 0){ // close file
		printf("File close error.");
	}
	free(sequence); // release memory

}

/*
writes Sequence 1 to Filename
the sequence is based on integers of N/1.3^index
*/
void Save_Seq2(char *Filename, int N){
	
	// generate sequence
	int * sequence = genSeqTwo(N);
	
	// open file for writing
	FILE * fptr = NULL;
	fptr = fopen(Filename, "w");

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

	// clean up
	if(!fclose(fptr) == 0){ // close file
		printf("File close error.");
	}
	free(sequence); // release memory

}