[Home | Assignments | Links | Grades | CIS 313]
CIS 323 - Assignment 5
Sorting
Due Thursday, March 11, 2010
Description
You can write your code in any programming language for this assignment.
I would encourage you to use a different programming language than C++ or Java. It is good practice for you to implement algorithms in other languages and you will probably find that it is not terribly difficult.
The goal of this assignment is to implement and compare sorting algorithms.
Task
- Implement quicksort
- Implement at least 2 other sorting algorithms
- Compare running times for different input sizes
Quicksort pseudocode can be found in chapter 7. Heapsort in chapter 6. Insertion sort in section 2.1. Merge sort in section 2.3. Wikipedia is also a good source for pseudocode. Beware not to get tempted to copy actual implementation code. You will not learn anything from this.
Input/Output
The input will be formatted in the following way:
- A number n, indicating how many numbers to insert
- n number of lines, each with a number, either positive or negative.
Duplicate numbers might be be inserted.
Here is an example:
- Input:
-
5 4 35 9 -10 48 - Output
-
-10 4 9 35 48
Testcases
You can find test inputs here. You can create your own using the random number generator found in the same folder. It's a python file, courtesy of Peter Boothe, with a few modifications.
What to turn in
- Implementation of each of the sorting algorithms you have implemented.
- A half to one page write up of your findings. Including:
- Which algorithm is faster.
- A graph showing running times of the algorithms as function of input size.
- What do your results show about the asymptotic running time of the algorithms.