c code programming
Introduction to Programming CS1325
Assignment #5 – Pointer Exercises, Sort by Pointers
Introduction
Your fifth assignment will consist of two C programs. The C programs should be submitted as a
standard C source code file.
Please note that your computer program should comply with the commenting and formatting
rules as described in class. For example, there should be a header for the whole program that
gives the author’s name, class name, date, and description. End braces should be commented,
and there are alignment and indenting requirements as discussed. In addition, all non-main
functions should be placed below main. Please ask if you have any questions.
Program 1: Warmup Exercises with Pointers
Sometimes when we’re working with a new subject, like pointers, it helps to do a series of
smaller problems before we tackle a bigger one. That is the purpose of this first program.
For this problem, write a single program that does the following 10 tasks. Please put clear
comments in your code to indicate when the various tasks are being done.
1) Create two int variables x and y and initialize them to 5 and 10 respectively.
2) Create two int pointers, ptr1 and ptr2, and initialize them to point to x and y
respectively.
3) Verify that x and y were initialized properly by printing out their values and their
addresses (i.e., using the address operator on x and y) as follows:
Stage 1: x = XXX, y = XXX; &x = XXX; &y = XXX
(Note that we’ve designed the output so that the values are on the left and the addresses
are on the right. This makes it easier to align the values.)
4) Verify that ptr1 and ptr2 were initialized properly by printing the variables they are
pointing to on the left and their addresses on the right as follows (print out all 4 items
using the pointers only):
Stage 2: *ptr1 = XXX; *prt2 = XXX; ptr1 = XXX, ptr2 = XXX
5) Using ptr1 and ptr2 only, change x to 10 and y to 15.
CS1325 – Introduction to Programming page: 2
6) Verify that x and y were changed as follows: Stage 3: x = XXX, y = XXX; &x = XXX; &y = XXX
7) Write a swapInt() function that changes the values of x and y. Call it on x and y.
(It is important that you use this exact name for this function.)
8) Verify that x and y were changed as follows: Stage 4: x = XXX, y = XXX; &x = XXX; &y = XXX
9) Write a swapIntPtr() function that changes the values of ptr1 and ptr2. Call it
on ptr1 and ptr2.
(Again, it is important to use this exact name for this function. Note that there is no
function overloading in C (therefore, this function must be named differently than the
function referenced above).)
10) Verify that ptr1 and ptr2 were changed properly as follows: Stage 5: *ptr1 = XXX; *prt2 = XXX; ptr1 = XXX, ptr2 = XXX
Output Requirements
These types of experiments are easier to interpret if the output is neat and well organized. Here
is an example of the output from a correct run of this program. Yours should look just like this
(but with different addresses, of course).
Stage 1: x = 5, y = 10; &x = 0032FD10, &y = 0032FD04
Stage 2: *ptr1 = 5, *ptr2 = 10; ptr1 = 0032FD10, ptr2 = 0032FD04
Stage 3: x = 10, y = 15; &x = 0032FD10, &y = 0032FD04
Stage 4: x = 15, y = 10; &x = 0032FD10, &y = 0032FD04
Stage 5: *ptr1 = 10, *ptr2 = 15; ptr1 = 0032FD04, ptr2 = 0032FD10
Of course, the addresses will be different for each run of the program. Nevertheless, the stages
are clearly marked and all of the integers and all of the addresses line up. As a result, we can
now see exactly what is happening. Stage 3 occurs after the values for x and y were changed
using ptr1 and ptr2. Stage 4 occurs after the swapInt() function is called on x and y.
And Stage 5 occurs after the swapIntPtr() function is called on ptr1 and ptr2. As we
can see in the last line (i.e., Stage 5), ptr1 now points to y and ptr2 now points to x.
Please make your output neat and aligned as demonstrated above. All of the integer values are
on the left, all of the addresses are on the right. Each value should be clearly identified and
everything should line up neatly.
CS1325 – Introduction to Programming page: 3
Final Notes
Errors and Warnings
As we grade this assignment, we are going to look in particular for errors or warnings of the
following types:
warning C4047: 'function' : 'int *' differs in levels of indirection from 'int **' or
warning C4024: 'swapIntPtr' : different types for formal and actual parameter 1
These particular warnings were generated in Visual Studio, and so, of course, they may be
slightly different with different compilers. Nevertheless, these types of warnings often occur
when we have a data type mismatch involving pointers. For example, they can occur when we
attempt to send an int into a function that is expecting an “int *”. Note that in this case, the
levels of indirection are different. Most compilers will correctly identify that problem.
When we compile your programs, there should be no warnings or errors of this kind at all. Each
such warning or error would indicate that a pointer is not being used correctly, and will cost
points.
Future Problems
It is very important that these problems be correctly implemented. Note only will it help your
understanding of pointers, but you will also need the swapIntPtr() function in the next
problem.
Program 2: Sorting with Pointers
Sometimes we’re 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 if the data set is large and memory limited (say, perhaps, in
an embedded system), this solution might not be practicable. A more elegant solution is to sort
the array indirectly, i.e., by using pointers. With this technique we wouldn’t 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.
CS1325 – Introduction to Programming page: 4
Here are some diagrams that illustrate the idea:
The book from which these diagrams were taken called the array containing the original data set
the “donations Array,” but that is not relevant to our current problem. What is depicted here is
the original data set contained in the array on the right in each picture, and an array of pointers
pointing at various elements of the original data set on the left in each picture. 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 let’s use the data in the file “Array Input Pointer Sort” found in
the “Homework Input Files” folder on eLearning. Since we don’t have file I/O in C yet, we can
load those data into our programs through an initialization list as follows:
int mainArr [ ] = {
// copy in array contents here
};
Note that we should never copy anything from a non-text file (e.g., Word, PDF, etc.) directly into
our programs. Instead, copy/paste the numbers first into NotePad (or a Notepad equivalent) and
from there copy/paste them into your source code.
Sorting
There are many common sorting algorithms that could be used to sort these data. Most of these
are what’s 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.
CS1325 – Introduction to Programming page: 5
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(n 2 ) algorithm that is
based on two nested loops:
outer loop index “i” runs from n-1 down to 1 (inclusive) o inner loop index “j” runs from 0 to i-1 (inclusive)
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. As written, this algorithm will swap
arrays elements until the data set is sorted. (Note that it is necessary to swap two values in the
last line.) In our implementation, however, we will swap the pointers that point to those array
elements, while leaving the array elements themselves untouched. This should be done with a
swapIntPtr() function as described below.
As given, this algorithm would sort the original array of ints very well. However, as
mentioned, it does so by changing the values in the original array. 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. The name of the function should be swapIntPtr(). (Do not use the name
“swap().” The reason is that there are built in swap functions on various compilers that can
conflict with our functions.)
What should the input parameters for the swapIntPtr() function be?
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.
Note that the display function that displays the data in the original array must be different than
the display function that displays the data through the pointer array. Thus, this operation will
require two different functions. Each will have a different set of input parameters.
CS1325 – Introduction to Programming page: 6
Project Requirements (Overview)
This is a high level outline of what needs to be accomplished in this assignment:
1) Initialize an int array of size 150 and load it with the data from eLearning (“Array Input Pointer Sort”). 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 swapIntPtr() 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.
CS1325 – Introduction to Programming page: 7
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. Don’t
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 function. In this way, you control the number
of errors you have to deal with and vastly decrease the time required to develop your solution.
I suggest implementing your solutions as follows:
1) First initialize your main array (Data Array) with the data from eLearning. This contains 150 pseudo-random integers between 0 and 3000.
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. Don’t 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. Don’t do anything else until this function is written
and debugged.
5) Then write the swapIntPtr() function that swaps two int pointers. Test it by using a small driver program as follows:
CS1325 – Introduction to Programming page: 8
int x=5, y=10;
int * xPtr = &x;
int * yPtr = &y;
printf (“Address of x = %p; Address of y = %p\n”, xPtr, yPtr);
swap (&xPtr, &yPtr);
printf (“Address of x = %p; Address of y = %p\n”, 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 swapIntPtr() 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.
Final Notes
It is important to emphasize again that your code should not contain any errors that indicate that
the pointers are not being used properly. (See the end of Problem 1 in this assignment for an
elaboration of this point.)
Since the second problem is much more difficult than the first, these two problems will be
graded according to a 40/60 grading scale.