Electrical Computer Engineering Department, University of Maryland, College Park
Fall 2018 ENEE150 Dr. Gang Qu
Project 1: Evaluation of Sorting Algorithms
Discussed: September 13, 2018
Due date: 11:59 pm September 28, 2018
Project Objectives
1. Learn various sorting algorithms and compare their performance
2. Master basic programming concepts: array, file I/O, and command line argument
3. Practice on function prototyping, implementation, call and return
4. Understand recursion and how to apply it to solve (sorting) problems
5. Get familiar with UNIX programming environment
Project Description
In this rject, you wil implement four sorting algorithms, bubble sort, insertion sort,
radix sort and either merge sort or quick sort and compare their efficiencies. The input to your
program will be multiple files containing lists of unsorted numbers. Your program should sort
these numbers with a given sorting algorithm, and output to a file the sorted numbers. You will
also need to submit a report as part of the project displaying the performance of the sorting
algorithms and the exact amounts of time each algorithm took to process different files. By doing
so, you will not only learn how to implement the sorting algorithms, but also understand their
differences and advantages.
General Requirements
For this project, your program should run with the following command line arguments:
a.out input.txt k outputFile.txt
where a.out is the compiled executable, input.txt is the input file name (which will be
different for each of the files), k is an integer representing the sorting algorithm to be used, and
outputFile.txt is the output filename. You should do a safety check on this. Each of these
command line arguments are elaborated below.
Input file
There will be multiple inputs files with lists of different sizes that you will need to process.
The first line of each input file will be a single integer representing the total number of lines (or
numbers). The second line is an empty line and each line after that will contain exactly one (1)
integer. You can assume that there will be no more than 500 numbers to be sorted. These
numbers can be positive, zero, or negative, and duplicate numbers may also exist.
Your program will be sorting each of these files multiple times, using different sorting
algorithms. If a file does not exist, your program should print an error and exit. If the file does
exist, you can assume that the file follows the format given above.
Sorting algorithms
The integer k in the command line arguments represents the sorting algorithm to be used:
1 bubble sort 2 insertion sort 3 radix sort 4 merge sort or quick sort
If the integer inputted is not one of these four choices, the program should print error and exit.
Electrical Computer Engineering Department, University of Maryland, College Park
Fall 2018 ENEE150 Dr. Gang Qu
For buble sort, insertion sort, and radix sort, he exact implementations are up to you, as
long as they can sort the numbers correctly and collect the performance metrics, such as the
number of comparisons and swap/copy data, but for merge sort and quick sort you must choose
one to implement and must implement whichever you choose recursively. Additionally, before
your implementation of bubble sort, briefly explain the algorithm you have chosen to code in the
comments. Keep in mind that although you’re not required to implement bucket sort, it’s
recommended to do so and use it for the implementation of radix sort.
Output file
The first section of the output file should be in the same format as the input file:
- The first line should contain an integer with the number of lines that will be processed in
the file, followed by an empty line
- The rest of the file should contain the integers sorted in ascending order
The output file will be compared with the expected output using the “diff” command, so it is
important that the exact format is followed to generate the output file.
Performance metrics: comparisons and swaps/copies
The efficiency or performance of a sorting algorithm can be evaluated by the number of
comparisons between array elements, and the number of swaps or copies it needs to create the
sorted array. In this project, you need to implement the following three functions for this
purpose. A description of each of the functions is given below:
● int compare(int array[size_of_array], int index_1, int index_2)
This function compares two numbers, array[index_1] and array[index_2], in
the array and returns an integer to indicate whether array[index_1] is greater than,
equal to, or less than array[index_2]. More specifically, it returns a positive integer
if array[index_1] is larger, a negative integer if array[index_1] is smaller,
or 0 if the two numbers are equal. During the sorting process, whenever you need to
compare two array elements, you must call this function. So when the array is sorted, the
number of times this function is called will be the number of times you compare two
array elements. You need to implement a mechanism to count how many times this
function is called.
● void swap(int array[size_of_array], int index_1, int index_2)
This function swaps two numbers, array[index_1] and array[index_2], in the
array. When you implement quick sort/merge sort and insertion sort, you must use this
function every time that you wish to swap two numbers in the array. You also need to
implement a mechanism to count how many times this function is called.
● void copy(int source[size_of_array], int
destination[size_of_array], int index_in_source, int
index_in_destination)
This function copies array element source[index_in_source] to another array as
element destination[index_in_destination]. Merge sort, as we have discussed in
class, needs to copy some data into a temporary array, and then re-copy that data back to
the original array. Every time you copy some data from one array to another, you must
use this function. You also need to implement a mechanism to count how many times this
function is called.
Electrical Computer Engineering Department, University of Maryland, College Park
Fall 2018 ENEE150 Dr. Gang Qu
Note: If you copy an array element to a temporary variable, this will also count as a copy or
one call to function copy. If you use this temporary variable for comparison, that will also be
considered as one comparison.
Report
The exact layout of the report is up to you as long as it contains all the information listed
below, however, a .docx file containing a labeled table with all the information required will be
provided in the project folder which you may choose to use.
- For each input file, list the file name, number of elements in the file, and the comparison
and swap/copy data.
- Alongside each file, also list the user time it takes for each sorting algorithm to process
the data. (An example of how to obtain the user time for your code will be provided in
the public folder)
- Your program will sort each file at a time and keep track of the number of comparisons,
the number of swaps, the number of copy operations it takes to sort. After sorting all the
lists, calculate the average of these numbers and print it out, keeping two digits after the
decimal point. There will be three values displayed, one for the average number of
comparisons and two for the average number of swaps and copies, respectively.
Make sure that all the values listed are properly labeled and kept organized. After all the data is
displayed, write a few sentences at the bottom of the report about the different sorting algorithms
and their efficiencies when being used to sort data of different sizes.
Project Requirements:
1. The project must be implemented using C under the GLUE UNIX system in a file named
p1.c which should be submitted with the following command
submit 2018 fall enee 150 010x 3 p1.c
2. Your submission must conform. to the expectations outlined above for program execution
and input/output files.
3. Your submission must implement bubble sort, insertion sort, radix sort and either merge
sort or quick sort, and create the functions compare(), swap(), and copy().
4. Code must be reasonably commented to allow a user to follow the flow of their program,
as well as neat and orderly.
Grading Criteria:
Corect handling of input/output commands and files: 10%
Corect implementation of compare(), swap(), and copy(): 15%
Corect implementation and output of sorting algorithms: 60%
Coding style. and documentation: 5%
Report 10%
Files that do not compile will be given a 0. The late submission penalty: -20% per day and no
submission will be accepted 2 days after the due date.