ece264/solutions/ECE264Solutions/PA03/answer03.c

#include "pa03.h"
#include <stdio.h>
#include <stdlib.h>

/**
 * Read a file of integers.
 *
 * Arguments:
 *
 * filename: the name of a file that contains a list of integers (one
 * per line)
 * 
 * numberOfIntegers: pointer to store the number of integers in the
 * file. You need to update the value stored at the address which is
 * the pointer's value
 *
 * Returns:
 *
 * a array of integers from the file, or NULL if *any* error is
 * encountered.
 *
 * You do NOT know how many integers are in the file until you have
 * read it. Once you know how many integers there are, you can modify
 * the "numberOfIntegers" variable. (Note that this is a pointer, not
 * an integer) You must allocate memory to store the integers.
 * 
 * Once memory is allocated to store the integers, you will need to
 * re-read the values from the file. To do this, you must reset the
 * file pointer to the beginning of the file using the function
 * "fseek".
 * 
 * You should not use rewind (if you have learned it somewhere).  The
 * difference of rewind and fseek is that rewind does not tell you
 * whether it fails.  
 *
 * One way to read integeres is to use the "fscanf" function.  It is
 * easier than reading one character at a time by using fgetc.
 *
 * You must use malloc in this function.
 * 
 * Some old books encourage readers to type cast in front of malloc,
 * something like
 *
 * int * ptr = (int *) malloc(sizeof(int) * size);
 *
 * Type cast is no longer needed and in fact is discouraged now.  You
 * should *NOT* type cast malloc.  It is discouraged even though it is
 * not wrong.
 *
 * The allocated memory will be released in pa03.c. You do not need to
 * worry about releasing memory.
 *
 * You will receive zero if you allocate a large array whose size is
 * independent of the number of integers in the file.  For example, if
 * you write this
 *
 * int array[10000];
 * 
 *
 */
int * readIntegers(const char * filename, int * numberOfIntegers)
{
  FILE *file; // file pointer
	int *contents; // array to be returned
  int val; // temp variable
	int i = 0; // incrementor variable

	file = fopen(filename, "r"); // open file
	if(file == NULL) // return NULL on file read error
		return NULL;
	while(fscanf(file, "%d", &val) == 1) // count number if integers in file
	{
		i++;
	}
	*numberOfIntegers = i; // set numberOfIntegers
	
	if(!fseek(file, 0, SEEK_SET) == 0) // reset file pointer
		return NULL; // return NULL on pointer reset error
		
	contents = malloc(*numberOfIntegers * sizeof(int)); // allocate memory
	for(i = 0; i < *numberOfIntegers; i++) // sets contents' values
	{
		fscanf(file, "%d", &val);
		contents[i] = val;
	}
	
	if(!fclose(file) == 0) // close file
		return NULL; // return NULL on file close error
		
	return contents; // return array of data read from file
}

/**
 * Sort an (ascending) array of integers
 *
 * Arguments:
 * arr    The array to search
 * length Number of elements in the array
 *
 * Uses "quicksort" to sort "arr".  Use the first element of the array
 * as the pivot.  
 *
 * Your solution MUST use recursive function (or functions)
 * 
 * quicksort works in the following way: 
 * 
 * find an element in the array (this element is called the
 * pivot). 
 *
 * rearrange the array's elements into two parts: the part smaller
 * than this pivot and the part greater than this pivot; make the pivot
 * the element between these two parts
 * 
 * sort the first and the second parts separately by repeating the 
 * procedure described above
 * 
 * You will receive no point if you use any other sorting algorithm.
 * You cannot use selection sort, merge sort, or bubble sort.
 * 
 * Some students are fascinated by the name of bubble sort.  In
 * reality, bubble sort is rarely used because it is slow.  It is a
 * mystery why some students (or even professors) like bubble sort.
 * Other than the funny name, bubble sort has nothing special and is
 * inefficient, in both asymptotic complexity and the amount of data
 * movement.  There are many algorithms much better than bubble sort.
 * You would not lose anything if you do not know (or forget) bubble
 * sort.
 *
 */
void q_sort(int *arr, int start, int end) // helper function for sort
{	
	if(end - start < 2) // condition to end recursion
		return;
	
	int pivot = start; // set initial pivot index
	int val; // create temporary variable used to swap values
	int i = start; // incrementor variable
	int j = end; // decrementor variable
	
	while(i < j) // prevent i and j from over-lapping
	{
		while(arr[i] < arr[pivot] && i <= end)
		{	
			i++; // find index of value less than pivot value
		}
		while (arr[j] > arr[pivot] && j >= start)
		{
			j--; // find index of value greater than pivot value
		}
		val = arr[i]; // swap value at i with value at j
		arr[i] = arr[j];
		arr[j] = val;
	} // repeat for all values i < j, i.e. one pass

  q_sort(arr, start, j-1); // repeat for sub array of smaller indices
  q_sort(arr, j+1, end);  // repeat for sub array of larger indices
}

void sort(int * arr, int length)
{
	q_sort(arr, 0, length - 1); // call helper function
}

/**
 * Use binary search to find 'key' in a sorted array of integers
 *
 * Arguments:
 * 
 * arr The array to search. Must be sorted ascending.  You do not need
 *        to check. This array is from the result of your sort
 *        function. Make sure your sort function is correct before you
 *        start writing this function.
 *
 * length Number of elements in the array
 * key    Value to search for in arr
 *
 * Returns:
 * The index of 'key', or -1 if key is not found.
 *
 * Since the array is sorted, you can quickly discard many elements by
 * comparing the key and the element at the center of the array. If
 * the key is the same as this element, you have found the index.  If
 * the key is greater than this element, you can discard the first
 * half of the array.  If the key is smaller, you can discard the
 * second half of the array.  Now you have only half of the array to
 * search.  Continue this procedure until either you find the index or
 * it is impossible to find a match.
 * 
 * Your solution MUST use recursive function (or functions)
 *
 * Don't forget that arrays are 'zero-indexed'. Also, you must
 * use a binary search to pass this question.
 * 
 * You will receive no point if you do the following because it is not
 * binary search.  This is called linear search because it checks
 * every element.
 *
 * int ind;
 * for (ind = 0; ind < length; ind ++)
 * {
 *    if (arr[ind] == key)
 *    {
 *       return ind;
 *    }
 * }
 * return -1;
 */
int b_search(int * arr, int start, int end, int key)
{
	if (start > end) // condition to end recursion
		return -1;
		
	int val = (start + end) / 2; // set val to halfway point in arr
	
	if(arr[val] == key) // return index if key is found
		return val;
		
	if(arr[val] < key) // rerun function if key is in top half
	 	return b_search(arr, val + 1, end, key);
	if(arr[val] > key) // rerun function if key is in bottom half
		return b_search(arr, start, val - 1, key);
		
	return -1; // return -1 if key is not found
}

int search(int * arr, int length, int key)
{
	return b_search(arr, 0, length - 1, key); // call helper function
}