For your second programming assignment,
you are to implement a sorting algorithm only using a stack and
two queues, and a set of allowed operations.
Your program will check both real and decimal numbers as well as strings.
Your executable must be named sqsort.
The executable reads in a series of only string, decimal, or real numbers, either from
a file or from stdin,
and will produce, on stdout, the list of numbers as they are processed
Here is an example invocation:
$ echo 2 4 5 3 1 > items
$ sqsort -d items
$ is the system prompt.
The file to be processed (items in the example)
is a free-format text file. That is, the potential values
within are separated by arbitrary amounts of whitespace (i.e. spaces, tabs, and
newlines) and every line
ends with a newline. If a file name is not given, input is to be
read from the keyboard:
$ sqsort -s
"goodbye" "c is the best"
["goodbye","c is the best","hello","please compile","0"]
["goodbye","please compile","hello","c is the best","0"]
["please compile","hello","goodbye","c is the best","0"]
Input is ended by entering a ^D character.
The executable must handle the following options:
| option || example || action
| give author's name and exit
sqsort -d FILENAME
| print the steps of each pass of the algorithm
| || || found in
| print the steps of each pass of the algorithm
| || || read in from stdin
Here are some example invocations using options:
$ sqsort -v
Jeffrey A. Robinson
$ sqsort -r
2.6 1.5 3.8 1.9
Reading the input
You must use the Art and Science of Programming - C Edition
scanner for this task:
The scanner can read in integers, reals, or double-quoted strings
from a file or from stdin.
Note that a token is not a string.
Using scanf, fscanf, gets, or other equivalent functions is
forbidden and will be considered a test failure.
You should write three input functions for reading in files of the three
types of values. You should then use a function pointer to point to the
appropriate input function when processing the command line options.
The only error checking you must perform is detecting
the valid use of flags.
$ sqsort -q
unknown flag 'q', valid flags are -d, -r, -s, and -v
After printing the error message, you should exit the program.
Other than this one exception,
your program will only be tested with valid input.
You must follow the C programming style guide for this project:
Your implementation should have two queues, input and output,
and a stack.
During the execution of your program you move items from input and
them on output in some, possibly different, order.
During this process where you move elements from the input queue
to the output queue,
you can perform three operations:
If more than one operation is possible,
transferring a value from the stack takes
precedence over the other operation(s).
Note that these descriptions assume a comparator that implements
A comparator that implements
“greater than” would use the opposite comparisons.
Move an item from input directly to output.
Do this if the item just dequeued from the input is less than
the item now on the front of the input queue.
Move an item from the stack to output.
Do this if the
sequence of the last item of the output,
the top item on the stack, and the
the item ready to come off
the input does not violate the sort ordering.
Move an item from input to the stack.
Do this if the item just dequeued from the input is greater
than the item now on the front of the input queue.
If there are elements on the stack after the input queue is exhausted,
these elements are moved to the output queue.
Once all elements have been placed on output,
swap the input and output queues (this must happen in constant time).
If the elements are sorted you are done, otherwise you do another pass.
The first line you present reflects the original input
and the final line should reflect the sorted values.
Each intermediate line should contain the result of a pass.
You must use the stack and queue classes from Assignment 0,
keeping the same public interface.
You must use the displayQueue function you implemented from assignment 0
to output each line. An output has a minimum of two lines.
For this assignment,
you will use a comparator function to compare items
and a display function to display them.
In order to remove extraneous code you are required to use function pointers for the comparator and print.
To make things easier you can use the following type definitions.
typedef int (*Comparator)(void*,void*)
typedef void (*Printer)(FILE*,void*)
these can be used in your program as such:
case 'd': // decimal
comp = intComparator;
print = displayInteger;
where intComparator and displayInteger have been previously defined.
You must also define the functions
realComparator and stringComparator with similar semantics
appropriate for the types they are comparing.
Your string comparator function
must be based on the strcmp function.
All your comparator functions should be placed in a module named
comparator.c. The function signatures of these functions and the
above typedefs should be placed in comparator.h.
It is important that only the comparator functions are placed in
You must implement your sorting algorithm in C99. You
must provide a makefile which responds properly to the commands:
make command compiles your program, which should compile
cleanly with no warnings or errors
at the highest level of error checking (the
-Wall and -Wextra options).
make test command should test your program and
make clean command should remove object files and
the executable. Here are examples (your files may differ
in number and name):
$ make clean
rm -f scanner.o integer.o real.o string.o queue.o sll.o stack.o dll.o comparator.o sqsort.o sqsort
gcc -Wall -std=c99 -c -g scanner.c
gcc -Wall -std=c99 -c -g integer.c
gcc -Wall -std=c99 -c -g real.c
gcc -Wall -std=c99 -c -g string.c
gcc -Wall -std=c99 -c -g queue.c
gcc -Wall -std=c99 -c -g sll.c
gcc -Wall -std=c99 -c -g stack.c
gcc -Wall -std=c99 -c -g dll.c
gcc -Wall -std=c99 -c -g comparator.c
gcc -Wall -std=c99 -c -g sqsort.c
gcc -Wall -std=c99 scanner.o integer.o real.o string.o queue.o dll.o stack.o dll.o comparator.o sqsort.o -o sqsort
make: `sqsort' is up to date.
$ make test
sqsort -d mytestfile
[1, 2, 3, 4, 5, 6]
[6, 5, 4, 3, 2, 1]
The compilation command
must name the executable sqsort (not sqsort.exe for you
You may develop on any system you wish but
your program will be compiled and tested on a Linux system.
Only the most foolish
students would not thoroughly test their implementations on
a Linux system before submission.
Note: depending on where you develop your code,
uninitialized variables may have a
tendency to start with a value of zero. Thus, a program with uninitialized
variables may work on
your system but fail when I run it.
The correctness and efficiency of your makefile will be tested.
You must have the correct dependencies and your makefile should not
perform any unnecessary compilations.
All code you hand in must be
attributed to its authors. Comment sparingly but well. Do explain the
purpose of your program. Do not explain obvious code. If code is not
obvious, consider rewriting the code rather than explaining what is
going on through comments.
Grading will proceed in the same fashion as the previous assignment.
To submit assignments, you need to install the submit system.
You will hand in (electronically) your code for the
preliminary assessment and for final testing with the
submit cs201 lusth assign1
Make sure you are in the same directory as your makefile when
The submit program will bundle up all the files in your current
directory and ship them to me, so run a
make clean command
It is very important that only the source code and any testing
be in your directory.
.o files may cause you to fail some of the makefile
You should clean up your subdirectories as well, since
all the files in your subdirectories will also be shipped to me.
You may submit as many times as you want before the deadline; new
submissions replace old submissions. Old submissions are stored and
can be used for backup.