CMPE 250 – DATA STRUCTURES & ALGORITHMS

Project #3

Due: 7.8.2005 Sunday at 12:00 PM

Comparison of Sorting Algorithms

In this project, you will compare different sorting methods. For each method, you will use various data (to be sorted) that has specific characteristics. Then, you will compare time complexities of each sorting method.

Sorting Methods

You will implement the following sorting methods. Each method sorts the data in ascending order.

·        Insertion Sort

·        Shell Sort

·        Quick Sort: Use Median-of-Three pivot picking method.

Data to be Sorted

There will be three different datasets (whose elements are of type long) to be sorted. You will generate these datasets in your program. Each dataset will be of size N (i.e. 10000), covering a range of values from 1 to N (no duplicates allowed).

·        Presorted Data : Already sorted in ascending order.

·        Reverse Ordered Data : Already sorted in decreasing order.

·        Fully Random Data

Your program will get two inputs from the user: 1) dataset size (N), 2) Sorting algorithm (1:Insertion sort, 2:Shell sort, 3: Quick Sort). Program will output the execution timings for 3 datasets (Presorted, Reverse Ordered, Random). For random dataset, you have to perform 10 independent runs, and then give the average sorting execution time. For each method, you will report timings to sort each dataset. Show all the results in one table.

Implementation Details

·        Try to use object oriented concepts as much as possible.

·        Make sure your code compiles with JDK 5.0.

 NOTES:

• Source code should be cleverly commented.
• Give a nice report explaining your design, algorithms, assumptions and results. Be compact and clear.

• For projects, you need to submit both your .java files and your report. Submit your report as hard copy in stapled form and e-mail your .java files to konur@boun.edu.tr in zipped form with CMPE250 Project X on the subject line. The name of your zip file must be CMPE250_[Your_name]_[Project X].zip (e.g. CMPE250_UmutKonur_Project1.zip).
• Do not submit your report in electronic form or your source code as hard copy.

• You can leave hard copy documents to Umut Konur at ETA413.
• Late giving policy may be strict, so try to finish on time (no flexibility will be provided).
• Do not cheat!