|
Analysis of sorting
Description
Implement a divide-and-conquer sorting algorithm like mergesort or quicksort
in perl. Analyse if (or when) it is useful to switch to another computationally
simpler sorting algorithm like insertion sort or some version of bubble sort
when the sub sets become small enough by implementing such a switch and measure
running times. This project requires a 2-5 pages report with graphs of your
findings, discussion of running time for your chosen sorting algorithms and a
conclusion.
Sorting algorithms are of general interest in programming. There is no
special bioinformatic approach.
Input and output
There is no input to this program. It should generate large lists of random
numbers to be sorted. You can add options of your own choosing, that controls
f.ex. the size of the lists, when to switch to the simple sort, and so forth.
The output must by some comparable time measure that can be easily translated
into a nice graph, where it can be seen when (if) to switch sorting algorithm.
You must also be able to prove that your sorting works, f.ex by printing
out the sorted list (with an option perhaps), or by an internal foolproof check
of your resulting sorted list.
Sorting algorithms
There are lots of information and implementations (in pseudo-code) of
different sorting algorithms on the net.
Wikipedia
has a lot to say about sorting.
Check it out.
|
