Programming in C

Problem 1

Ordering Arrays Using Pointers

In this program you will write a function that orders an array of items. While our immediate example will be a deck of cards, we will write the function so that it can order an array of arbitrary items by passing a not only the array, but also the size of the array and a pointer to an
appropriate comparator function.

To be truly generic, our array must be able to contain data elements beyond primitive data types (int, double, etc.). We want to be able to sort, for example, an array of strings. More generally, we will want to be able to sort an array of structures (which we will study shortly).

To accomplish this, our array will ALWAYS be an array of void pointers where each pointer contains the address of one of the elements in the array, whether that item is a single character or a multimegabyte data record. The pointers will be of type void because our sort function has no way of knowing what type of data the pointer points to.

Our comparator function will take two pointers to two items to be compared. If the first item should be placed before the second item, the function should return a negative integer. If the first item should be placed after the second item, the function should return a positive integer. If the two items are equivalent (in terms of ordering) the function should return zero.

You may use any sorting algorithm you like (except bogosort), including the most basic, brute force version of bubble sort - the sorting algorithm is not the focus here.

To test your sorting algorithm, generate a data set containing ten random integers in the range -100 to +100 (such that -100 and +100 are NOT possible values). Remember, your array will be an array of pointers where each pointer points to one of the integers in the data set. There are two ways to accomplish this. The first is to dynamically allocate memory for each integer separately (in a loop) and store the pointer in the array.

This is the most general purpose approach. The second is to create an array of integers and then loop through this array assigning a pointer to each element to the corresponding pointer in the array of pointers that will be passed to the sort function. For this problem, allocated each integer individually (you will use the other method in the next problem). Don't forget to free up any memory you have allocated before your program terminates.

Write two comparator functions, one that sorts ascending and the other that sorts descending. Note that once you have one of these, there is nothing to prevent you from having the other call the first one and modify the return value appropriately.

Have your program print the data out three ways - first is the original data, second is the data in ascending order, and second is the data in descending order. Each of these three printouts should be on a single line in columns that are four wide and with each value having an explicitly positive/negative sign and being exactly two digits long (so add a leading zero if needed).

The following is what a run might look like:
O: -58 +60 +66 -66 -34 -96 +36 +06 -02 +87 +34 -13 +98 +12 -88
A: -96 -88 -66 -58 -34 -13 -02 +06 +12 +34 +36 +60 +66 +87 +98
D: +98 +87 +66 +60 +36 +34 +12 +06 -02 -13 -34 -58 -66 -88 -96

Problem 2

Write a program that uses the sort function from the prior problem to sort a string of characters, in ascending order according to their ASCII values. For this task use the string "Mary had a little lamb -- and with a bit of berry jam, dinner's set to go."

The ideal goal here is to sort this string in place (i.e., modify the contents of the string so that when it is printed out the characters appear in sorted order). However, the sort function sorts the pointers so that they point to the data elements in the right order. So instead what you can do is first perform the sort on an array of pointers as before.

To accomplish this, you want to use the second method to create your array of pointers; namely have each pointer point to the next character in the string. Be sure to NOT include the NUL terminator - first, this is not part of the string (it's a representation artifact), and second, it needs to stay at the end of the sorted string.

Once the array of pointers is sorted, create a temporary character array of the correct size (i.e., dynamically allocated it to be the same length as the original string) and copy the characters into this array in order. Then copy the elements of this array back to the original string.

Since you are modifying the string, you do NOT want to use a string literal as your data set. You need an actual character array that contains the string. The simplest way to do this is to initialize such an array. Do NOT simply assign a pointer to a string literal!

To indicate the extents of the string, surround the printed string with square brackets.

Your output should look something like:
O:[Mary had a little lamb -- and with a bit of berry jam, dinner's set to go.]
A:[ ',--.Maaaaaaabbbdddeeeefghhiiiijlllmmnnnooorrrrssttttttwyy]