# Assignment 04: Searching, Sorting, and Algorithm Analysis Solved

30.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

5/5 - (1 vote)

## Requirements

You are allowed to write everything in one file this time, so long it is organized and the file is not too long. If the file gets too long, please split it into multipleÂ `.h`Â andÂ `.cpp`Â files, and have aÂ `main.cpp`Â thatÂ `#include`s theÂ `.h`Â files, and can be used to call the functions prototyped in them.

All the files you produce must be able to exist within a single project. You will submit these files via github as normal.

### Setup

• Write a function namedÂ `print_vector`Â that takes aÂ `const std::vector<int> &`Â as an argument, and outputs the contents (separated by whitespace) to stdout (followed by a newline).
• Write theÂ `main`Â function. It doesn’t need to do anything right now, but as you write the functions below, you should put code inÂ `main`Â to test them.

### Selection Sort

Write a function namedÂ `selection_sort`Â that takes aÂ `std::vector<int> &`Â as an argument, and sorts it in-place. The algorithm is as follows:

1. For the index of each element in the array (the “current index”)
2. Find the index of the minimum element at or after the current index.
3. Swap the element at the current index with the smallest element found.

For a more thorough explanation, google around, or seeÂ the relevant Wikipedia entry.

### Merge Sort

Write a function namedÂ `merge_sort`Â that takes as an argument aÂ `const std::vector<int> &`Â and returns aÂ `std::vector<int>`containing all the elements of the vector that was passed as an argument, in ascending order. The algorithm (which is recursive) is as follows:

1. If the vector contains only 1 element, return the vector unchanged.
2. Otherwise, split the vector into two halves, namedÂ `left`Â andÂ `right`.
3. Recursively sort each half (i.e. callÂ `merge_sort(left);`Â andÂ `merge_sort(right);`).
4. MergeÂ `left`Â andÂ `right`Â into a new vector namedÂ `sorted`, in the following manner:
1. As long asÂ `left`Â andÂ `right`Â both have elements not inÂ `sorted`, compare the smallest such elements of each list, take the smaller of the two, and append it toÂ `sorted`.
2. Once all of the elements of eitherÂ `left`Â orÂ `right`Â are inÂ `sorted`, take the leftover elements and append them toÂ `sorted`.
5. ReturnÂ `sorted`.

For a more thorough explanation, google around, or seeÂ the relevant Wikipedia entry.

You may need to search around for the best way to split a vector into two smaller vectors. Here’sÂ one wayÂ from stackoverflow.

(None)

## Style

• Place your solution in aÂ `solution--YOURNAME`Â subdirectory (whereÂ `YOURNAME`Â is your GitHub username).
• Include your copyright and license information at the top of every file, followed by a brief description of the file’s contents, e.g.
```/* ----------------------------------------------------------------------------
* Copyright &copy; 2016 Ben Blazak <[email protected]>
* ------------------------------------------------------------------------- */

/**
* A short program to print "Hello World!" to standard output.
*/```
• Use “include guards” in allÂ `.h`Â files. Be sure to give the preprocessor variable a name corresponding to the file name. For example, inÂ `point.h`:
```#ifndef POINT_H
#define POINT_H
// ----------------------------------------------------------------------------

// ... everything besides the copyright information and file description

// ----------------------------------------------------------------------------
#endif  // POINT_H```
• `main()`Â must have its ownÂ `.cpp`Â file. I suggest calling itÂ `main.cpp`.
• Classes must have bothÂ `.h`Â andÂ `.cpp`Â files, with member functions defined in theÂ `.cpp`Â files unless they are truly trivial. If it makes sense, you may put multiple classes into one pair ofÂ `.h`Â andÂ `.cpp`Â files.
• Declare member functions and function arguments asÂ `const`Â when appropriate (in general, whenever possible).
• Document and format your code well and consistently. Be sure to clearly document the source of any code, algorithm, information, etc. that you use or reference while completing your work.
• Wrap lines at 79 or 80 columns whenever possible.
• End your file with a blank line.
• DoÂ notÂ useÂ `using namespace std;`. You may get around typingÂ `std::`Â in front of things or with, e.g.,Â `using std::cout;`.
• assignment-04.zip