Archive for the ‘CMPSC 101’ Category

Bubble Sort and Binary Search

In Computer Science 101 one of our last assignments for the class was to create a program that first prompts the user to create a restaraunt menu essentially including food and calories. Than once the user is done entering menu items the user types “done”.  The program than sorts the data using a bubble sort which puts the items in alphabeltical order by comparing each individual item and than swaping if one has a greater value.

The next stage of the program is you can look up what you want by just searching. It does this using a binary search which basically searches the program from the middle and than works its way up or down based upon the numerical value the program assigns to it.

Here is the code below.

#include <iostream>

#include <string>

using namespace std;

int main()

{

string food[100];

string lookup;

int calories[100];

bool itemFound = false;

int a = –1;

// Enter Data

do

{

a++;

cout << “Enter a menu item (enter
‘done’ when finished): “
<< endl;

getline(cin, food[a]);

if (food[a] != “done”)

{

cout << “Enter the number of calories:
<< endl;

cin >> calories[a];

cin.ignore();

}

}while (food[a] != “done”);

// Sort

for (int x = 1; x < a; x++)

{

for (int y = 0; y < a-1; y++)

{

if (food[y] > food[x])

{

string tmpname = food[x];

int tmpage = calories[x];

food[x] = food[y];

calories[x] = calories[y];

food[y] = tmpname;

calories[y] = tmpage;

}

}

}

// Binary Search

while (itemFound == false)

{

cout << “Enter a product to look up:

;

getline(cin,lookup);

if (lookup == “done”)

{

itemFound = true;

break;

}

int upperbound = a;

int lowerbound = 0;

int position;

position = (lowerbound + upperbound) / 2;

while((food[position] !=
lookup) && (lowerbound <= upperbound))

{

if (food[position] > lookup)

upperbound = position – 1;

else if(food[position] < lookup)

lowerbound = position + 1;

position = (lowerbound + upperbound) / 2;

}

if (food[position] == lookup)

cout << food[position] << ” has

<< calories[position] << “calories.” << endl;

if (lowerbound

> upperbound)

cout << lookup << ” was not
found.”
<< endl;

}

}

Advertisements