This assignment involves implementing a pseudocode sorting algorithm in C++ and implementing several functions that use pointers. You are given the main function, which will create the array, call one of your functions to do the sort, and then display the results. You are not allowed to use the [] (array subscript) notation in your code. All array access must be done using pointers. Having your code properly sort the array is not sufficient. Your code must implement the sort routine given in the pseudocode for this assignment. In other words, you can't copy a sort routine from somewhere else.
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