((Explanation))

My program works completely. 

(Heap Initialization)
Preconditions: Inputting an array of length zero will not cause the program to crash, but you will not receive any useful output in either time lapsed or resulting arrays.

To initialize the heap, I looped through the values in the array from index 0 to the last index and for each value, I percolated up as necessary, treating everything with a lower index as part of a heap structure, as the percolation had already been applied to those indices. My percolation method: checked if the value at the current index was less than its the value at its parent index in the heap structure, if so, switch them and repeat as necessary.  

(Iteratively returning min from heap)
I took the minimum value from the heap (the top of the heap, so index=0), and swapped it with the value at the back of the array. I then percolated the value I inserted at the top of the array as necessary, until it fell into place. My result for this singular iteration would be the smallest value at the last index of the array, and a min heap in array form for the rest of the indices. I then repeat this for the penultimate value, which obviously results in the second smallest value in the second to last spot in the array, and a min heap for the rest of the spots. Continued for the entire length of the array, I receive a reverse ordered list, which I reorder to be correctly sorted in O(N), which maintains the overall heap sort O(Nlog(N)). 

(Quad Sort - insertion sort) 
Preconditions: Inputting an array of length zero will once again not cause a crash, but it doesn't really make sense to do. 

For each index in the array, we consider all values with an index less than it, and move each value in the array to the right until the value we're considering fits between the last value moved, and the next value to be moved. That is, we are iteratively inserting into progressively larger already sorted sub-arrays. 

((Test Plan))

We have tested some edge cases, such as inputting arrays of length 0 and of length 1 and 2 to ensure that everything works as expected. We have also tested very large input arrays, such as size 1 million. These have all behaved as expected. 

For each, we even tested the arrays sorted by our heapsort and insertionsort algorithms against Java's (presumably more robust and veracious) built in Arrays.sort, and received the same values. We are consequently confident that both the heap initialization and construct min array code blocks work because a properly sorted array demands that both be implemented completely correctly.


((Experiments))

(Small sized input arrays)
Hypothesis: quadSort is better for smaller values in all instances because it does not have to deal with heap instantiation. 
Results: We have compared random inputs, sorted inputs, and reverse sorted inputs on both heapsort and quadsort, all for varying sizes of arrays. For the remainder of the writeup, let N=number of elements in input array. We have found that in every run we've completed with N<~100, quadSort completes with faster run time in all three Random, Sorted, and Reverse Sorted input. 

(All other sized input arrays)
Hypothesis: heapsort wins out for all instances, expect previously sorted input in which case abstractions that turn out to be unnecessary end up taking too much runtime. 
Results: For N>~100, heapsort seems to have better run time than quadsort in both Random and Reverse sorted input. However, quadsort wins out in sorted input for all N. 

((Conclusions))

(Small sized input arrays) 
The results of our experiment are expected, as the instantiation of the heap takes more time than it saves for small values of N, while the quadSort experiences no such lag. We also notice a property of O(N) and its contribution to this observation: for small values of N, the term with leading degree in O(N) may not be the leading term, and so this can help us understand why quadsort is faster for small values of N. 

(All other sized input arrays) 
Once again, the results of our experiment are expected. With large N, the instantiation of the heapsort (which takes O(NlogN)) no longer causes lag relative to the quadSort (O(N^2)). We start to see the O(N) term dominate, and the efficiency of heapsort comes forth as it does not have to compare every value against every other value like quadsort does. Quadsort wins out for sorted inputs because, unlike heapsort, it does not need to instantiate a heap in order to do the sorting. Additionally, it does not need to actually switch around any values while our implementation of heapsort does. This makes quadsort more effecient for already sorted input. 

((Honor Code))

 I have neither given nor received unauthorized aid on this assignment.
 
 Signed: