Exercise 5

Sorting

Due Date - March 10, 2012 @ 2:00pm

Introduction

Sorting is the problem of organizing a set of items in an order so that a special attribute of each item (called the "search key") is increasing or decreasing within the item sequence. This operation is important in many applications, such as for databases, and therefore, it has been extensively studied by many researchers. Many algorithms have been developed for sorting, all of them try to optimize time complexity and memory resources. Sorting is not a big topic these days because many consider it to be a solved problem. However, no matter if you are interested in creating a more efficient sorting algortithm, sorting should be studied by programmers because many concepts from sorting algorithms can be applied to many other kinds of algorithms. Sorting is also useful when learning how to write efficient code.

In this exercise you will be implementing Selection Sort, a sorting algorithm that iterates through a set of numbers.  In every iteration it finds the minimum value of the remaining positions in the loop. Then it swaps the minimum element with the element at the current position and goes to the next iteration. By the end of the iteration the set of elements will be sorted.

Links about sorting:

Animation of famous sorting algorithms.

Video explaining Selection Sort

Selection sort (from Wikipedia)

Assignment

      Write a C program that performs selection sort on a set of numbers given in a file and prints the sorted list as output. 

Output Code

    You can download the code for the expected output here.  The output code contains two functions and one structure.

List - Structure of a List.

PrintList - Prints the list given as an argument.

PrintError - Prints the appropriate error messages if you have problems opening a file or there is the wrong number of command-line inputs

Specifications

1. You should print an error message and exit the program with a value of EXIT_FAILURE if the user does not give enough command line arguments.  The expected output is in the output code (error code 1).
2. You should print an error message and exit the program with a value of EXIT_FAILURE if the user gives an invalid file.  The expected output is in the output code (error code 2).
3. You should print an error message and exit the program with a value of EXIT_FAILURE if the dynamic memory is not allocated properly.  The expected output is in the output code (error code 3).
4. The name of file containing the set will be given as a command-line argument.
5. You can assume the values in the set to be integers, one for each line in the input text file. (Hint: use strtol() to convert from strings to integers.)
6. Your sorting program must be implemented using a selection sorting algorithm.
7. There is no maximum number of values in a set.
8. You will need to dynamically allocate memory to store the set.
9. Only one instance of a value will be in a set. (Each value in the set is unique).
10. You should print out the set only once it is sorted using PrintList function. For this you will need to use the list structure.
11. The largest number possible in the set is 1000000

Warning

You are not allowed to use anything like the following:

    int count = 0;
    ... /* find the number of elements */
    int array[count]; 

You have to use malloc and free.

Compile and Execute

You will need to create a Makefile to compile your code.  You can find an introduction on Makefiles here.  You should use "gcc -Wall" instead of "gcc".  This will turn on warning messages.  Treat warning messages seriously because warnings are very likely errors.

Warning messages are often indications of errors. For this assignment, you lose 0.1 point for each warning message. The command will generate an executable file called "ex5."

To execute this program, type

./ex5 <filename>

The argument (argv[1]) is the file containing the set

Testcases

You can find a testcase generator here.  It is compiled to run on the machines in EE206.  After download you need to change the permissions of the file.  To do this type

chmod 711 testgen

To execute it, you should type

testgen <# of values to be sorted> <lower bound of numbers> <upper bound of numbers> <filename of unsorted list of number> <filename of sorted list of numbers>

 

Submission Procedure

   Create a zip file contain the folowing files

• At least 1 .c and 1 .h file
• Makefile - The makefile should produced the executable "ex5".

   and then submit to the course grading website. 

You need to provide a user name and a password through Blackboard before submission.  The user name and the password are different from your Purdue career account.

.h Files

A .h file, short for header file,  typically contains the following

• All the the C library files that your program will need (i.e. stdio.h, stdlib.h, etc.)
• All constants you will need.  Constants can be defined using the #define command.  An example would be  "#define MAXLEN 102".
• All function headers  for the function in your program. 
• All Structures used.

Once completed, your .h file should be included in your .c file.  This is done by typing the following: #include "filename.h"

Memory Management

Memory management (allocation and release) is an important part of ECE 264. You have to allocate enough memory to make your program work. You have to allocate and release memory as needed. You are not allowed to allocate a large piece of memory regardless of the input size. We will restrict stack size to prevent that. You will receve heavy penalty (50%) if your program does not release all memory (i.e. memory leak). We will use valgrind to check for memory leaks.

New! If you use Eclipse, you can set up valgrind following this link.

Grading

The maximum score for this exercise is 2.0 points.

Examples

If the set is the following

{185, 152, 154 , 1, 13, 95, 85}

Your program should output

1 13 85 95 152 154 185

Hint

If you read the file using fgets, consider to use strtol to convert a string to an integer. Check this page about how to use strotol.

You can also use fscanf to read an integer from a file.