Program 3 will be worth 100 points and will be assigned points according to the following scheme:

 

Program compiles                                                                     25 Points

Documentation                                                 

      Header documentation (personal)                                         10 Points

      Internal documentation (what your program is doing)         10 Points

Style

      Indentation                                                                            5 Points

      White space                                                                           5 Points

Output

      Correctly calculated                                                              20 Points

      Correct use of Functions                                                       15 Points

      Correctly printed output (on monitor)                                              10 Points

Total                                                                                        100 Points

Assignment:

Part 1:

Write a program to do the following:

Write a program to implement pattern matching and sorting techniques. Give user a menu choice to either implement pattern matching or sorting technique. Keep running this code until this user decides to exit.

Pattern Matching Part:

Accept some text from the user. Accept the string that needs to be searched. Your program is supposed to print the number of occurrences of the string found within the text, and the position at which the pattern was found. Look at the following sample output:

Sample Output:

Enter text: “Call me Ishmael. Some years ago - never mind how long precisely - having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world. It is a way I have of driving off the spleen, and regulating the circulation”

String to search – “Some years ago”

Number of occurrences – 1

Position Found – 18

Sorting Techniques/Methods:

Generate 10 random numbers from 1 - 100 and sort those using the following sorting method. Each sorting method should be an individual function:

Bubble Sort – Look at the pseudo code explanation and pseudo code is in text book

Input Validation: Make sure only unique random numbers are generated

Sample Output:

Initial Set of numbers: 9 34 12 1 45 67 55 100 11 91

Bubble Sort – 1 9 11 12 34 45 55 67 91 100

Part 2 (optional):

Create a new program. Copy the contents of your PART A code. Modify the above code to add another sorting technique to the program.

Selection Sort – Look at the pseudo code explanation and pseudo code is in text book

Modify the menu choice, so when user chooses sorting, you give them 2 more menu choices to choose from: Bubble Sort, Selection Sort. Keep doing this user decided to exit. (If user chooses exit, then exit back to the Main Menu choice)

Sample Output:

Initial Set of numbers: 9 34 12 1 45 67 55 100 11 91

Bubble Sort – 1 9 11 12 34 45 55 67 91 100

Initial Set of numbers: 19 44 22 11 55 77 25 100 3 81

Selection Sort – 3 11 19 22 25 44 55 77 81 100

Before you start writing code, take some time to think about design of this program. Decompose into a set of functions, and create a main() function that reads like an outline for your solution to the problem. Make sure each function does one task.

* * Be sure to print the header documentation as you did in the fist programming assignment.  * *

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#include "sortalg.h"

//All the main menu options.
enum MAIN_MENU_OPTIONS {PATTERN_MATCHING, SORTING_TECHNIQUES, MAIN_MENU_EXIT, UNKNOWN};

//Search for occurences of searchText into text. Output in foundPositions the positions in the text where the searchtext is found.
//Returns number of occurences.
int seachForText(std::string text, std::string searchText, std::vector<int> &foundPositions)
{
int numberOfOccurences = 0;
std::size_t pos = text.find(searchText, 0);
while(pos != std::string::npos)
{
foundPositions.push_back(pos+1);
pos = text.find(searchText, pos+1);
numberOfOccurences++; //if text is found, increase by 1 the counter of texts found
}
return numberOfOccurences;
}

//Display a vector of numbers(integer) separated by space.
void displayVector(std::vector<int> vect)
{
std::vector<int>::const_iterator i;

for(i=vect.begin(); i!=vect.end(); ++i)
{
std::cout<<(*i)<<" ";
}
}

//Display search menu.
void GetSearchTextAndFullText(std::string &fullText, std::string &searchString)
{
//display to the screen to inform the user to enter some text
std::cout<<"Please enter some text:";
//read from the user the text into 'fullText' variable(some text).
std::getline (std::cin,fullText);

//display to the screen to inform the user to enter search text
std::cout<<"The string that needs to be searched:";
//read from the user the text to be searched into 'searchText' variable
std::getline (std::cin, searchString);
}

//display found positions
void displayFoundPositions(std::vector<int> foundPos)
{
std::cout<<"Position found - ";
displayVector(foundPos);
}

//display number of occurences
void displayNumberOfOccurences(int number)
{
std::cout<<"Number of occurences - "<<number<<std::endl;
}

//Menu for search - read input and search search, and output to the screen number of occurences and found positions
void patternMatchingMenu()
{
//search the input string into text
std::string fullText, searchText;
GetSearchTextAndFullText(fullText, searchText);//input by user full text and text to be seached
std::vector<int> foundPos;
int numberOfOccurences = seachForText(fullText, searchText, foundPos); //search the positions of searched text and full text and return number of occurences
//display number of occurences
displayNumberOfOccurences(numberOfOccurences);
displayFoundPositions(foundPos);
}

//Generate numbers = numberOfItems, values between minValue and maxValue.
//Returns the numbers generated in a vector.
std::vector<int> generateUniqueNumbers(int numberOfItems, int minValue, int maxValue)
{
std::vector<int> generatedValues;

for (int p = 0; p < numberOfItems; p++)
{
int num = minValue;
bool found = false;
do
{
found = false;
num = rand() % maxValue + minValue; //generate the number
std::vector<int>::const_iterator i;
for(i=generatedValues.begin(); i!=generatedValues.end(); ++i) //if the number is already in the list, generate another number (numbers are unique)
 //the list items are compared with generated number
{
if ((*i) == num)
{
found = true;
}
}
}
while (found == true);

generatedValues.push_back(num); //if not already in list, add it
}
return generatedValues;

}

void displaySortingTechniquesMenu();
void displaySortingTechniquesMenuLoop();

//read the option selected from main menu
MAIN_MENU_OPTIONS readMainMenuOption()
{
//read line from keyboard
std::string read;
std::getline (std::cin,read);

if (read[0] == '1')
return PATTERN_MATCHING;
if (read[0] == '2')
return SORTING_TECHNIQUES;
if (read[0] == '3')
return MAIN_MENU_EXIT;
return UNKNOWN;//if none of these, uknown menu
}

//Display menu according to option selected in main menu
void mainMenuSelection(MAIN_MENU_OPTIONS option)
{
switch(option)
{
case PATTERN_MATCHING:
patternMatchingMenu();
break;
case SORTING_TECHNIQUES:
displaySortingTechniquesMenuLoop();
break;
case MAIN_MENU_EXIT:
break;
}
}

//displays the main menu texts
void displayMainMenu()
{
std::cout<<std::endl<<"Main Menu"<<std::endl;
std::cout<<"1.Pattern Matching"<<std::endl;
std::cout<<"2.Sorting techniques"<<std::endl;
std::cout<<"3.Exit"<<std::endl;
}

//Displays the main menu while '3'= Exit is selected
void displayMainMenuLoop()
{
MAIN_MENU_OPTIONS option  = UNKNOWN;
do
{
//displays on screen the menu
displayMainMenu();
option = readMainMenuOption();
mainMenuSelection(option);
}
while(option != MAIN_MENU_EXIT); //exit the loop on selecting 3 option

}

//Display sorting techniques menu
void displaySortingTechniquesMenu()
{
std::cout<<std::endl<<"Please select an option."<<std::endl;
std::cout<<std::endl<<"1.Bubble sort"<<std::endl;
std::cout<<"2.Selection sort"<<std::endl;
std::cout<<"3.Exit"<<std::endl;
}

//Displays menu for selecting sort algorithm, select algorithm sort 1 = Bubble Sort, 2 = Selection Sort, 3 = Exit
void displaySortingTechniquesMenuLoop()
{
std::string read;
do
{
displaySortingTechniquesMenu();
//read from keyboard user input - menu selection
std::getline (std::cin,read);
if (read[0] == '1') //select bubble sort algorithm
{
std::vector<int> vectorUniqueNumbers = generateUniqueNumbers(10, 1, 100); //generate 10 numbers, from 1 to 100
cout<<"Initial set of numbers: ";    //display text
displayVector(vectorUniqueNumbers);  //display generated vector
bubble_sort(vectorUniqueNumbers);    //sort the vector
std::cout<<std::endl<<"Bubble sort - "; //display text
displayVector(vectorUniqueNumbers); //display sorted vector
}

if (read[0] == '2')//select selection sort algorithm
{
std::vector<int> vectorUniqueNumbers = generateUniqueNumbers(10, 1, 100);//generate 10 numbers, from 1 to 100
cout<<"Initial set of numbers: ";   //display text
displayVector(vectorUniqueNumbers); //display generated vector
selectionSort(vectorUniqueNumbers); // sort the vector
std::cout<<std::endl<<"Selection sort - ";//display text
displayVector(vectorUniqueNumbers); //display sorted vector
}
if (read[0] == '3') //select display main menu
{

}
}while(read[0] != '3'); //exit the loop on selecting 3 option


}
//main function - entry point
int main()
{
displayMainMenuLoop();
}



#include <iostream>
#include <string>
#include <vector>

//Bubble sort algorithm on a vector
void bubble_sort(std::vector<int>& a)
{
    for (int i = a.size(); i > 0;i--)
    {
         for (int j = 0, k = 1; k < i;j++, k++)
         {
             if (a[j] > a[k])
             {
                 int swap = a[j];
                 a[j] = a[k];
                 a[k] = swap;
             }
         }
    }
}

//swap items on position i with item in position j in vector
void swap(std::vector<int> & data, int i, int j)
{
    int tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
}


//selection sort algorithm on a vector
void selectionSort(std::vector<int> & data)
{
    int length = data.size();

    for (int i = 0; i < length; ++i)
    {
        int min = i;
        for (int j = i+1; j < length; ++j)
        {
            if (data[j] < data[min])
            {
                min = j;
            }
        }

        if (min != i)
        {
            swap(data, i, min);
        }
    }
}