2D Array Pointers

Overview

The overall goal of this assignment is to implement a C++ application that makes use of pointers to access data contained in arrays. Throughout this assignment you will refresh your knowledge of control structures, functions, one and two dimensional arrays, and pointer arithmetic. As a bonus, you will be implementing the insertion sort algorithm to sort the data in the given array.

The functional goal is to sort the 2D array given to you. You will use insertion sort to perform sorting column or row wise. see image.

In the end, your goal is to sort the array and use pointers to traverse through the given data. The learning objectives of this session include:

• to learn how to sort data in arrays using the insertion sort algorithm.
• to learn how to traverse through array data structures using pointer notation.
• to reinforce your knowledge of one- and two-dimensional arrays.
• to reinforce your knowledge of control structures and functions.

To achieve the learning objectives, students are expected to complete the following:

• attend lecture
• attend lab
• review video lectures

Functional Requirements

The following requirements are an overview of what is expected of you in this assignment. More details on how to implement the solution can be found in the Technical Requirements section.

• Each given data set will have five rows and five columns. The given data set will be a 2D array of type char
• Pointers should be used to retrieve data from the arrays.
• You must be able to sort rows and columns of the given data set using insertion sort.
• Insertion sort can be applied row-wise or column-wise.
• Insertion sort is a simple sorting algorithm with time complexity O(n^2). It is efficient with small data sets and as such it is a good match for our assignment. It also sorts in-place which means it only requires O(1) of additional memory space.

The following snippet is pseudocode for the insertion sort algorithm:

for i <- to length(A)-1
j <- i
while j > 0 and A[j-1] > A[j].
swap A[j] and A[j-1]
j = j <- 1
end while
end for

Which behaves as presented below:

1 2 3 5 6 7 8

1. Download the starter file set. It will contain the following files:

• catch.hpp
• functions.h
• main.cpp

2. The provided main.cpp file is the test file. You are free to test your own program using your own main.cpp file but bear in mind that you will be tested against the provided one.

3. The provided functions.h file contains all of the function prototypes of the functions that are going to be tested. You are free to add any others as you wish. Your main task is to write the C++ implementation code for each of these functions.

4. Use your favorite IDE or editor to modify your files. At first, the program won't compile because the functions' implementation are missing.

5. In functions.h , write an empty implementation for each of the functions specified.

6. The program will now compile. If you try running the program it will tell you that it has failed all the tests. Your goal is to make the program pass all the tests by completing the implementation of the methods given to you. You can implement helper functions if needed. See the following section for more information.

Technical Requirements

This section will serve as a guideline of what is necessary for the program to pass all the tests. We perform unit testing using the Catch framework. Catch is a header-only framework which means you just need to drop the header file containing the framework into your project. This is the reason behind the catch.hpp file.

You can also see that some code is provided in the main.cpp file. This code tests the functions in your functions.h file. If your code passes all the tests it is ready for submission and will, most likely (cheating is heavily penalized), receive full credit.

The only thing that you need to do is to modify the functions.h files to get the provided functions working. Don't change the function signature as the testing program relies on this to grade your submission.

Let's start explaining what each of the functions must do.

• char getCharacter(char array[][arraySize], int row, int column): This function takes as an argument a 2D array. The size of the array is fixed by arraysize. It also takes a row and a column that allows you to tap into that specific location in the provided array. You must use pointers to get the character.

const unsigned int rows = 4;
const unsigned int columns = 4;
char first[rows] [columns] = {
{'z', 'c', 'a', 'f'},
{'a', 'q', 'w', 'e'},
{'y', 'a', 'b', 'z'},
{'n', 'e', 'i', 'o'}
};
// Looks at position (0,0) for 'z'
getcharacter (first, 0, 0);

• The code snippet performs the following: see image.
• char* getCharacterAddress(char array() [arraySize], int row, int column): This function takes as an argument a 2D array. The size of the array is fixed by arraySize. It also takes a row and a column that allows you to tap into that specific location in the provided array. You must return a character pointer that points to the address of the character. You MUST use pointer notation.

const unsigned int rows = 4; const unsigned int columns = 4;
char first[rows][columns] = {
{'z', 'c', 'a', 'f'},
{'a', 'q', 'w', 'e'},
{'y', 'a', 'b', 'z'},
{'n', 'e', 'i', 'o'}
}

// Looks at the address of the character in position (0,1).
// address should be something like ox7fff5fbfe281 char* address = getcharacterAddress(first, 0, 1);

// Note: to display the address value, you would need to cast
// the address variable to void*, e.g., see below.
cout << static_cast void*>(address);

• The code snippet performs the following: see image.
• void getRow(char array()(array Size], int row, char* resultArray): This function takes as an argument a 2D array. The size of the array is fixed by arraySize. It also takes a row parameter that allows you to tap into that specific row in the provided array. One of the nice things about pointers is that they allow functions to alter variables outside of their scope. To do this, you pass a pointer and so you allow that function to read and write to the data. This function takes a third argument, char* resultArray , so you can modify resultArray from the function itself. Use resultArray to hold the values in the extracted row. You MUST use pointer notation.

const unsigned int rows = 4;
const unsigned int columns = 4;

char first[rows][columns] = {
{'z', 'c', 'a', 'f'},
{'a', 'q', 'w', 'e'},
{'y', 'a', 'b', 'z'},
{'n', 'e', 'i', 'o'}
};

const unsigned int size = 5;
const unsigned int rowNumber = 3;
char row[size];

getRow(first, rowNumber, row);

• The code snippet performs the following: see image.
• void getColumn(char array()(arraySize], int column, char* resultArray): This function takes as an argument a 2D array. The size of the array is fixed by arraySize. It also takes a column parameter that allows you to tap into that specific column in the provided array. This function takes a third argument, char* resultArray , so you can modify resultArray from the function itself. Use resultarray to hold the values in the extracted column. You MUST use pointer notation.

const unsigned int rows = 4;
const unsigned int columns = 4;
char first[rows][columns] = {
{'z', 'c', 'a', 'f'},
{'a', 'a', 'w', 'e'},
{'y', 'a', 'b', 'z'},
{'n', 'e', 'i', 'o'}
};

const unsigned int size = 5;
const unsigned int columnNumber = 3;
char column[size];
getColumn(first, columnNumber, column);

• The code snippet performs the following: see image.
• void insertionSort(char data[], int size): This function takes as an argument an array of type char. It also takes as an argument the size or length of the array. This function implements insertion sort which is a simple (quadratic) sorting algorithm. It is not the most efficient when it comes to performance but is efficient enough for small data sets. This function should perform in-place sorting. It is acceptable not to use pointer notation here.

char test[4] = {'z', 'c', 'a', 'f'};
insertionSort(test, 4);

• The code snippet performs the following: see image.
• void sortRow(char array()(arraySize], int row): This function takes as an argument a 2D array. It also takes a row as an argument that specifies which row should be sorted. The sorting algorithm should be insertion sort. It is acceptable not to use pointer notation here.

const unsigned int rows = 4;
const unsigned int columns = 4;

char first[rows][columns] = {
{'z', 'c', 'a', 'f'},
{'a', 'q', 'w', 'e'},
{'y', 'a', 'b', 'z'},
{'n', 'e', 'i', 'o'}
};

sortRow(first, 0);

• The code snippet performs the following: see image.
• void sortColumn(char array()(array Size], int column): This function takes as an argument a 2D array. It also takes a column as an argument that specifies which column should be sorted. The sorting algorithm should be insertion sort. It is acceptable not to use pointer notation here.

const unsigned int rows = 4;
const unsigned int columns = 4;

char first[rows][columns] = {
{'z', 'c', 'a', 'f'},
{'a', 'q', 'w', 'e'},
{'y', 'a', 'b', 'z'},
{'n', 'e', 'i', 'o'}
};

sortColumn(first, 0);

• The code snippet performs the following: see image.