CPSC319 Assignment 1 Solved

Implementation and Comparison of Sorting Algorithms  

Computers are frequently used to sort lists of items, especially when these lists are long. Many sorting techniques are available, some more efficient than others. In this assignment, you will implement four different sorting algorithms in a Java language program, and compare their performance. The sorting algorithms you will implement are:

1   Selection Sort

2. Insertion Sort

3. Merge Sort

4. Quick Sort

You can base your own code for these algorithms on the code given in the textbook or discussed in lectures, or on code found from other sources. Be sure to cite the source for any code you borrow or adapt, putting the citation in comments in your program.

Your program will create an array of integers to be sorted. The user will be able to specify whether the array is filled with integers in random order, ascending order, or descending order. The length of the array is arbitrary and will be specified at run time. The array may contain duplicate numbers. Your program will take this array and sort it into ascending order, outputting the sorted list to a text file, one item per line. The sorting algorithm to use and the name of the output file will also be specified at run time using command-line arguments.

 Your program will time how long it takes to sort the array. Be sure to time only the sorting function itself, and not the time taken to fill the array with numbers or do input or output. Your program will print the time in seconds to the screen (standard output). You will use this data to help compare the efficiency of the four algorithms.

Write a program in the Java programming language to implement the above requirements. Your program will be invoked from the command line as follows:

          java Assign1 order size algorithm outputfile 

where Assign1 is the name of the file containing executable bytecode for your program, order is the order of the integers in the input array (use one of the following strings: ascending, descending, random), size is the number of items in the integer array to be sorted, algorithm specifies the sorting technique to use (use one of the following strings: selection, insertion, merge, quick), and outputfile is the name of the output file where the sorted list will be written to. Be sure your program detects any command-line input errors (for example, a negative number for size), printing out an error message, and aborting the program.

Experiments and Data Collection
You will use your program to perform a series of experiments that help you to compare the efficiency of the four sorting algorithms in the best case (input array in ascending order), worst case (input array in descending order), and average case (input array in random order). At the very least, use the following sizes for the array length: 10, 100, 1000, 10,000, 100,000, and 1,000,000. Determine the timings for all four algorithms using these inputs.