CIS 150 Programming Project: Pointers, arrays, sorting

• Follow instructions (program requirements)
• Use pointer notation instead of standard array notation
• Create function prototypes
• Create and use functions
• Implement pseudocode algorithms in C++
• Pass arrays to functions

1. You must use prototypes for all of the functions other than main. This means that you have to add three function prototypes to the supplied code.
2. You may not have any global variables.
3. You must use pointers for all of the code that you write. You are not allowed to use [ ] to access elements of the array or specify an array in a parameter list. If you use [ ] for those purposes, then that code will score a 0. Note: The [ ] notation should only be used in two locations in your program, where the memory for the array is allocated, and where that memory block is set free.
4. When swapping elements of the array, you must use the swap function that is supplied. That is why it has been supplied.

The following is your pseudocode for the three functions you must implement.

sort: // Name: sort // Purpose: // The purpose of this function is to provide a convenient way for other // code to call the real sorting function. This function only requires a // pointer to the array and the length of the array. The real sorting // function sorts sections of an array and must therefore get a pointer // to the array, a position where sorting should start, and a position // where sorting should end. // Input: // A pointer to a series of integer values (an array) to be sorted // The number of integer values in the series (the length of the array) // Output: // Nothing is returned // Side effect: // The series of integers (array) pointed to should be sorted upon return call a sort that will sort this series from position 0 to the position: length of series - 1 return sort: // Name: sort // Purpose: // This function sorts a continuous series of values within a possibly // larger series of values. The starting and ending positions for the // sorting within the array must be specified. // Input: // A pointer to a series of integer values (an array) to be sorted // An index to the position in the series where sorting starts // An index to the position in the series where sorting stops // Note: The index should be 0-based // Note: To sort the whole series, use 0 and length of series - 1 // Output: // Nothing is returned // Side effect: // The section of the series of integers (array) specified by the // start and end positions should be sorted upon return // Assumptions in pseudocode: // nums: is the pointer to the series of integers // left: is the index where sorting should start // right: is the index where sorting should stop let minNdx and maxNdx be the index in the array where sorting will start if left is less than right for i = left + 1 to right if the array element at index i is less than the array element at index minNdx let minNdx = i if the array element at index i is greater than the array element at index maxNdx let maxNdx = i if minNdx is not equal to left swap the array elements at positions left and minNdx if maxNdx is not equal to right if maxNdx is equal to left let maxNdx = minNdx swap the array elements at positions right and maxNdx call sort with the same array, but with left increased by one and right decreased by one return sumArray: // Name: sumArray // Purpose: // The purpose of this function is to add up all the elements of an // array and return the sum. // Input: // A pointer to a series of integer values (an array) to be summed // The number of integer values in the series (the length of the array) // Output: // The sum of the elements of the array (an integer). // Side effect: // No side effects. The array is left unchanged. initialize the sum iterate through the array adding each element's value to the sum return the sum

The following code is also available at: SortStart.cpp

#include <cstdlib> #include <iostream> #include <iomanip> using namespace std; bool isSorted(int* ar, int len); void initArray(int* ar, int len); void displayArray(int* ar, int len); void swap(int* ar, int pos1, int pos2); int main(int argc, char** argv) { srand(time(NULL)); // initialize random number generator const int NUM_TESTS = 1703; // number of tests to run on sort int errorCount = 0; // keeps track of how many tests fail int arraySize = 0; // keeps track of length of array int* nums = NULL; // pointer to array int sum = 0; // used to make sure array has not been corrupted // Run the code for the number of tests specified for (int test = 1; test <= NUM_TESTS; test++) { // Display the test number every 100 tests and at end if (test % 100 == 0 || test == NUM_TESTS) { cout << "\rTest number " << test; cout.flush(); } // Create an array of random size from 1 - 1000 arraySize = rand() % 1000 + 1; nums = new int[arraySize]; if (nums == NULL) { cout << "Error allocating space for array\n"; exit(EXIT_FAILURE); } // Fill array with random numbers initArray(nums, arraySize); // Get sum for array to check if it is same after sorting sum = sumArray(nums, arraySize); // Sort array sort(nums, arraySize); // Make sure array is sorted and sum is consistent if (sum != sumArray(nums, arraySize)) { cout << "Error: Array corrupted.\n"; errorCount++; } else if (!isSorted(nums, arraySize)) { cout << "Error: Array not sorted\n"; errorCount++; } // Free memory used by array delete[] nums; } cout << "\nNumber of tests: " << NUM_TESTS << '\n'; cout << "Number of errors: " << errorCount << '\n'; return 0; } /* Name: isSorted Input: ar: a pointer to an array of integers len: the length of the array Output: true if the array is sorted, otherwise false */ bool isSorted(int* ar, int len) { bool sorted = true; for (int i=0; i<len-1; i++) { if (*(ar+i) > *(ar+i+1)) { sorted = false; break; } } return sorted; } /* Name: initArray Input: ar: a pointer to an array of integers len: the length of the array Output: None Side effect: The input array is sorted in ascending order. */ void initArray(int* ar, int len) { for (int i=0; i<len; i++) { *(ar+i) = rand() % 1000 + 1; } } /* Name: displayArray Input: ar: a pointer to an array of integers len: the length of the array Output: None Side effect: The input array is displayed on the screen in ten columns of width five. A newline is displayed after every tenth item and after the last item. */ void displayArray(int* ar, int len) { for (int i=0; i<len; i++) { cout << setw(5) << *(ar+i); if (i == len-1 || i % 10 == 9) cout << '\n'; } } /* Name: swap Input: ar: a pointer to an array of integers pos1: an index of one item in the array to be swapped pos2: an index of another item in the array to be swapped Output: None Side effect: The two items in the input array are swapped. */ void swap(int* ar, int pos1, int pos2) { // Only swap if the two items are not the same item if (pos1 != pos2) { int temp = *(ar+pos1); *(ar+pos1) = *(ar+pos2); *(ar+pos2) = temp; } }

Test number 1703 Number of tests: 1703 Number of errors: 0

• 3 points: for proper documentation comments and for correctly following coding conventions (indentation, naming rules, NO tabs, etc.)
• 3 points: for having the three function prototypes correct
• 4 points: for having the sort function that takes two arguments implemented properly
• 13 points: for having the sort function that takes three arguments implemented properly
• 5 points: for having the sumArray function working properly
• 2 points: for using the swap function properly instead of writing your own swap code