Description
Merge k Ordered Lists Efficiently
You are required to implement correctly and efficiently an O(nlogk) method for merging k sorted sequences,where n is the total number of elements. (Hint: use a heap, see seminar no. 2 notes).
Implementation requirements:
● Use linked lists to represent the k sorted sequences and the output sequence
Input: k lists of numbers >,
Output: a permutation of the union of the input sequences: < >
Thresholds
7 Adapt heap operations to work on new structure (list_index, key); use minHEAP
- 9 Correct and complete algorithm implementation, with demo on a smallsized input
- 10 Evaluation, interpretations, discussion
Evaluation
! Before you start to work on the algorithms evaluation code, make sure you have a correct
algorithm! You will have to show your algorithm works on a smallsized input (e.g. k=4, n=20).
We will make the average case analysis of the algorithm. Remember that, in the average case, you have to repeat the measurements several times. Since both kand nmay vary, we will make each analysis in turn:
|
Threshol d |
Requirements |
|
5 |
Generate k random sorted lists, having n elements in total (n and k given as parameters); merge 2 lists |
- Choose, in turn, 3 constant values for k (k1=5, k2=10, k3=100); generate k random sorted lists for each value of k so that the combined number of elements in all the lists (n) varies between 100 and 10000, with a maximum increment of 400 (we suggest 100); run the algorithm for all values of n (for each value of k); generate a chart that represents the sum of assignments and comparisons done by the merging algorithm for each value of k as a curve (total 3 curves).
- Set n = 10.000; the value of k must vary between 10 and 500 with an increment of 10; generate k random sorted lists for each value of k so that the combined number of elements in all the lists is 10000; test the merging algorithm for each value of k and generate a chart that represents the sum of assignments and comparisons as a curve.
- Interpret your charts.
