EECS168 09:Homework8

Navigation
Home
Information
Syllabus Schedule Lecture Notes Exam Reviews
Classwork
Labs Homework Submitting Work

Overview

You are going to write a program that reads a list of numbers from a file. There may be duplicate numbers in the file, but they will all be non-negative integers.
DUE DATE: The electronic submission of your homework must be received before 11:59 pm, Monday, 4th of May.

Problem Description and Program Requirements

1. Write a program recursiveSort.cpp.
2. The program takes a file as an input, stores the contents in a vector, and displays it unsorted the screen.
3. The program should give the user a list of options, 1 add a number, 2 remove a number by index location, 3 sort the list of numbers.
   1. The first option should ask the user for a number and add it to the end of the list.
   2. The second option should remove the number at the position specified by the user.
   3. The third option should sort the list from lowest to highest, with duplicate entries appearing consecutively.
4. After each user operation the program should display the list of numbers and ask if the user would like to make another selection.
5. The outline of a class numbers is given below. No additional member functions or variables may be added, and the arguments and return types should stay the same.
6. The main() provided is only for testing the numbers class, you should replace it with your own main.
7. You should check user input for validity, e.g. non-negative integers input, and indexes within the range of existing values to be removed.

Writing your own recursive member function

We are going to add the concept of recursive functions to the concept of classes from last week's lab. You will create a class called numbers. It will store a list of integers in a private vector, and will have a member function to sort the vector. The sort function should be recursive. You will also notice that the sort function is overloaded. There is a public member function which takes no arguments. This calls the private sort function, which is the recursive function. The private function will call itself iteratively until the vector is sorted. All the other member functions have been defined for you.

Program outline:

/*
 * Author: Ima KU Student
 * Date: 04/28/2009
 * Program to define a class which manages a vector of integers, and uses a recursive sorting function
 */

#include<iostream>
#include<vector>

using namespace std;

class numbers
{
public:
	void add(int n);   // Adds a new number to the end of the vector
	int remove(int i); // Removes the element at the specified index of the vector
	void sort();       // Calls the private recursive sort function
	void display();    // Prints the vector to the screen
	
private:
	vector<int> numbers;
	vector<int> sort(vector<int> unsorted_list);
};

void numbers::add(int n)
{
    // Insert your code here
}

int numbers::remove(int index)
{
    // Insert your code here.  Hint: You will probably need to use the numbers.pop_back() vector member function.
}

void numbers::sort()
{
	numbers = sort(numbers);
}

void numbers::display()
{
	for (int i=0;i<numbers.size();i++){
		cout << numbers[i] << ' ';
	}
	cout << endl;
}

vector<int> numbers::sort(vector<int> unsorted_list)
{
        \\ Insert your code here to complete the sort function.
}

int main(){
	numbers our_numbers;
	for (int i=15;i>=0;i--){
		our_numbers.add(i);
	}
	for (int i=25;i>=12;i--){
		our_numbers.add(i);
	}
	cout << "Unsorted numbers: ";
	our_numbers.display();
	our_numbers.sort();
	cout << "Sorted numbers: ";
	our_numbers.display();
	return 0;
}

Completing the sort function will probably require you to think differently then you would using normal loops, but you can start by asking yourself how you would solve it using a while loop? You would probably look for the smallest number in the unsorted vector, remove it, and put it at the beginning of the sorted vector. You can then look for the next smallest. You would stop when there are no more numbers in the unsorted vector.

Example testing output from the provided main:

./recursiveSort

Unsorted numbers: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 25 24 23 22 21 20 19 18 17 16 15 14 13 12
Sorted numbers: 0 1 2 3 4 5 6 7 8 9 10 11 12 12 13 13 14 14 15 15 16 17 18 19 20 21 22 23 24 25

Notes

• Your source code files should have comments at the top with:
  • your name
  • the class ("EECS 168")
  • the assignment name (i.e., "Homework 8")
  • the date
  • an explanation of what the code is supposed to do
• You should have comments in the code that explain what the code is doing.

Additional Requirements For EECS 169 Students

• Allow the user to select whether to sort the list in ascending or descending order. You may add a parameter to each of the sort functions to indicate ascending or descending.

Submission

The files you should submit electronically (in a tarball) are:

• recursiveSort.cpp: Your source code.
• testing.txt: The testing you did on your finished program. Test your code with a variety of input files and user input.