this is for holding javascript data
Alex Varghese edited q3.tex
about 10 years ago
Commit id: c4872cc10fd2c0c5571d850779b01ccc2f9d5633
deletions | additions
diff --git a/q3.tex b/q3.tex
index f11f443..cbc8e9b 100644
--- a/q3.tex
+++ b/q3.tex
...
\item
To sort the scores of the participants for each university, we can use \textbf{mergesort} for our comparative sorting algorithm. Our initial array will just be filled with the (unsorted) scores for every student of every university, and since the array is filled with numerical values, a simple mergesort (with no modifications) is needed to sort the scores. Disregarding space efficienecy, mergesort has a worst case of $nlogn$.
For our non-comparitive sort, we can use counting sort because we do know that there is a maximum and minimum score, so the possible values for the
radix counting sort are bounded. Also all the values are integers so there will be no issues using this sort which will take n time.
\item
To sort the scores of participants given k files, where each file includes the sorted scores from specific universities, we will make use of a max heap.
First we will take the first element of each array (university), and insert it into a max heap. This takes $klogk$ time. Since these arrays are all sorted we will be inserting the largest elements, then we will pop out the largest element. Popping the
smallest largest
value takes $logk$ time. This value is the highest score in all the
universities universities.
Then, we examine the popped element, and if the element is from array $i$, then the next element we add to the heap will be from array $i$. This takes $logk$ time.