Sorting algorithm

The exercise is to develop sorting algorithms, to test them, to measure their performance, and to compare the measured performance to theoretical predictions.

Write a report that describes the algorithms in English and in pseudo code. Give the source code in an appendix. Predict the time order of your algorithms. Tabulate and graph the measured performance of your algorithm and discuss how the actual performance relates to the predicated performance. Discuss how the performance of the algorithm or implementation might be improved.


1. Develop an algorithm to sort a list of floating-point numbers. Check its behaviour in various cases, such as, but not limited to, the following:

1.1. Can it sort the empty list?
1.2. Can it sort a list with one element?
1.3. Can it sort a list with two elements?
1.4. Can it sort a list with a general number of elements?
1.5. Can it sort a list where some of the elements are the same?
1.6. Can it sort a list where some of the elements are infinity or minus infinity?
1.7. Can it sort a list where some of the elements are minus zero?
1.8. Can it sort a list where some of the elements are NaN?
1.9. Can it sort a list of pseudorandom data or data obtained from the world wide web?


2. Predict the time order of the algorithm, for example in the following ways.

2.1. Predict the best case time.
2.2. Predict the worst case time.
2.3. Predict the average time.
2.4. Cite a scientific work that gives predictions of the algorithm’s time.


3. Measure the time the implementation takes, for example in the following ways.

3.1. Put a variable in the “important” loops and increment it so that it reports the number of times the loop was executed.
3.2. Use an operating system timer to record the execution time of the program.
3.3. Use an operating system timer to record the real-world time of the program.


4. Tabulate the data. For example:
4.1. On screen.
4.2. In a file.


5. Graph the data. For example:
5.1. By hand.
5.2. By computer program.