See the assignment turn-in page (last modified on 4 March 2002) for instructions on turning in your assignment.
struct answer {
unsigned v1, v2, v3, moves;
}
typedef std::vector<unsigned> ivec;
answer min_3sort(ivec iv1, ivec iv2, ivec iv3);
that accepts three vectors of non-negative integers and determines the minimum
number of moves required to three-sort the vectors. A move occurs
whenever a number is shifted from one vector to a different vector (shifting a
number within the same vector is not a move). The answer returned by
min_3sort() should contain the following values:
v1: the value modulo 3 of any element in iv1.
v2: the value modulo 3 of any element in iv2.
v3: the value modulo 3 of any element in iv3.
move: the number of moves required to three-sort the vectors.
If there is more than one minimal three-sort possible, min_3sort() can
return any of them.
The answer struct, the ivec typedef and the min_3sort prototype
are defined in min-3sort.h in the assignment directory
/export/home/class/cs-509/pa4.
You can test your procedure by compiling it with the file
/export/home/class/cs-509/pa4/os-main.o
where os is either linux, solaris, or stlport-solaris.
Running the resulting executable calls min_3sort() and compares the answer
returned with my answer. If you get no output, then everything's fine;
otherwise you'll get an error message indicating a problem.
The -s command-line option takes an integer argument and uses it as the
seed for the random-number generator. You can run your code repeatedly on the
same set of randomly-generated data by passing in the same value with -s
on each execution. The default is to generate a different set of
randomly-generated data with each execution.
The source file for main() will not be made available because it contains
my answer to the problem.
If you use with stlport-solaris-main.o, make sure you compile and link
everything with STLPort files; otherwise you'll get link errors.
Your implementation of min_3sort() should not exploit any extra properties
of the input data; I'll be generating different input data when I test your
assignments.
To be correct, your solution must be efficient; that is, you solution should
take no more than twice the execution time my solution takes on the same input.
The test executable keeps track of execution times. The -t command-line
option prints the execution time taken by your version of min_3sort().
This page last modified on 25 October 2002.