Introduction to Programming CS1325 Assignment #6 Numbers and Pointers

Program 6:

Sorting with Pointers

Sometimes were given an array of data that we need to be able to view in sorted order while leaving the original order unchanged. In such cases we could sort the data set, but then we would lose the information contained in the original order. We need a better solution. One solution might be to create a duplicate of the data set, perhaps make a copy of one array into another, and then to sort the second array. This would allow us to view the data both in the original order and in the sorted order. This might be fine in many cases, but redundancy is frequently problematic. A more elegant solution is to sort the array indirectly, i.e., by using pointers. With this technique we wouldnt change the positions of the actual data items in the array; we would only change the values of the pointers that point into the array. Nevertheless, when this type of sorting is performed, we still will be able to access the data both in its original order, by using the original array, but also in sorted order, by using the array of pointers. We first initialize the array of pointers so that each element in the pointer array points to the element in the data array that has the same index value (left hand picture). We then sort the pointers according to the values they point to, leaving the original data set untouched (right hand picture). After this step is completed, we can access the data set in its original order by using the original array, or we can access the data set in sorted order through the pointer array.

Input For our input into this problem lets use the array that was used in Homework #4, A04cs1325statsData.txt. We can load it into our programs through an initialization list in the same way we loaded it in Homework #4. Sorting There are many common sorting algorithms that could be used to sort these data. Most of these are whats known as comparison based sorting algorithms, since they make decisions by comparing each array element against others. Most often, comparison based sorting algorithms work by interchanging, or swapping, elements within the array. One common and simple comparison based sorting algorithm is called Bubble Sort. It works by making multiple passes through the data set and on each pass comparing two adjacent array elements and swapping them if the right hand element is less than the left hand element. In this way, the largest element remaining is bubbled to the top of the array on each pass. After all the passes are completed, the array is in sorted order. Here is the pseudo-code for one version of the Bubble Sort. This is an O(n2) algorithm that is based on two nested loops: ?

outer loop index i runs from n-1 down to 1 o inner loop index j runs from 0 to i-1 ? compare array[j] and array[j+1] ? swap if array[j] > array[j+1]

Here, n refers to the size of the data set, 150 in our case. Note that it is necessary to swap two values in the last line. This should be done with a swap() function as described below. As given, this algorithm would sort the original array of ints very well. However, in this assignment, we need to be able to sort the pointer array instead of the original int array. Although the sorting should be done according to the values the pointer array is pointing to, the only values actually changed are pointers. Therefore, this algorithm will have to be modified to work on the pointer array. Swap Function We will need a swap function that can swap the values of two argument pointers. In this case, our original data set consists of all ints. Therefore, the swap function needs to be able to swap pointers to ints.

Displaying Data We will display the data both in sorted form and in unsorted form. The data should be displayed 10 numbers per line, each number in a 6 byte field. Functions should be used to display the data. Project Requirements (Overview) This is a high level outline of what needs to be accomplished in this assignment: 1)

Initialize an int array and load it with the data from eLearning (A04cs1325statsData.txt). For purposes of discussion, call this array the Data Array.

2)

Create an array of int pointers of the same size. For purposes of discussion, call this array the Pointer Array. Initialize it to point to the Data Array in such a way that, after being initialized, each element of the Pointer Array should point to the element in Data Array that has the same index. (This is illustrated in the first picture above.)

3)

Sort the Pointer Array by using a modified version of the Bubble Sort algorithm provided. After sorting, pointerArr[0] should point to the smallest element in Data Array, pointerArr[1] should point to the second smallest element, and so forth.

4)

Your program should print out the data set three different times. First, print out the data set in its original order (by traversing the Data Array). Second, print it in sorted order (by traversing the Pointer Array). And finally, print the Data Array one more time to demonstrate the original order.

Functional Requirements: You will need to write the following functions besides main(): 1)

A swap() function. When called on two pointer arguments, this function should swap the values of the pointer arguments.

2)

A sorting function. This function should implement the Bubble Sort (or some other common sorting algorithm) on the Pointer Array. Note that we are not sorting the Data Array in this problem, only the Pointer Array. Therefore, the pseudocode for the Bubble Sort given above will have to be modified to work on pointers. Furthermore, the sorting will be done according to the values the pointers are pointing to. Referring back to Bubble Sort, if we are comparing the values pointed to in one adjacent pointer element to another, and the value pointed to is smaller in the right hand element

than the left, then we swap the pointers, not the values in the Data Array. 3)

A display function for the Data Array. This function should display the data in the Data Array, 10 numbers per line in a 6 byte field.

4)

A display function for the Pointer Array. This function should display the data pointed to in the Pointer Array, 10 numbers per line in a 6 byte field. Note that this function does not display addresses. It should display the integers found in the data set, but in sorted order.

PseudoCode for main() function: Your main() function could look something like this: create and initialize the data array create and initialize the pointer array call the sorting function to sort the pointer array display prompt (Now displaying data in the original order) call the display function that displays the data in the original order display prompt (Now displaying data in sorted order) call the display function that displays the data in sorted order. display prompt (Now displaying data in the original order) call the display function that displays the data in the original order For this assignment, you can develop your own prototypes for these functions. Suggestions for implementation Until you get used to them, pointers can be very confusing to work with. Therefore, it is very important, in this project especially, to implement your final solution one piece at a time. Dont try to write the whole thing at once. It is much better to work on one function at a time and thoroughly debug it before moving on to the next one. I suggest implementing your solutions as follows: 1)

First initialize your main array (Data Array) with the data from eLearning.

2)

Then implement the function that prints out the data in the Data Array. Set it up to print 10 numbers per line, each number in a 6 byte field. Use it to test that the Data Array was initialized properly. Dont do anything else until this function is written and debugged.

3)

Then set up the Pointer Array and initialize it as described above.

4)

Then implement the display function that prints out the data from the Pointer Array. Use it to test the initialization of the pointer array. At this point, the data should display in the same order as in the original array. Dont do anything else until this function is written and debugged.

5)

Then write the swap() function that swaps two int pointers. Test it by using a small driver program as follows: int x=5, y=10; int * xPtr = &x; int * yPtr = &y; printf (Address of x = %p; Address of y = %p , xPtr, yPtr); swap (&xPtr, &yPtr); printf (Address of x = %p; Address of y = %p , xPtr, yPtr);

If your code is working well, the addresses should be swapped. 6)

Then implement the Bubble Sort algorithm using the modified sorting algorithm given above. It should use the swap() function described above to do its swapping. As you work, use the display function for the pointer array that you have already written in step 4 -- to check your work.

7)

Once everything is working, set up the main() function to perform the tasks of the assignment.

**USE ANY ARRAY FOR TESTING**