CS 216  Lab 12

For 8 April 2019

Using make to manage a project - A few files for implementing a sort. Four options, in quests/ :

1. quicksort/ Quicksort - an array of int - elegant but partition is tricky. Array will be filled with random numbers.
   
2. sort/   -- Easier  -- an array of int - by any means you choose (you might find your merge useful)
3. stringsort/       --  Will read words, and make an array of pointers to them, sort in dictionary order
4. listsort/           --  Will read words, and set up a "linked list" of them. -- For those familiar with Data Structures

In fact, you may code any sorting method you prefer, and you are free to change the name of the sort function, so long as you do so consistently. The real goal is to learn to use make. See below

make is a unix utility for "automating" the process of compiling, assembling and linking a program consisting of many files.

Compiling steps

gcc manages the steps of producing an executable program, which are:

1. preprocessing each .c files (carrying out #define and #include directives)
2. Compiling to assembly language (giving a .s file) - not usually saved
3. Assembling to machine code .o files
4. Linking .o files together, also with library routines (containing functions such as printf ), giving an "executable file." By convention, these usually don't hae a .extension. They have x (execute) permission.
   

Suppose there are several source files. Once you have compiled all of them to object files, then you discover one needs a change, you only need to recompile that one, then link them all together. (When you are all done, you can get rid of the intermediate object files.

For example, suppose you have the files: myfunctions.c and myprog.c, which uses myfunctions. The first time you compile, you can do this:

gcc -c myprog.c
gcc -c myfunctions.c 
gcc -o myprog myprog.o myfunctions.o

gcc -c myprog.c
gcc -o myprog myprog.o myfunctions.o

Header files (.h)

/* A main program that does I/O and calls functions prototyped in myfunctions.h */
#include <stdio.h>
#include "myfunctions.h"

make

the make utility is designed to describe tasks that need to be done on the basis of file times. It reads the file Makefile containing rules of the form:
target : prerequisites
"make updates a target if it depends on  prerequisite  files  that  have been modified since the target was last modified, or if the target does not exist." (from man make) Thereafter follow line(s) started with a tab character, with the command(s) required to update the target. This would a suitable Makefile for the program just described. We start from a goal, the executable file.

myprog : myprog.o myfunctions.o		# goal is this executable file
	gcc -o myprog myprog.o myfunctions.o
myprog.o : myprog.c  myfunctions.h	# (re)compile sources if necessary
	gcc -c myprog.c
myfunctions.o : myfunctions.c myfunctions.h
	gcc -c myfunctions.c 

Once Makefile is created (in the same directory,) all you need to type for a new myprog executable is, Ta-Da:

make

Quicksort

Quicksort is an efficient (O(n lg n)), recursive algorithm published by C. A. R. Hoare in 1961. We have discussed it in class. The basic idea is to 'divide and conquer' by partitioning an array into smaller and larger values, and then repeating the process on shorter arrays.

I have created a partially completed quicksort program as several files. You may make changes to any of them, and will have to complete what's wrong or unfinished. I don't think I made many syntax errors, but... You may change variable names to ones more meaningful to you, clean up my comments (which are rough outlines of the algorithm) and make your own.

Your task today is to create a Makefile for compiling and linking this program to produce the executable file dosort. and then to make, correct, test, re-make, until the program can be run. And just maybe, actually sorts an array. (But the goal is the process, really.)

The files are:

quicksort.h

contains prototypes of all the functions. included in all the .c files

qsmain.c

Main program, creates array of random numbers, prints it, calls quicksort and prints again.

quicksort.c

the quicksort function, a skeleton, you fill in the recursion.

partition.c

the tricky one. returns two pointers by storing them in addresses passed as arguments.

qsutils.c

utility functions: fillarray, which probably works, and printarray -- you must decide the details, however you want the printed array to look. Probably you should finish with a newline.

swap.s

The familiar swap function. Don't change it, it's been tested (details later)

Makefile

I just got it started, so you need to fill out all the details, for each file that needs to be compiled.

An easier way .... a simple sort

Perhaps you are overwhelmed by the complexity of partition. And it is a bit finicky. So if you prefer, code any simple sort you like, in the file sort.c.

The files are:        and they are in directory sort/ (instead of quicksort)

sort.h

contains prototypes of all the functions. included in all the .c files

sortmain.c

Main program, creates array of random numbers, prints it, calls sort and prints again.

sort.c

function that sorts, a skeleton, you fill in the method.

arrayutils.c

utility functions: fillarray, which probably works, and printarray -- you must decide the details, however you want the printed array to look. Probably you should finish with a newline.

swap.s

The familiar swap function. Don't change it, it's been tested (details later) You might find it convenient

Makefile

I just got it started, so you need to fill out all the details, for each file that needs to be compiled.

Notes: A random number generator is used to create test data. You can choose the size of your array in sortmain.c. Each run will get different numbers, but if you comment out the line indicated, you will always get the same numbers, this is uesful while debugging. In arrayutils.c you can change the range of numbers that are generated. Choose a pleasing way to display your array. I don't mind whether you sort ascending or descending, or what method you choose to do it.

Sorting Strings

This might be fun, the main difference is that you rearrange based on strcmp rather than direct comparison. 

Same files as from sort, except

stringutils.c

Note different file name. Utilities to read words from stdin , and print the list

README

Gives some general instructions.

Two versions of this: 1. Array of pointers, 2. Linked List

1. Files in stringsort/ -- the array is of pointers, you rearrange it.
2. Files in listsort/   --   If you are familiar with the data structure of Linked List, the words are in nodes that are linked together with "next" pointers, which you must rearrange. Merging two sorted linked lists, for example, is quite straightforward and requires no additional storage.
   Quicksort, on the other hand, is totally inappropriate.
   
   Reading is from stdin. That means you can either type (lines of) words, or take input from a file, such as the two .txt files provided. The syntax for this is
   ./dosort <quick.txt

Instructions

1. Get the files

cp -r /home/COURSES/CSC116/quests/sort  .
cd sort

2. Fill in the blanks, complete algorithms, Makefile, get it working

The point of this exercise is to learn to combine several files into a project. You may prefer the convenience of MegaBlockBuilder++, but hey, it just constructs a Makefile, and calls on make to do the work! Understand this!

This is your program, you are free to change anything you don't like, or add additional files. You do not have to use my swap, for instance.

I find it very convenient to use Kwrite or Kate, good highlighting, and Kate has a built-in terminal (if you don't see it, go to Settings|Configure|Plugins and check Terminal) Do the cycle of

make
./dosort

During debugging, I recommend adding additional print statements. In particular, you can call printarray whereever you want to see what's happening.

When it's all working, you no longer need the .o files, or any backups, so clean up before you submit, tehn get out of the directory. Type:

make clean
cd ..  #up one directory

3. Submit your directory (not individual files!)

submit cs216 sort	#or#  other directory

So what's this swap.s file all about?