ece368/Spring 2014/PA02/sorting.c~

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

Node * Load_File(char * Filename){

	// temporarily store last read value
	long val = 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;
    }
    
    Node *head;
    head = malloc(sizeof(Node));
    head->value = 0;
    head->next = NULL;
    
    Node *temp = head;
    
  	while(fscanf(fptr, "%ld", &val) != EOF){ // check for error
		temp->value = val;
		temp->next = malloc(sizeof(Node));
		temp = temp->next;
		temp->value = 0;
		temp->next = NULL;
	}
	
	// clean up
	if(!fclose(fptr) == 0){ // close file
		printf("File close error.");
		return NULL; // return NULL on file close error
	}
	return head;
}

int Save_File(char * Filename, Node * list){

	int count = 0;
	
	// write to file
	FILE * fptr = NULL;
	fptr = fopen(Filename, "w");
	
	Node *temp = list;
	while(temp->next != NULL){
		fprintf(fptr, "%ld\n", temp->value);
		count++;
		temp = temp->next;
	}
	
	// close file
	if(!fclose(fptr) == 0){ 
		printf("File close error.");
		return EXIT_FAILURE; // return NULL on file close error
	}
	
	return count;
}



Node * Shell_Sort(Node *list){

	int size = Get_Size(list);
	// 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 (Get_Node_At(list, minIndex)->value > Get_Node_At(list, j)-> value){
		            minIndex = j; // new min
				}
				cCount++; // Array[minIndex] > Array[j]
			}
		    // swap values with temp
		    value = Get_Node_At(list, i)->value;
			mCount++; // value = Array[i]
		    Get_Node_At(list, i)->value = Get_Node_At(list, minIndex)->value;
			mCount++; // Array[i] = Array[minIndex]
		    Get_Node_At(list, minIndex)->value = value;
			mCount++; // Array[minIndex] = value

		}
	}

	// clean up
	free(pratt); // free sequence
	return list;
}

int Get_Size(Node * list){
	int size = 0;
	Node *temp = list;
	while(temp->next != NULL){
		size++;
		temp = temp->next;
	}
	return size;
}

Node * Get_Node_At(Node *list, int index){
	Node *temp = list;
	int i;
	for(i = 0; i < index; i++){
		temp = temp->next;
		if(temp == NULL){
			printf("Error, index out of bounds.");
			return NULL;
		}
	}
	return temp;
}

void Destroy_List(Node * head)
{
	Node *temp = head;
	while(head != NULL)
	{
		temp = temp->next;
		free(head);
		head = temp;
	}
}

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