This lab should be done with a partner of your choosing.

Lab 2 Goals:

• Practice with C programming basics: declaring vars, type, arrays, functions
• Writing C code and functions that uses statically declared arrays
• Practice writing and using C functions. Pass by value: basic types and array parameters.
• C I/O: scanf, printf, and using a file reading library.
• More practice with top-down design.
• Using a Makefile.

First, both you and your partner should run setup31 to grab the starting point code for this assignment. Suppose users molly and tejas which to work together. Molly can start by running

  [~]$ setup31 labs/02 tejas

Once the script finishes, Tejas should run

  [~]$ setup31 labs/02 molly

Please note that the script tries its best to ease the initial creation and cloning of git repos and it tries to be smart and check that each partner agrees that they are partners. That said, there are some race conditions and if there are uncooperative formations of partners, the script and the instructor will get confused. If you play nice with the script, it will play nice with you.

For the next step only one partner should copy over the starting code

  [~]$ cd ~/cs31/labs/02
  [02]$ cp -r ~adanner/public/cs31/labs/02/* ./
  [02]$ ls
  Makefile  sorter.c  readfile.c  readfile.h 
  floats.txt floats2.txt floats3.txt

Now push the changes to your partner

[02]$ git add Makefile *.c *.h floats*.txt
[01]$ git commit -m "lab 2 start"
[01]$ git push

Your partner can now pull the changes. In this case if Tejas wishes to get files Molly pushed, he would run

[~]$ cd ~/cs31/labs/02
[02]$ git pull

The starting point code includes:

1. Makefile: a makefile you should use to compile your program
2. floats.txt, floats2.txt, floats3.txt: example input files to your program (you should use these to do most of your testing as you incrementally implement and test parts of your solution. However, you will ultimately want to create new files to more extensively test your program.)
3. readfile.h, readfile.c: DO NOT CHANGE ANY CODE IN THESE FILES. This is a file reading C library. You can make calls to functions in this library in your program. This functionality will be explained below.
4. sorter.c: the starting point file into which you will add your C solution. The starting point code includes two functions:
• get_filename_from_commandline: takes a string and the command line arguments and initializes the string to the filename command line argument. You should not change this function, but feel free to change where it is called in your final program.
• open_file_and_check: this function does the work of opening the file and double-checking that the open was successful, so that you don't have to worry about how this is accomplished.
The rest of the lab 2, an implementation of a sorting algorithm, should be added to this file, as should good comments.

To compile and run (and use make to compile, otherwise you need to compile and link in the readfile library by hand, which you don't want to do):

     make
     ./sorter floats.txt

For this lab, you will implement program that sorts floating point numbers using a sorting algorithm of your choice in C. Your program will read a collection of unsorted floats from a file, store those floats in an array, provide some information about the floats to the user, sort them from smallest magnitude to largest magnitude (i.e., ascending order), and print them out in sorted form to the user.

Program Start-up

Your program will take one command line argument, which is the name of the input file containing floating point values, one on each line. There is no guarantee that the input file is in sorted order, so you program must contain routines that sort the integers before outputting them to the user. Here is an example command line:

./sorter floats.txt        

The code to get the file name string is provided for you in the starting point code.

File Format

The input file format consists of several lines of an ASCII file. A properly formatted file will contain a short header, consisting of a single line with one integer and two floats on it. These numbers represent the total number of integers in the file, as well as the minimum and maximum to-be-sorted float value in the file. These numbers will be written like this:

number_of_floats minimum_float_value maximum_float_value  

For example, here is the header of a valid input file:

4 0.0 9.0

This header indicates that the file contains a total of 4 floats that need to be sorted. In addition, the smallest float value seen in the file is 0.0, and the largest is 9.0. You may not need to know the minimum and maximum values to successfully sort the values, but you will need to inform the user about the range of values being sorted. With the starting point code are one or more sample test files you can use to test your code. Every line after the first line in the file will contain a single floating point number. These are the float values that must be sorted. For example, a file containing the header we just saw might look like this (after the first line):

0.0
2.1
9.0
5.3

With the starting point code is a readfile library that contains functions you can use to read values from the file. See the "File I/O" section below for more details.

File I/O

For this assignment you will use functions in the provided readfile library (in the files readfile.c and readfile.h). You should not change any code in these files. The readfile.h file contains function prototypes for the readfile library. There are function comments in this file that describe each function and a high-level comment describes how to use the library.

Here are the general rules for how to use these functions:

1. open a file by calling: open_file, passing in the name of the file to open as a string (open_file returns 0 if the file is successfully opened, and -1 if the file cannot be opened).

2. make calls to read values of different types into program variables: read_int, read_string, read_float. These functions take arguments much like scanf does: they need to know the memory location of where to put the value read in. For example:

   int x;
   float f;
   char s[20];
   ...
   // these functions return 0 on success or -1 if read fails or
   // if there is nothing left to read (end-of-file has been reached).
   ret = read_float(&f); // returns 0 on success, -1 on EOF 
   ret = read_int(&x)    // returns 0 on success, -1 on EOF
   ret = read_string(s)  // returns 0 on success, -1 on EOF
   

3. close the file when you are done with it: close_file

If you are curious, the implementation of these functions is in readfile.c. You can take a look and see how it uses the C FILE * interface and fscanf functions for reading. We will use this interface directly later in the semester.

Array of Floating Point Data

The floating point data read in from the file should be stored in an array of C floats. You can implement any sorting algorithm of your choosing including slower quadratic sorts like Insertion Sort and Selection Sort. You do not need to implement anything fancy like Quick Sort or Merge Sort. In fact, you probably don't have enough C tools right now to implement Merge Sort.

You may assume that there are never more than 100 numbers to sort.

Print the Unsorted Floats (Possible Function)

You should print the contents of the input file in the original order before starting the sorting function. In addition, you should inform the user about the information contained in the file header, by printing out the values contained there in a human-readable way. Note that you will also need to print out the sorted values later on, so it is good code design to create a separate function that prints arrays for the user. Hint: be careful about how many digits you print when attempting to print float values using printf. C offers you the ability to specify the precision, which may be useful so that, for instance, 9.0 doesn't print out at 9.00000....

Function to Sort the Floats and Print them

You should write a function that sorts the floating point values. You can implement any sorting routine you like and it does not have to be optimal. Options like Insertion Sort and Selection Sort are pretty straightforward. If you had CS35 before, you may challenge your C writing skills by trying Quick Sort. Do not try to implement Merge Sort. We need some extra C tools to implement this one.

The sorting algorithm must sort the floats without creating a separate, auxiliary C array (this is why you can't do merge sort). This will be facilitated by a swap function, which will be described below. Sorting will also be facilitated by a check function, which looks over the array of floats and determines whether they are, in fact, sorted, or not. This function will also be described below. After the array is sorted, the primary sorting function should print the floats once again, as a sorted collection.

Swapping Function

In service of the primary sorting function, mentioned above, you will need to write a function that takes three input arguments: an array of floats, and two additional integers that describe positions in the array. Given this information, the function should swap the values in the array at the specified positions.

Remember that for this function, and any other function you write, you should declare the function before main(), and define the function down below main(). Doing so is considered good coding practice. However, if you decide to define your functions below main(), you absolutely MUST declare them first.

Checker Function

Also in service of the primary sorting function, mentioned above, you will need to write a function that takes two input arguments: an array of floats, and an additional integer that represents the number of integers to be sorted. In other words, how many unsorted floats did the program read in? Given this input information, the function will determine if the array is sorted, or not. Hint: since this function needs to know how many floats there are to be sorted, and since the checker function is being called by the primary sorting function, the primary sorting function will probably need that information, also.

This is a fairly large programming assignment, similar to something you may have done near the end of CS21. Use all you know about top-down design and incremental implementation and testing to help you implement a good modular and bug-free solution.

• Make use of Prof. Newhall's C programming resources and links and refer to example C code we've given you in class and lab.
• Your code should be well-designed, modular, robust, use meaningful variable and function names, and must be well-commented. This includes having a top-level comment describing your program and listing your and your partner's names and the date. In addition, every function should be well-commented. Read and follow the C Style Guide. This document describes what we expect for good function and program comments and has some tips for how to avoid line wrapping. Some of this documentation refers to parts of C that you have not yet learned.
• Before even starting to write code, use top-down design to break your program into manageable functionality.
• Your solution should have at least 3 function-worthy functions in addition to main.
• Use incremental implementation and testing, and use function stubs to help test program control flow.
• Your program should not use global variables. You should use only local variables and parameters. So, if a function needs a value from the caller, then that value should be passed in as a parameter. If a function needs some variables to compute what it needs to compute, then those should be declared as local variables inside the function. If you don't know what a global variable is, that is great, you won't make the mistake of using one.
• Make use of constants (#defines) for values that do not change in your program

• Make use of C programming resources and code that I gave you in class and in lab to help you figure out C syntax.
• Use debug printfs to help you see what your program is doing, but make sure to remove all debug output from your submitted code.

• Use CNTRL-C to kill a running program stuck in an infinite loop.

Here is output from a run of a working program. It does not show every possible run, or error handling, but should give you some idea of what a correct program may look like. Your program's output does not need to be identical to mine, but it should print out information in an easy to read way.

To submit your code, simply commit your changes locally using git add and git commit. Then run git push while in the labs/02 directory. Only one partner needs to run the final push, but make sure both partners have pulled and merged each others changes. See the section on Using a shared repo on the git help page.

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:42 PM