Spring 2009 ICS 311 Project 1

Analysis of Common Sorting Algorithms

Overview

Write a Java console application that:

• implements five sorting algorithms: Insertion Sort, Selection Sort, Bubble Sort, Merge Sort, and Heap Sort.

• reads a sequence of integers from a text file.

• records and displays the number of operations required to sort the integers.

• writes the sorted integers to another text file.

Write a concise report that:

• analyzes the run-time performances of each sorting algorithm.

• includes graphs generated from the output of your program that demonstrate the time complexities of each algorithm.

Application Input Requirments

Your application shall run based on command line input with the following format:

java JadeChengP1 filePath sortingMethod iterations

1. filePath — a path to a text file that contains a sequence of integer numbers seperated by whitespace. Here is an example of the input file.

2. sortingMethod — the method used to sort the integers from the file. The particular method shall be identified by one of the following values:

   • insertion — use Insertion Sort

   • selection — use Selection Sort

   • bubble — use Bubble Sort

   • merge — use Merge Sort

   • heap — use Heap Sort

3. iterations — the number of times to sort the sequence of integers. Your program shall loop over this number. For each iteration i, your program shall read i number of integers from the file, sort those numbers using the specified sorting method, and display the number of operations required to perform the sort.

Application Output Requirments

Your application shall write a tab-delimilated table to standard output. Each line corresponds to one iteration. Each line consists of two columns. The first column indicates the iteration number (the number of integers sorted). The second column indicates the number of operations performed for that iteration by the specified sorting method.

Hint: This output format is suitable for pasting into a spreadsheet that can be used to generate the graphs required for the analysis report.

Your application shall create a text file named sorted.txt in the currect directory. This file shall contain the sorted sequence of integers read from the aforementioned file on the last iteration. Each number shall be seperated by whitespace.

Example

In the following example, the application reads up to 10 integers from the random.txt file that exists in the working directory. It uses the merge sort and reports the number of operations performed.

uhunix2:/home/26/yucheng% java JadeChengP1 random.txt merge 10
1	1
2	6
3	13
4	20
5	29
6	38
7	47
8	56
9	67
10	78

In the first iteration the application read 1 integer from the file and performed 1 operation for the entire sort. So it output "1\t1\n" to indicate 1 item was sorted in 1 operation.

In the second iteration the application read 2 integers from the file and performed 6 operation for the entire sort. So it output "2\t6\n" to indicate 2 items were sorted in 6 operation.

This continued until the tenth iteration in which the application read 10 integers from the file and performed 78 operations for the entire sort. It output "10\t78\n" to indicate 10 items were sorted in 78 operations. At this point, the application reached the maximum number of iterations specified on the command line, so it terminated.

uhunix2:/home/26/yucheng% cat sorted.txt
26285
53365
66759
77237
218827
235829
419200
437825
488675
689362

After excuting the program, sorted.txt exists in the current directory. It contains the first ten integers from the random.txt file in sorted order.