//Date: 2003.02.26
//Author: AOU
//File: cArray10.cpp
/*
Added the following member functions:
defrag algorithm
*/
///////////////////////////////////////////////////////////
// include files
///////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
///////////////////////////////////////////////////////////
// constants
///////////////////////////////////////////////////////////
const int MAX_COUNT = 10; //maximum size of array
const int MAX_VALUE = 5;
const int UNDEFINED = -9;
///////////////////////////////////////////////////////////
// prototypes
///////////////////////////////////////////////////////////
void testSearchSeq(void);
void testAreDistinct(void);
void testConstructorR(void);
void testSortBubble(void);
void testDisplayAll(void);
void testIsSorted(void);
void testShuffle(void);
void testFrag(void);
///////////////////////////////////////////////////////////
// class CArray
///////////////////////////////////////////////////////////
class CArray
{
private:
int m_a[MAX_COUNT];
int m_n;
void swap(int &x, int &y);
public:
CArray(void);
CArray(int m);
void display(void) const;
void displayMultiple(int c) const;
void populate(void);
bool areDistinct(void) const;
bool searchSeq(int x) const;
CArray(char ch);
void sortBubble(void);
void displayAll(void) const;
bool isSorted(void);
void shuffle(void);
void frag(void);
void defrag(void);
};
///////////////////////////////////////////////////////////
// void main(void)
///////////////////////////////////////////////////////////
void main(void)
{
//srand(time(NULL));
// srand(2);
// testSearchSeq();
// testAreDistinct();
// testConstructorR();
// testSortBubble();
// testDisplayAll();
// testIsSorted();
// testShuffle();
// testFrag();
}
// void CArray::defrag(void)
/*
Description:
defragment the array by moving values to the left
and undefined values to the right. By the time we
are done, there should not be any undefined value
left side of a value.
Examples:
before a[4]=-9 5 -9 0 -9 -9 2 2 -9 -9
after a[4]= 5 0 2 2 -9 -9 -9 -9 -9 -9
before a[4]= 5 0 2 2 -9 -9 -9 -9 -9 -9
after a[4]= 5 0 2 2 -9 -9 -9 -9 -9 -9
before a[4]=-9 5 -9 0 -9 -9 2 2 -9 -9
before a[4]=-9 5 -9 0 -9 -9 2 2 -9 -9
temp = -9 at 0
is there a value right of 0
a[4]=5 -9 0 -9 -9 2 2 -9 -9
a[4]=5 -9 0 -9 -9 2 2 -9 -9 -9
temp = -9 at 1
is there a value right of 1
a[4]=5 0 -9 -9 2 2 -9 -9 -9
a[4]=5 0 -9 -9 2 2 -9 -9 -9 -9
temp = -9 at 2
is there a value right of 2
a[4]=5 0 -9 2 2 -9 -9 -9 -9
a[4]=5 0 -9 2 2 -9 -9 -9 -9 -9
temp = -9 at 2
is there a value right of 2
a[4]=5 0 2 2 -9 -9 -9 -9 -9
a[4]=5 0 2 2 -9 -9 -9 -9 -9 -9
temp = -9 at 4
is there a value right of 4
a[4]=5 0 2 2 -9 -9 -9 -9 -9 -9
Algorithm:
Put all the undefined values at the end
or
Put all the defined value at the beginning
or
Make sure there is no undefined value on the left side of a value
Put all the undefined values at the end
s1:
Find an undefined value at pos p
if there a value right of p then
move a[p] to temp
delete value at position p
move temp to a[MAX_COUNT-1]
go to step s1
end if
s1:
Find an undefined value at pos p
if there a value right of p at q then
swap a[p] and a[q]
go to step s1
end if
*/
void CArray::defrag(void)
{
}
///////////////////////////////////////////////////////////
// void testFrag(void)
///////////////////////////////////////////////////////////
void testFrag(void)
{
cout << "testFrag\n";
cout << "========\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray myArray('r');
myArray.displayAll();
myArray.frag();
cout << "After frag\n";
myArray.displayAll();
cout << "------------------------\n";
}
}
///////////////////////////////////////////////////////////
// void frag(void);
///////////////////////////////////////////////////////////
/*
Description:
Fragments/scatters/unpack the values in the array
Example:
[1, 2, 3, 4,-9,-9, -9,-9,-9,-9]
=> [-9, 2,-9, 3,-9, 4,-9, 1,-9,-9]
Algorithm:
*/
void CArray::frag(void)
{
for (int i=1; i<=MAX_COUNT*1000; i++)
{
int pick = rand()%MAX_COUNT;
swap(m_a[pick], m_a[0]);
}
}
///////////////////////////////////////////////////////////
// void CArray::swap(int &x, int &y);
///////////////////////////////////////////////////////////
void CArray::swap(int &x, int &y)
{
int temp;
temp = x;
x = y;
y = temp;
};
///////////////////////////////////////////////////////////
// void testShuffle(void)
///////////////////////////////////////////////////////////
void testShuffle(void)
{
cout << "testShuffle\n";
cout << "===========\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray myArray('r');
myArray.display();
myArray.shuffle();
cout << "After shuffle\n";
myArray.display();
cout << "------------------------\n";
}
}
///////////////////////////////////////////////////////////
//void CArray::shuffle(void)
///////////////////////////////////////////////////////////
/*
a[1,3,6] => a[6,3,1]
a[3,3,1] => a[3,1,3]
a[1,2,3,4,5,6,7,8,9] => a[4,2,3,7,5,6,1,8,9]
Algorithm0:
do the following n*100 times
Pick a value randomly and swap it with the first value
Algorithm1:
do the following n*100 times
Pick a value randomly
Swap it with the first value
Algorithm2:
do the following n*100 times
pick = random value between 0 and n-1
Swap a[pick] with a[0]
*/
void CArray::shuffle(void)
{
for (int i=1; i<=m_n*100; i++)
{
int pick = rand()%m_n;
swap(m_a[pick], m_a[0]);
}
}
///////////////////////////////////////////////////////////
// void testIsSorted(void)
///////////////////////////////////////////////////////////
void testIsSorted(void)
{
cout << "testIsSorted\n";
cout << "============\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray myArray('r');
myArray.display();
if (myArray.isSorted())
cout << "myArray is sorted\n";
else
cout << "myArray is NOT sorted\n";
myArray.sortBubble();
cout << "After sortBubble\n";
myArray.display();
if (myArray.isSorted())
cout << "myArray is sorted\n";
else
cout << "myArray is NOT sorted\n";
cout << "------------------------\n";
}
}
///////////////////////////////////////////////////////////
//bool CArray::isSorted(void)
///////////////////////////////////////////////////////////
/*
a[1,3,6] => true
a[3,3,1] => false
a[3,3,9] => true
Algorithm0:
if a[0] and a[1] out of order then return false
if a[1] and a[2] out of order then return false
if a[2] and a[3] out of order then return false
...
if a[n-2] and a[n-1] out of order then return false
return true
Algorithm1:
do the following for i= 0 to n-2
if a[i] and a[i+1] out of order then return false
end do
return true
*/
bool CArray::isSorted(void)
{
for (int i= 0; i<= m_n-2; i++)
if (m_a[i] > m_a[i+1])
return false;
return true;
}
///////////////////////////////////////////////////////////
// void testDisplayAll(void)
///////////////////////////////////////////////////////////
void testDisplayAll(void)
{
cout << "testDisplayAll\n";
cout << "==============\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray array1('r');
array1.display();
array1.displayAll();
}
}
///////////////////////////////////////////////////////////
// void CArray::displayAll(void) const
///////////////////////////////////////////////////////////
void CArray::displayAll(void) const
{
cout << "array[" << m_n << "]=";
for (int i=0; i<MAX_COUNT; i++)
cout << m_a[i] << ' ';
cout << endl;
}
///////////////////////////////////////////////////////////
// void testSortBubble(void)
///////////////////////////////////////////////////////////
void testSortBubble(void)
{
cout << "testSortBubble\n";
cout << "==============\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray array1('r');
array1.display();
array1.sortBubble();
cout << "After sortBubble\n";
array1.display();
}
}
///////////////////////////////////////////////////////////
// void CArray::sortBubble(void)
///////////////////////////////////////////////////////////
/*
Sorts array contets in increasing order
[2, 3, 1] => [1, 2, 3]
Algorithm:
Check for special cases
repeat
from left to right put values in order
while something changed
somethingChanged = true
while somethingChanged = true
somethingChanged = false
do the following for i=0 to n-2
if a[i] > a[i+1] then
switch a[i] and a[i+1]
somethingChanged = true
end if
end while
repeat
somethingChanged = false
do the following for i=0 to n-2
if a[i] > a[i+1] then
switch a[i] and a[i+1]
somethingChanged = true
end if
while something changed
*/
void CArray::sortBubble(void)
{
if (m_n <= 1)
return;
bool somethingChanged;
int i;
do
{
somethingChanged = false;
for (i=0; i<=m_n-2; i++)
{
if (m_a[i] > m_a[i+1])
{
int temp = m_a[i+1];
m_a[i+1] = m_a[i];
m_a[i] = temp;
somethingChanged = true;
}
}
} while (somethingChanged == true);
}
///////////////////////////////////////////////////////////
// void testConstructorR(void)
///////////////////////////////////////////////////////////
void testConstructorR(void)
{
cout << "testConstructorR\n";
cout << "================\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray array1('r');
array1.display();
}
}
///////////////////////////////////////////////////////////
// CArray::CArray(char ch)
///////////////////////////////////////////////////////////
/*
A constructor fills array with values
depending on the value of parameter ch.
If ch is equal to 'r' then it fills the
array with random values which are
also random in count.
CArray array1('r');
gives: m_a[4,1,2], m_n=3
CArray array2('r');
gives: m_a[4,1,2,3,5,3], m_n=6
Algorithm:
m_n = random integer bet 0 and MAX_COUNT
do the following for i=0 to m_n-1
m_a[i] = random integer between 0 and MAX_VALUE
*/
CArray::CArray(char ch)
{
if (('r'==ch) || ('R'==ch))
{
m_n = rand()%(MAX_COUNT+1);
for (int i=0; i<=m_n-1; i++)
m_a[i] = rand()%(MAX_VALUE+1);
for (i=m_n; i<MAX_COUNT; i++)
m_a[i] = UNDEFINED;
}
else
m_n = 0;
}
///////////////////////////////////////////////////////////
// void testAreDistinct(void)
///////////////////////////////////////////////////////////
void testAreDistinct(void)
{
cout << "testAreDistinct\n";
cout << "===============\n";
for (int p=1; p <= 10; p++)
{
cout << "Case #" << p << endl;
int n = rand()%(MAX_COUNT+1);
CArray myArray(n);
myArray.display();
if (myArray.areDistinct())
cout << "Array has distinct values\n";
else
cout << "Array does not have distinct values\n";
cout << "--------------------------------------\n";
}
}
///////////////////////////////////////////////////////////
// bool CArray::areDistinct(void) const
///////////////////////////////////////////////////////////
bool CArray::areDistinct(void) const
{
if (m_n <= 1)
return true;
else
{
for (int i=1; i<=m_n-1; i++)
for (int j=0; j<=i-1; j++)
if (m_a[i] == m_a[j])
return false;
return true;
}
}
///////////////////////////////////////////////////////////
// void testSearchSeq(void)
///////////////////////////////////////////////////////////
void testSearchSeq(void)
{
cout << "testSearchSeq\n";
cout << "=============\n";
for (int p=1; p <= 10; p++)
{
cout << "Case #" << p << endl;
int n = rand()%(MAX_COUNT+1);
CArray myArray(n);
myArray.display();
int x;
x = rand()%(MAX_VALUE+1);
if (myArray.searchSeq(x))
cout << x << " is in the Array\n";
else
cout << x << " is NOT in the Array\n";
cout << "--------------------------------------\n";
}
}
///////////////////////////////////////////////////////////
// bool CArray::searchSeq(int x) const
///////////////////////////////////////////////////////////
bool CArray::searchSeq(int x) const
{
for (int i=0; i<=m_n-1; i++)
if (x == m_a[i])
return true;
return false;
}
///////////////////////////////////////////////////////////
// CArray::CArray(int m)
///////////////////////////////////////////////////////////
CArray::CArray(int m)
{
m_n = m;
for (int i=0; i<=m_n-1; i++)
m_a[i] = rand()%(MAX_VALUE+1);
for (i=m_n; i<MAX_COUNT; i++)
m_a[i] = UNDEFINED;
}
///////////////////////////////////////////////////////////
// void CArray::populate(void)
///////////////////////////////////////////////////////////
void CArray::populate(void)
{
m_n = rand()%(MAX_COUNT+1);
for (int i=0; i<=m_n-1; i++)
m_a[i] = rand()%(MAX_VALUE+1);
}
///////////////////////////////////////////////////////////
// void CArray::displayMultiple(int c)
///////////////////////////////////////////////////////////
void CArray::displayMultiple(int c) const
{
for (int i=1; i<=c; i++)
display();
};
///////////////////////////////////////////////////////////
// void CArray::display(void) const
///////////////////////////////////////////////////////////
void CArray::display(void) const
{
cout << "array[" << m_n << "]=";
for (int i=0; i<=m_n-1; i++)
cout << m_a[i] << ' ';
cout << endl;
}
///////////////////////////////////////////////////////////
// CArray::CArray(void)
///////////////////////////////////////////////////////////
CArray::CArray(void)
{
m_n=0;
for (int i=0; i<MAX_COUNT; i++)
m_a[i] = UNDEFINED;
cout << "Default constructor for CArray called\n";
}
///////////////////////////////////////////////////////////
// SAMPLE RUN
///////////////////////////////////////////////////////////
/*
*/
|