Lab 3.4 — Tagsort

The sorting techniques you've learned until now manipulate the array of data — swapping, sliding, and in general, moving the elements around until they are in sorted order. This can be undesirable for two reasons:

• There are times we wish to preserve the original order of the elements, and this is lost as a result of the sort.
• If the elements are large, the data movement resulting from the sort can be time-consuming, and/or require additional space.

Tagsort is a sorting technique that avoids these two problems. The basic idea is to maintain a secondary array (sometimes called an index or tag array) containing some sort of reference to the corresponding elements of the actual data array.

The tags are often implemented as integers corresponding to the subscripts (locations) of the elements in the data array:

Before sorting:
(index)         0   1   2   3   4
              +-------------------+
data array:   | 4 | 7 | 1 | 8 | 5 |
              +-------------------+

              +-------------------+
tag array :   | 0 | 1 | 2 | 3 | 4 |
              +-------------------+

After sorting:
(index)         0   1   2   3   4
              +-------------------+
data array:   | 4 | 7 | 1 | 8 | 5 |
              +-------------------+

              +-------------------+
tag array:    | 2 | 0 | 4 | 1 | 3 |
              +-------------------+

Iterating through the tag array after the sort, following the tags, and printing the values produces:

1 4 5 7 8

however, pointers often take the place of the integers. In the following example, the array begins at location 0100 (and each integer element is 4 bytes in length):

Before sorting:
(index)         0   1   2   3   4
              +-------------------+
data array:   | 4 | 7 | 1 | 8 | 5 |
              +-------------------+

              +-------------------+
tag array:    |100|104|108|10A|200|
              +-------------------+

After sorting:
(index)         0   1   2   3   4
              +-------------------+
data array:   | 4 | 7 | 1 | 8 | 5 |
              +-------------------+

              +-------------------+
tag array:    |108|100|200|104|10A|
              +-------------------+

and again, iterating through the pointers, and printing out the values at the other end of each pointer, results in:

1 4 5 7 8

Notes

• Iterating through the tag array produces a sorted enumeration of the data, while iterating through the data array produces the original sequence. Furthermore, no data has been moved during the sort — only the relatively small tags.
• (Note that in Java, where all access to data (except primitives) is via a reference, and thus when sorting an array, one is merely sorting the references, which are, in essence, acting as tags, and thus all sorts (except for those of primitives) are essentially tagssorts , in the sense of the references being moved around, and not the data. Like all access to object through references, this is completely transparent to your code). OTOH,if one wished to preserve the original order, one could make a copy of the original array, and sort that).
• In C/C++, we can use integers for the tag array (as shown above), or alternatively pointers to the elements. For the sake of practice with pointers, this exercise chooses the latter.

The Details

• Write a (C-style, i.e., non-class) module tagsort.h/.cpp with a single function named sort in the .h file. sort accepts an array of integer pointers, and a integer representing the number of elements in the array, and performs a tagsort on the data pointed at by the elements of the (tag) array parameter.
• You should also write a test driver in the form of a main method in its own file (tagsort_app.cpp) that declares two arrays … one of integers and the other of pointers to integer (i.e., int[] and int *[]. Populate the first array with integers read from the file numbers.text, and initialize the second so that each element points to the corresponding element of the integer array (i.e., element 0 of the pointer/tag array points at element 0 of the integer array, element 1 to element 1, etc. — the situation should thus look like the 'Before sorting' diagram above).
  • It's good, additional pointer practice to write this driver; however, I've supplied one for you (you can see it via the link at the bottom of the page. You may, however, want to try writing it yourself first before looking at mine.

Implementation Notes

• This is a 'C-like' module, i.e., no class is being written, only a non-member (C-like) function.
• Find a 'favorite' sort in your notes and/or code, code it in C++, and make sure it runs OK (i.e., feed it an array and make sure it sorts it correctly). Only then should you add the level of indirection through the tag pointer. That way, the only thing you should have to concentrate on are the pointer operations you are introducing.
  • If you are feeling shaky about this, I would recommend simply using bubble sort, or one of the other quadratic sorts.
• You may want to introduce additional functions within tagsort.cpp — for example a swap function.

Submitting to Codelab

• The tagsort_app.cpp supplied to you is the test driver used by CodeLab
• You don't have to worry about the output format — that's done completely by the test driver
• If you are using any auxiliary functions (e.g., swap, please make sure they are in the correct order, or use function headers.

Lab 3.5 — C++ Rational (Approval)

Overview

Like it says... the Rational class in C++. As before, I will be supplying a test program (rational_test.cpp) as well as an exception class (rational_exception.h). In addition, I am providing a partial rational.h to illustrate the proper parameter passing conventions used. You might want to not look at these files initially, and see if you can transliterate them yourself from the Java version I supplied, using the parameter transmission rules we discussed.

The basic specs are the same — the Notes section that follows contains language-specific differences. Any suggestions I provide are exactly that — suggestions. As long as you conform to the specs, and the CodeLab interface (see below), your are free to implement this in any manner you see fit.

The only additional function you need to write is a void print(ostream &os) const; member function that prints out the Rational. This replaces the toString of your Java implementation, and should have the same semantics.

Program Organization

While, normally, you would be free to organize your files as you see fit, I am providing a program organization you should follow — first, it's basically the organization you would use anyway (though you might have incorporated the gcd function into your Rational class -- I'm providing it here for you); second, the CodeLab implementation follows this organization and will complain if you deviate.

• rational_test.cpp
• rational.h
  • There are two versions: one with sample headers, and the other .skeleton suffix) with just the << operator
• rational.cpp
• rational_exception.h
• gcd.h
  • I placed my gcd function here. Since it's an .h file and potentially included by many sources in a program using it, I declared it inline to prevent 'multiple definitions' link errors.

You will be submitting rational.h and rational.cpp as two separate exercises in CodeLab. As I will be supplying the other, the function signatures in the .h and .cpp files must match (which is the purpose of this — to force you to use the correct signatures). All the function definitions (bodies) should go into the .cpp, i.e., none should be coded inline in the class declaration in the .h.

Notes

• Here is an example of this class with only one operation. There's non normalization, and little exception handling, but you can get most of that from your Java class.
• Much of this can be accomplished as a transliteration from Java to C++, the main differences are sketched out below
• function signatures — this is both one of the most significant of the changes as well as on of the main topics targeted by this exercise. Here is a link to the presentation of C++ Parameter Transmission.
  • In a nutshell:
    • parameters types:
      • if the argument is to be modified, use call-by reference (&); this is true of both fundamental as well as class types
      • if the type is a class, use const-class-by-reference (const … &)
      • if the type is a fundamental, use call-by-value
    • return type:
      • if the type is a fundamental, use return by-value
      • if the type is a class, and the value returned is a local variable (or an expression), use return-by-value
      • otherwise, if the type is a class, return by-reference
• You should collapse the three application-oriented (my term) constructors into one using defaults arguments
  • By application-oriented, I mean constructors that initialize the object using values meaningful to the semantics of the class. For example, using a pair of integers to initialize a Rational, or a name, address, and id to initialize a student. Such constructors deal with values coming from the application (numerators, name, etc).
  • This is in contrast to a copy constructor which uses another object of the same class. The semantics of copy constructors is essentially the same for all classes — copy (in a semantically appropriate manner) the fields of the source object to the corresponding fields of the destination. There is little if any logic related to the application.
  • There is, I believe, a conventional term for what I'm calling application-oriented constructors, but I can't seem to find it online
• As before, you can leverage the functionality of the arithmetic operator and their corresponding inPlace functions (in either direction).
• Don't forget, this is a pointer, so to get to fields of the object, you need -> and to refer to the object you need *this
• To make your lives simpler, I am providing a << operator for Rational. This function relies on your print function described in the overview.
  • this allows you to write cout << where r is of type Rational
    • We will llearn how to write this when we cover operator overloading
    • in the meantime, examine the code and see if you can make any sense of it
  • I am placing it in the file rational.h.skeleton that you can access (like all the other files provided) in the link at the bottom of this page.
  • the contents is a skeleton of the Rational class declaration, with the operator below and declared inline
  • Refer to Advice 2.1
• Do not put a using namespace std; in your .h file (we will discuss the reason for this when we get to separate compilation in Part II). The consequence of this is that anything from the Standard Library (e.g. ostream, cout, etc) must be fully qualified; i.e., must be prefixed with std::.

Submitting to Codelab

As in some of the previous Labs, this lab is broken up in CodeLab into multiple 'subexercises':

• 4.1.1 - Submit your rational.h
• 4.1.2 - Submit your rational.cpp

I had originally planned on allowing you to code the function signatures in any manner (as long as the resulting implementation 'worked'), but given that the correct signatures are more than simply 'good suggestions', I think we should enforce them from the very beginning.

A Word About the Compiler Feedback in CodeLab

In all likelihood, you will make a mistake on at least one function signature (by mistake I mean not matching my corresponding signature in the corresponding h / .cpp file; it may also be the case that I made a mistake in the signature). In the event of such (interface) errors, the compiler will complain about the two functions signatures not matching. In order for you to figure out your error, you should know which signature is your and which is mine, and where the compiler will be doing the complaining. In 4.1.1, the compiler will encounter the .h file first (because the #include is encountered at the top of the .cpp file), and thus the error will be manifested when it reaches my signature in the .cpp which won't match. Conversely, in 4.1.2 — where I am providing the .h file, the error will again appear in the .cpp signature, which is yours this time.