CS1337 Assignment 02 Introduction 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. 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 practical. 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 in another array that has pointers into the original data array. When this type of sorting is performed on the array that containers the pointers , we still will be able to access the data both in its original order in the original array and using the array of pointers that is in sorted order. Here are some diagrams that illustrate the idea: arrPtr Array Array arrPtr Array Array [0] 11 [0] [0] 11 [0] II [1] 10 [1] [1] array[j+1] Here, n refers to the size of the data set. As written, this algorithm will swap array 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. The sorting should be done according to the values in the data array. The pointer array has pointers that may be change position in the pointer array during sorting. 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 must be swap IntPtr(). What should the 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 space 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 parameters. Project Requirements (Overview) This is a high level outline of what needs to be accomplished in this assignment: 1) Get the data from the file into an array. 2) Assign a pointer array of int pointers to the same index in the data 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, pointer Arr[O] 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 display out the data set 2 different times for each number list. First, print the sorted number list by traversing the pointer array. 5) Repeat step 1 until there is not any more data in the file. Functional Requirements: You will need to write the following functions besides main(): 1. ReadIntoDataArray Read the data from the file into the data array. 2. A SwapIntPtr () function. 3. When called on two pointer arguments, this function should swap the values of the pointer arguments. 4. 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 to the 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. 5. A display function for the Data Array. 6. This function should display the data in the Data Array, up to 10 numbers per line in a 6 space field. 7. 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. 8. Repeat the process until there is not any data left in the field. The submittal must include a arrayData.txt file that demonstrates adequate testing of the program to make sure it runs correctly. Review the rules in the Required Best Practices document posted to the eLearning system. Ensure your program is well documented, well structured, modular and uses meaningful variable names. Use functions, with parameters, as necessary for good structure and readability. Do not use global variables. All functions must exist after the main () functions, so use function prototypes. All functions used must be modular and have arguments and parameters. Do not use any global variables in the design. PseudoCode for main() function: Your main() function could look something like this: create and initialize the data array create and initialize the pointer array read in data from file to the data array call the sorting function to sort the pointer array display ("Now displaying data in sorted order") call the display function that displays the data in sorted order (by traversing the pointer array). call the display function that displays the data in the original order display ("Now displaying data in the original order") pause the screen so that the display can be read repeat the process until end of file For this assignment, develop the prototypes for all the 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. Of course, your program should count the number of elements that have loaded into the array. 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. 6) Then implement the Bubble Sort algorithm using the modified sorting algorithm given above. It should use the swap IntPtr() 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) Pause the screen so that the data set processing can be viewed. Use the following code to pause the screen: #include : cout