//Date: 2003.03.12
//Author: AOU
//File: cArray13.cpp
/*
Added the following global friend functions:
areEqual
testAreEqual
*/
///////////////////////////////////////////////////////////
// include files
///////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
///////////////////////////////////////////////////////////
// constants
///////////////////////////////////////////////////////////
const int MAX_COUNT = 20; //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);
void testDefrag(void);
void testSortSelection(void);
void testAreEqual(void);
///////////////////////////////////////////////////////////
// class CArray
///////////////////////////////////////////////////////////
class CArray
{
public:
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 sortSelection(void);
friend bool areEqual(CArray array1, CArray array2);
};
bool areEqual(CArray array1, CArray array2);
///////////////////////////////////////////////////////////
// void main(void)
///////////////////////////////////////////////////////////
void main(void)
{
//srand(time(NULL));
// srand(2);
// testSearchSeq();
// testAreDistinct();
// testConstructorR();
// testSortBubble();
// testDisplayAll();
// testIsSorted();
// testShuffle();
// testFrag();
// testDefrag();
// testSortSelection();
testAreEqual();
}
///////////////////////////////////////////////////////////
// void testAreEqual(void)
///////////////////////////////////////////////////////////
void testAreEqual(void)
{
cout << "testAreEqual\n";
cout << "============\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray array1('r');
array1.display();
CArray array2('r');
array2.display();
if (areEqual(array1, array2))
cout << "Two arrays are equal\n";
else
cout << "Two arrays are NOT equal\n";
array1=array2;
array1.display();
array2.display();
cout << "----------\n";
if (areEqual(array1, array2))
cout << "Two arrays are equal\n";
else
cout << "Two arrays are NOT equal\n";
cout << "----------------------------\n";
}
}
///////////////////////////////////////////////////////////
//bool areEqual(CArray array1, CArray array2)
///////////////////////////////////////////////////////////
/*
order is not important
a1=[1, 5, 4]
a2=[1, 5, 4, 3]
areEqual(a1,a2) should return false
a1=[1, 5, 4]
a2=[1, 4, 5]
areEqual(a1,a2) should return true
a1=[1, 5, 4]
a2=[1, 5, 4]
areEqual(a1,a2) should return true
Algorithm0:
if both arrays are empty then
return true
if lenght of array1 <> length of array2 then
return false
ta1 = array1
ta2 = array2
sort ta1
sort ta2
do the following length of ta1 times
if ta1[i] <> ta2[i] then
return false
end if
end do
return true
*/
bool areEqual(CArray array1, CArray array2)
{
if ((array1.m_n == 0) && (array2.m_n == 0))
return true;
if (array1.m_n != array2.m_n)
return false;
CArray ta1 = array1;
CArray ta2 = array2;
ta1.sortSelection();
ta2.sortSelection();
for (int i=0; i<=ta1.m_n-1; i++)
if (ta1.m_a[i] != ta2.m_a[i])
return false;
return true;
}
///////////////////////////////////////////////////////////
// void testSortSelection(void)
///////////////////////////////////////////////////////////
void testSortSelection(void)
{
cout << "testSortSelection\n";
cout << "=================\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray array1('r');
array1.display();
array1.sortSelection();
cout << "After sortSelection\n";
array1.display();
if (array1.isSorted())
cout << "array1 is sorted\n";
else
cout << "array1 is NOT sorted\n";
cout << "----------------------------\n";
}
}
///////////////////////////////////////////////////////////
//void CArray::sortSelection(void);
///////////////////////////////////////////////////////////
/*
Sort by selection
Example
[23, 12, 44, 34, 33, 42]
[23, 12, 42, 34, 33] 44
[23, 12, 33, 34] 42 44
[23, 12, 33] 34 42 44
[23, 12] 33 34 42 44
[12] 23 33 34 42 44
[12 23 33 34 42 44]
Algorithm0:
do while size > 1
Find the pos of the highest value
Swap it with the value at the end
Ignore the last value by reducing the size
end do
Algorithm1:
size = n
do while size > 1
//Find the pos of the highest value in maxP
maxP = 0
do the following for i=1 to size-1
if a[i] > a[maxP] then maxP = i
end do
//Swap it with the value at the end
swap a[maxP] a[size-1]
//Ignore the last value by reducing the size
size--
end do
*/
void CArray::sortSelection(void)
{
int size = m_n;
while (size > 1)
{
//Find the pos of the highest value in maxP
int maxP = 0;
for (int i=1; i<=size-1; i++)
if (m_a[i] > m_a[maxP])
maxP = i;
//Swap it with the value at the end
swap(m_a[maxP], m_a[size-1]);
//Ignore the last value by reducing the size
size--;
}
}
///////////////////////////////////////////////////////////
// void testFrag(void)
///////////////////////////////////////////////////////////
void testDefrag(void)
{
cout << "testDefrag\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();
myArray.defrag();
cout << "After defrag\n";
myArray.displayAll();
cout << "------------------------\n";
}
}
///////////////////////////////////////////////////////////
// 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
s1:
//Find an undefined value and put its pos in p
p = -1
for i=0 to MAX_COUNT-1 do the following
if a[i] is undefined then
p = i, exit the loop
end if
end for
if p=-1 then exit function
q = -1
for i = p+1 to MAX_COUNT-1 do the following
if a[i] is not undefined then
q = i, exit loop
end if
end for
if q = -1 exit function
swap a[p] with a[q]
go to s1
do the following forever
//Find an undefined value and put its pos in p
p = -1
for i=0 to MAX_COUNT-1 do the following
if a[i] is undefined then
p = i, exit the loop
end if
end for
if p=-1 then exit function
q = -1
for i = p+1 to MAX_COUNT-1 do the following
if a[i] is not undefined then
q = i, exit loop
end if
end for
if q = -1 exit function
swap a[p] with a[q]
end forever
*/
void CArray::defrag(void)
{
int p, q, i;
while (true)
{
//Find an undefined value and put its pos in p
p = -1;
for (i=0; i<=MAX_COUNT-1; i++)
{
if (m_a[i] == UNDEFINED)
{
p = i;
break;
}
}
if (p==-1)
return;
q = -1;
for (i = p+1; i<=MAX_COUNT-1; i++)
{
if (m_a[i] != UNDEFINED)
{
q = i;
break;
}
}
if (q == -1)
return;
swap(m_a[p], m_a[q]);
}
}
///////////////////////////////////////////////////////////
// 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
///////////////////////////////////////////////////////////
/*
testAreEqual
============
Case #1
array[20]=5 4 4 5 4 0 0 4 2 5 5 1 3 1 5 1 2 3 0 3
array[9]=2 3 4 4 3 2 2 5 5
Two arrays are NOT equal
array[9]=2 3 4 4 3 2 2 5 5
array[9]=2 3 4 4 3 2 2 5 5
----------
Two arrays are equal
----------------------------
Case #2
array[12]=5 0 3 4 5 1 1 0 5 3 2 3
array[12]=2 3 1 5 4 5 2 4 3 3 1 5
Two arrays are NOT equal
array[12]=2 3 1 5 4 5 2 4 3 3 1 5
array[12]=2 3 1 5 4 5 2 4 3 3 1 5
----------
Two arrays are equal
----------------------------
Case #3
array[18]=1 4 4 5 2 0 0 4 4 2 4 4 2 3 2 3 4 2
array[12]=3 3 2 3 5 0 4 0 2 4 2 5
Two arrays are NOT equal
array[12]=3 3 2 3 5 0 4 0 2 4 2 5
array[12]=3 3 2 3 5 0 4 0 2 4 2 5
----------
Two arrays are equal
----------------------------
Case #4
array[16]=0 3 2 1 5 4 2 0 3 5 3 5 1 0 0 0
array[12]=2 5 0 5 5 2 4 0 3 5 3 3
Two arrays are NOT equal
array[12]=2 5 0 5 5 2 4 0 3 5 3 3
array[12]=2 5 0 5 5 2 4 0 3 5 3 3
----------
Two arrays are equal
----------------------------
Case #5
array[6]=4 0 5 0 5 5
array[9]=4 5 4 2 4 3 4 4 4
Two arrays are NOT equal
array[9]=4 5 4 2 4 3 4 4 4
array[9]=4 5 4 2 4 3 4 4 4
----------
Two arrays are equal
----------------------------
Case #6
array[6]=5 1 3 1 5 3
array[9]=5 5 1 2 5 0 2 4 2
Two arrays are NOT equal
array[9]=5 5 1 2 5 0 2 4 2
array[9]=5 5 1 2 5 0 2 4 2
----------
Two arrays are equal
----------------------------
Case #7
array[10]=3 2 0 5 0 5 4 5 0 5
array[2]=3 1
Two arrays are NOT equal
array[2]=3 1
array[2]=3 1
----------
Two arrays are equal
----------------------------
Case #8
array[9]=2 2 1 2 2 4 0 3 0
array[15]=0 4 1 0 5 1 0 2 0 2 1 5 2 1 0
Two arrays are NOT equal
array[15]=0 4 1 0 5 1 0 2 0 2 1 5 2 1 0
array[15]=0 4 1 0 5 1 0 2 0 2 1 5 2 1 0
----------
Two arrays are equal
----------------------------
Case #9
array[13]=5 3 0 5 1 4 5 2 5 3 2 5 1
array[14]=4 3 2 4 0 5 1 2 3 1 3 3 1 3
Two arrays are NOT equal
array[14]=4 3 2 4 0 5 1 2 3 1 3 3 1 3
array[14]=4 3 2 4 0 5 1 2 3 1 3 3 1 3
----------
Two arrays are equal
----------------------------
Case #10
array[19]=5 2 0 0 0 0 2 2 5 5 2 1 1 0 0 4 4 2 5
array[4]=5 2 5 3
Two arrays are NOT equal
array[4]=5 2 5 3
array[4]=5 2 5 3
----------
Two arrays are equal
----------------------------
Press any key to continue
*/
|