//file: COOL004.cpp
//Author: AOU
//Date 09/10/2004
////////////////////////////////////////////////////////
// Assignment 01, Date Assigned 9/3/2004, Due: 9/10/2004
////////////////////////////////////////////////////////
/*
As discussed in the class, implement the search function that finds
the occurrence of a value x in a list of sorted values and returns
the first position of the value and the number of times it occurs.
Submit the printed form of the following:
(1) Detailed Description:
(2) Two Example:
(3) Detailed Algorithm:
(4) Code:
(5) Output from 20 Test Cases:
void COOL::search(int x, int &p, int &c)
{
//Code to be replaced
p=1;
c=3;
}
Sample output:
COOL[19] = [-9999 0 1 1 2 3 5 5 5 6 7 7 7 7 7 8 9 9 9 10 9999 ]
Searching for 7
Found 5 copies of 7 starting at position 10
In other words, 7 was found at positions 10 11 12 13 14
COOL[18] = [-9999 1 2 2 4 5 5 6 6 7 7 7 8 8 9 9 10 10 10 9999 ]
Searching for 4
Found 1 copies of 4 starting at position 4
In other words, 4 was found at positions 4
COOL[7] = [-9999 0 0 5 5 5 6 7 9999 ]
Searching for 4
Found 0 copies of 4 starting at position -1
In other words, 4 was found at positions
COOL[5] = [-9999 0 1 3 6 10 9999 ]
Searching for 0
Found 1 copies of 0 starting at position 1
In other words, 0 was found at positions 1
*/
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
// includes
////////////////////////////////////////////////////////
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
////////////////////////////////////////////////////////
// constants
////////////////////////////////////////////////////////
int const MAX_SIZE = 20+2;
int const INFINITY = 9999;
int const TEST_COUNT = 20;
int const MAX_VALUE = 10;
/*
Description:
Example:
Algorithm:
*/
//Problem:
// List of values (duplicates allowed) kept in order
// with several operations:
// initialize, insert, delete, modify, search, ...
//Example:
// {}, {50}, {25,50}, {25,36,50}, {25,36,50,76},
// {25,36,50,76}
//Algorithms:
////////////////////////////////////////////////////////
// class COOL
////////////////////////////////////////////////////////
class COOL
{
private:
int a[MAX_SIZE];
int n;
void swap(int &v1, int &v2)
{
int t = v1;
v1 = v2;
v2 = t;
};
public:
COOL(void);
bool insert(int x);
void display(void) const;
bool isSorted(void)const;
COOL(int m);
int search(int x) const;
void search(int x, int &p, int &c) const;
void shuffle(void);
void sortBubble1(void);
};
////////////////////////////////////////////////////////
// test function prototypes
////////////////////////////////////////////////////////
void test_initialize(void);
void test_constructor(void);
void test_search(void);
void test_search2(void);
void test_shuffle(void);
void test_sortBubble1(void);
////////////////////////////////////////////////////////
// main
////////////////////////////////////////////////////////
void main(void)
{
srand(time(NULL));
//test_initialize();
//test_constructor();
//test_search();
//test_search2();
//test_shuffle();
test_sortBubble1();
}
////////////////////////////////////////////////////////
// void COOL::sortBubble1(void);
////////////////////////////////////////////////////////
/*
-99,1, 2, 3, 4, 5,+99
for i = 1 to n-1
for j=0 to n-2
if a[i] > a[i+1] then
swap a[i], a[i+1]
end for
end for
*/
void COOL::sortBubble1(void)
{
for (int i = 1; i<=n-1; i++)
{
for (int j=0; j<=n-2; j++)
{
if (a[j] > a[j+1])
swap(a[j], a[j+1]);
}
}
}
////////////////////////////////////////////////////////
// void test_sortBubble1(void)
////////////////////////////////////////////////////////
void test_sortBubble1(void)
{
cout << "+++++++++++++++++++++++++++++++\n";
cout << "test_sortBubble1\n";
cout << "+++++++++++++++++++++++++++++++\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int m = rand()%MAX_SIZE;
COOL myList(m);
myList.display();
myList.shuffle();
cout << "After shuffle\n";
myList.display();
myList.sortBubble1();
cout << "After sortBubble1\n";
myList.display();
if (myList.isSorted())
cout << "List is sorted\n";
else
cout << "List is NOT sorted\n";
cout << "------------------------\n";
}
}
////////////////////////////////////////////////////////
// void COOL::shuffle(void)
////////////////////////////////////////////////////////
/*
Description:
shuffles/scramble/unsort/re-organize/shake
Example:
[-99, 12, 24, 24 99]=>[-99, 24, 12, 24 99]
Algorithm:
randomly pick two values and swap
delete a value randomly while building another sequentially
split the list into two sublists and merge them randomly
randomly pick a value and swap it with the first value
do the following n*n
p = random value between 1 and n-2
swap a[1] with a[p]
*/
void COOL::shuffle(void)
{
if (n<=3)
return;
for (int i=1; i<=n*n; i++)
{
int p = 1 + rand()%(n-2);
swap(a[1],a[p]);
}
}
////////////////////////////////////////////////////////
// void test_shuffle(void)
////////////////////////////////////////////////////////
void test_shuffle(void)
{
cout << "+++++++++++++++++++++++++++++++\n";
cout << "test_shuffle\n";
cout << "+++++++++++++++++++++++++++++++\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int m = rand()%MAX_SIZE;
COOL myList(m);
myList.display();
myList.shuffle();
cout << "After shuffle\n";
myList.display();
cout << endl;
}
}
////////////////////////////////////////////////////////
// void COOL::search(int x, int &p, int &c)
////////////////////////////////////////////////////////
/*
Description: searches for copies of x in the list,
in p returns the position, in c returns the number
of copies of x starting at p.
Example:
[-99, 12, 24, 24, 24, 45, 50, 60, 75, 99], 24
=> 2, 3
=> at positions 2, 3, 4
Algorithm:
*/
void COOL::search(int x, int &p, int &c) const
{
//Code to be replaced
p=1;
c=3;
}
////////////////////////////////////////////////////////
// void test_search2(void)
////////////////////////////////////////////////////////
void test_search2(void)
{
cout << "+++++++++++++++++++++++++++++++\n";
cout << "test_search2\n";
cout << "+++++++++++++++++++++++++++++++\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int m = rand()%MAX_SIZE;
COOL myList(m);
myList.display();
int x = rand()%(MAX_VALUE +1);
cout << "Searching for " << x << endl;
int p, c;
myList.search(x, p, c);
cout << "Found " << c << " copies of " << x << " starting at position " << p << endl;
cout << "In other words, " << x << " was found at positions ";
for (int j=p; j<=p+c-1; j++)
cout << j << ' ';
cout << endl << endl;
}
}
////////////////////////////////////////////////////////
// int COOL::search(int x)
////////////////////////////////////////////////////////
/*
Description: searches for the first value x in the list
and returns the position if found else returns -1
Example:
[-99, 12, 24, 45, 50, 60, 75, 99], 24 => 2
[-99, 12, 24, 45, 50, 60, 75, 99], 25 => -1
Algorithm:
for i=1 to n-2
if x = a[i] then
return i
if x < a[i] then
exit loop
end for
return -1
*/
int COOL::search(int x) const
{
for (int i=1; i<=n-2; i++)
{
if (x == a[i])
return i;
if (x < a[i])
break;
}
return -1;
}
////////////////////////////////////////////////////////
// void test_search(void)
////////////////////////////////////////////////////////
void test_search(void)
{
cout << "+++++++++++++++++++++++++++++++\n";
cout << "test_search\n";
cout << "+++++++++++++++++++++++++++++++\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int m = rand()%MAX_SIZE;
COOL myList(m);
myList.display();
int x = rand()%(MAX_VALUE +1);
cout << "Searching for " << x << endl;
cout << "Found at " << myList.search(x) << endl;
}
}
////////////////////////////////////////////////////////
// COOL::COOL(int m)
////////////////////////////////////////////////////////
//create a list with m values
COOL::COOL(int m)
{
n = 2;
a[0] = -INFINITY;
a[1] = +INFINITY;
for (int i=2; i<=MAX_SIZE-1; i++)
a[i] = 0;
for (i=1; i<=m; i++)
{
int x = rand()%(MAX_VALUE+1);
insert(x);
}
}
////////////////////////////////////////////////////////
// void test_constructor(void)
////////////////////////////////////////////////////////
void test_constructor(void)
{
cout << "+++++++++++++++++++++++++++++++\n";
cout << "test_constructor\n";
cout << "+++++++++++++++++++++++++++++++\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int m = rand()%MAX_SIZE;
COOL myList(m);
cout << "After COOL myList(" << m << ");\n";
myList.display();// display(myArray, m);
}
}
////////////////////////////////////////////////////////
// bool COOL::isSorted(void)
////////////////////////////////////////////////////////
// bool isSorted(int a[], int n)
/*
Description: checks if the list is in order
Example:
Algorithm:
*/
bool COOL::isSorted(void) const
{
for (int i=0; i<=n-2; i++)
if (a[i] > a[i+1])
return false;
return true;
}
////////////////////////////////////////////////////////
// void test_initialize(void)
////////////////////////////////////////////////////////
void test_initialize(void)
{
cout << "+++++++++++++++++++++++++++++++\n";
cout << "test_initialize\n";
cout << "+++++++++++++++++++++++++++++++\n";
COOL myList;
for (int i=1; i<=TEST_COUNT/TEST_COUNT; i++)
{
//myList.initialize(); //initialize(myArray, m);
myList.display();// display(myArray, m);
int j, x;
for (j=1; j<=TEST_COUNT; j++)
{
x = rand()%(MAX_VALUE+1);
myList.insert(x); //insert(myArray, m, x);
myList.display(); //display(myArray, m);
if (myList.isSorted()) //(isSorted(myArray, m))
cout << "List is in order\n";
else
cout << "List is NOT in order\n";
}
}
}
////////////////////////////////////////////////////////
// COOL::COOL(void)
////////////////////////////////////////////////////////
/*
Description:
Initializes the list of values by setting n=0, and
a[0..MAX_SIZE-1] = 0;
Algorithm:
n = 2
a[0] = -INFINITY
for i=1 to MAX_SIZE-2
a[i] = 0;
a[MAX_SIZE-1] = +INFINITY
*/
COOL::COOL(void)
{
n = 2;
a[0] = -INFINITY;
a[1] = +INFINITY;
for (int i=2; i<=MAX_SIZE-1; i++)
a[i] = 0;
}
////////////////////////////////////////////////////////
// bool COOL::insert(int x)
////////////////////////////////////////////////////////
/*
Description: inserts x into the list and maintains the order
Example:
{}, {50}, {25,50}, {25,36,50}, {25,36,50,76},
{25,36,50,76}
Algorithm0:
Case0: list is full
Case1: x goes to empty list
x Case3: x > all the values in the list
x Case2: x < all the values in the list
Case4: x goes between two values and handle duplicates
Algorithm1:
m = n
s1: if (x >= a[m-1]) then
a[m] = x
n++
exit function
else
a[m] = a[m-1]
m--
goto s1
Algorithm2:
m = n
while x < a[m-1])
a[m] = a[m-1]
m--
wend
a[m] = x
n++
*/
bool COOL::insert(int x)
{
if (n >= MAX_SIZE)
return false;
int m = n;
while (x < a[m-1])
{
a[m] = a[m-1];
m--;
}
a[m] = x;
n++;
return true;
}
////////////////////////////////////////////////////////
// void COOL::display(void)
////////////////////////////////////////////////////////
/*
Description:
Algorithm:
*/
void COOL::display(void) const
{
cout << "COOL[" << n-2 << "] = [";
for (int i=0; i<=n-1; i++)
cout << a[i] << ' ';
cout << "]\n";
}
|