Task 1: Write the code for the printArray function. The function takes an array
ID: 3748376 • Letter: T
Question
Task 1: Write the code for the printArray function. The function takes an array and the size of the array as arguments. The function should print to screen the contents of the array it receives as argument. The contents of the array should be printed on a single line. Run the program. You should see array A, which is created in the first line of the main function, displayed to screen.
Task 2: Write the code for the isSorted function. It should return true if the items in the array it receives as argument are sorted (in ascending order), and false otherwise. Uncomment the first block of comments in the main function and run the program. The isSorted function should pass the test (you should not see any error message displayed).
Task 3: Before you write the insertionSort function, take a look at the insert function and answer the following questions:
QUESTION 1: Which lines from the INSERTION-SORT algorithm is the function implenting?
QUESTION 2 :
A) How would you describe what the insert function does?
B) What assumption is made about the array that it takes as argument
Task 3 pt 2:
For task 3, you must make use of the insert function to sort array A manually. That is, you must make as many calls to the insert function as needed to have the array sorted. Do not use any loops. Uncomment the second block of comments in the main function and run the program. Your program should pass the tests (you should not see any error message displayed).
TASK 4. Implement the insertionSort function according to the INSERTION-SORT algorithm. Make use of the insert function. Uncomment the third block of comments in the main function and run the program. Your program should pass all tests (you should not see any error message displayed).
TASK 5. Create an array with 10 numbers of your choice in random order and call it arrayLastName, where you will substitute LastName for YOUR last name. For example, my array would be called arrayMichelle. Then, call the insertionSort function to sort the items in your array. Next, use assert to test that the array is now sorted (using the isSorted function). Finally, you should print your sorted array (using the printArray function).
Explanation / Answer
#include <iostream>
#include <cassert>
using namespace std;
//the insert function will move the element/key forward[toward the right] and insert element/key in proper place
void insert(int A[], int i, int key) {
while (i >= 0 && A[i] > key){
A[i + 1] = A[i];
i = i - 1;
}
A[i + 1] = key;
}
void insertionSort(int A[], size_t N) {
for(size_t i=1;i<=N-1;i++)
insert( A, i-1, A[i]);
}
bool isSorted(int A[], size_t N){
bool sorted = true;
if (N == 1 or N == 0){
sorted = true;
}
else{
for(size_t i=1;i<N;i++)
{
if (A[i-1] > A[i]){
sorted = false;
break;
}
}
}
return sorted;
}
void printArray(int A[], size_t N){
for(size_t i=0;i<N;i++)
{
cout << A[i] << " " ;
}
cout << endl;
}
int main () {
int A[] = {22, 11, 99, 88, 9, 7, 42};
printArray(A, 7);
/*FIRST BLOCK OF COMMENTS*/
assert(!isSorted(A, 7));
/**/
//Calls to insert function go here (to sort the array manually)
insert( A, 0, A[1]);
insert( A, 1, A[2]);
insert( A, 2, A[3]);
insert( A, 3, A[4]);
insert( A, 4, A[5]);
insert( A, 5, A[6]);
/*SECOND BLOCK OF COMMENTS*/
assert(isSorted(A, 7));
cout << "Array after sorting: " << endl;
printArray(A, 7);
/**/
/*THIRD BLOCK OF COMMENTS*/
int B[] = {222, 111, 999, 888, 99, 77, 422};
insertionSort(B, 7);
assert(isSorted(B, 7));
cout << "Array after sorting: " << endl;
printArray(B, 7);
/**/
/*FOURTH BLOCK OF COMMENTS for arrayLastName*/
int arrayLastName[] = {522, 111, 99, 88, 9, 7, 888, 99, 77, 422};
insertionSort(arrayLastName, 10);
assert(isSorted(arrayLastName, 10));
cout << "Array after sorting: " << endl;
printArray(arrayLastName, 10);
/**/
}
--outputt---
22 11 99 88 9 7 42
Array after sorting:
7 9 11 22 42 88 99
Array after sorting:
77 99 111 222 422 888 999
Array after sorting:
7 9 77 88 99 99 111 422 522 888
QUESTION 1: Which lines from the INSERTION-SORT algorithm is the function implenting?
The part of moving the element/key forward[toward the right] and insert element/key in proper place is done by the insert function.
For insert-sort to apply there is now only need for single loop which calls elements one by one.
The internal second loop is done by the insert function
QUESTION 2 :
A) How would you describe what the insert function does?
the insert function will move the element/key forward[toward the right] and insert element/key in proper place
B) What assumption is made about the array that it takes as argument
assumption made about the array is that, before the insert the position before the insert is already in sorted order
for example before the insert( A, 2, A[3]) call; the elements at index 0 and index 1 are already in sorted order
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.