Vector Int

Introduction

This lab will introduce you to sorting and reinforce your understanding of vectors and passing them to functions. In this lab, you will sort vectors of numbers using given user-defined functions, find statistics on sorted vectors, and output the found statistics to the terminal.

Lab: Getting Statistics from Sorted Vectors

Download the zip file from Canvas to receive a prebuilt main for you to code in. When you run this prebuild main you must pass it one command line argument, the count of integers you want in your vector you are sorting.

In the provided helpers.cpp file you have been provided with 3 sorts:

• Bubble Sort - https://en.wikipedia.org/wiki/Bubble_sort
• Selection Sort - https://en.wikipedia.org/wiki/Selection_sort
• Insertion Sort - https://en.wikipedia.org/wiki/Insertion_sort

You do not need to implement these sorts in this lab. You will need to know how to use the provided sort functions in helpers.cpp in order to sort vectors in this lab. The sort functions you will use are:

• Use bubbleSort(vector< int> to bubble sort a vector using reference parameters.
• Use selectionSort(vector< int>) to selection sort a vector using reference parameters.
• Use insertionSort(vector< int>) to insertion sort a vector using reference parameters.

Passing a vector to any of these functions will sort the vector using the indicated sort method.

LAB

In lab11.cpp in main there are 3 sections to code in, one for each sort. In each section you are given an unsorted vector of integers contained in a variable named list. You will need to perform the following operations on list in each section:

• Sort the vector using the proper sort function.
• Find the minimum of the sorted vector.
• Find the maximum of the sorted vector.
• Find the sum of the vector.
• Find the average of the vector.
• Reverse the elements of the vector.

You will need to output 1-6 to the terminal from main calling functions written in this lab.

To accomplish 2-6 you will need to implement the functions on the following page

Minimum of a Sorted Vector

Create a function:

int minimum(const vector< int>&)

The vector passed to this function is guaranteed to be sorted. Return the first element of the passed vector as it is the minimum element in the vector. Do not use any loops in this function.

Maximum of a Sorted Vector

Create a function:

int maximum(const vector< int>&)

The vector passed to this function is guaranteed to be sorted. Return the last element of the passed vector as it is the maximum element in the vector. Do not use any loops in this function.

Sum of a Vector

Create a function:

int sum(const vector< int>&)

Iterate through the passed vector summing up each of the elements of the vector. Once you have summed all of the numbers in the vector, return the sum you got. You may use loops in this function.

Average of a Vector

Create a function:

double average(const vector< int>&)

Call the previous sum function you created on the passed vector in order to get the sum of it. Once you have gotten the sum of the vector, divide it by the size of the vector, this gives you the average of the vector. Return this obtained average from your function. Do not use any loops directly in this function.

Reverse a Vector

Create a function:

void reverseVector(vector< int>&)

To perform this operation you want to go through the vector with elements at positions 0, 1, , n-2, n-1, swapping elements 0 with element n-1, element 1 with element n-2, and so on until you eventually hit the middle of the vector. An algorithm to do such is as follows:

• Make 2 variables: start which is initialized at 0, and end which is initialized at vector.size() - 1 (for the passed vector).
• Swap the element at start with the element at end.
• Increment start.
• Decrement end.
• Continue from (2) until end < start.

You may use loops in this function.

Once you have completed the above functions you can use them to match the example output. For each sort section, call each function you created on the provided list and then output the result of the function call in the order provided at the beginning of this lab. The order to call/output is:

• Sort list (sort is dependent on which section you are doing), output the sorted list you get as a result.
• Find the minimum of the sorted list, output the minimum you get as a result.
• Find the maximum of the sorted list, output the maximum you get as a result.
• Find the sum of the sorted list, output the sum you get as a result.
• Find the average of the sorted list, output the average you get as a result.
• Reverse the sorted list, output the reversed list you get as a result.

In the Example Output your "Elapsed Time" will vary, therefore runtimes do not need to match exactly.

When you have finished the coding portion of this lab run your program with an input of 50000 (this will cause your program to create and sort vectors of 50000 integers). This will take a few seconds to run. Once your program has finished executing you will notice some sorts take less time to run than others. You do not need to submit the following questions for grading, but some questions to think about are:

• Which sort takes the longest to sort?
• Which sort takes the shortest to sort?
• Why does selection sort speed up sorting?
• Why does insertion sort speed up sorting?

Again, you do not need to submit these 4 questions for grading.

Example Output

An example of an interaction with your program is shown below, your output should match these examples exactly. (The words printed in blue are from the computer, based on your commands, the words in red are user input. Note: these colors are simply here to distinguish components and not needed in your program.):

Example 1

Alexs-iMac:lab11 alex$ ​./a.out 10
BUBBLE SORT
Unsorted: 8 50 74 59 31 73 45 79 24 10
Sorted: 8 10 24 31 45 50 59 73 74 79
Minimum: 8
Maximum: 79
Sum: 453
Average: 45.3
Reverse: 79 74 73 59 50 45 31 24 10 8
Elapsed time in seconds: 36 microseconds.
SELECTION SORT
Unsorted: 41 66 93 43 88 4 28 30 41 13
Sorted: 4 13 28 30 41 41 43 66 88 93
Minimum: 4
Maximum: 93
Sum: 447
Average: 44.7
Reverse: 93 88 66 43 41 41 30 28 13 4
Elapsed time in seconds: 30 microseconds.
INSERTION SORT
Unsorted: 4 70 10 58 61 34 100 79 17 36
Sorted: 4 10 17 34 36 58 61 70 79 100
Minimum: 4
Maximum: 100
Sum: 469
Average: 46.9
Reverse: 100 79 70 61 58 36 34 17 10 4
Elapsed time in seconds: 28 microseconds.

Example 2

Alexs-iMac:lab11 alex$ ​./a.out 100
BUBBLE SORT
Unsorted: Too long!
Sorted: Too long!
Minimum: 2
Maximum: 100
Sum: 4717
Average: 47.17
Reverse: Too long!
Elapsed time in seconds: 85 microseconds.
SELECTION SORT
Unsorted: Too long!
Sorted: Too long!
Minimum: 2
Maximum: 100
Sum: 5118
Average: 51.18
Reverse: Too long!
Elapsed time in seconds: 50 microseconds.
INSERTION SORT
Unsorted: Too long!
Sorted: Too long!
Minimum: 1
Maximum: 100
Sum: 4960
Average: 49.6
Reverse: Too long!
Elapsed time in seconds: 38 microseconds.