CS209 lab2
http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l2.html
-
For this lab you should submit all source code (python
files), and the result(s) of running the program on (a few)
test cases.
The source code must
be well presented (indenting, spaces, reasonable variable/function names,
etc.) and must include comments (as a rough guideline - aim to have nearly as
many comments as lines of code).
-
The above material should be uploaded to BLACKBOARD
before
the deadline of midnight
Thursday 8th. February 2018. You will lose 20% for each day
(or part of day) the lab is late.
-
Plagiarism (the unattributed copying of work from other sources
(internet, fellow students,....)) will not be tolerated.
You risk getting zero for your lab if it is found to be
plagiarized.
http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/
Consider the INSERTION SORT and MERGE SORT algorithms covered in lectures, with code
at
http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/
-
Build a new hybrid recursive algorithm, that calls
insertion sort
and merge sort alternately. So, say, first time around
merge sort is called, and this function will then call two copies of
insertion sort, which then calls merge sort, etc. (with of course
successively decreasing sizes of the lists).
Your program will have to have two functions.
(Example: Say we were sorting [4,-1,2,9,0]. We call mergesort
on this, which will lead to a merge of the 2 lists [4,-1] and [2,9,0]. For
[4,-1], we call insertion sort, which will insert the element -1 into
the list [4]. For [2,9,0] we call insertion sort, which will insert 0
into the list [2,9]. For [2,9], we call merge sort which will merge the
lists [2] and [9]).
-
Adapt your code as follows. If the (sub)list has an even number
of elements, always carry out mergesort, while if the (sub)list has
an odd number of elements, always carry out insertion sort (all within
the one algorithm).
©
NUI, Galway