Lab 5 — 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.