//Solution4_sortedList19.cpp
//date: 11/01/2002
//author: AOU
////////////////////////////////////////////////////////////
// Include files
////////////////////////////////////////////////////////////
#include<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
////////////////////////////////////////////////////////////
// Constants
////////////////////////////////////////////////////////////
const int ARRAY_SIZE = 20;
const int UNDEFINED = -9999;
const int MAX_VALUE = 20;
const int TEST_COUNT = 5;
////////////////////////////////////////////////////////////
// Test function prototypes
////////////////////////////////////////////////////////////
void testSortBubble2(void);
void testSearchSeq(void);
void testSearchBinary(void);
void testSearchBinaryLM(void);
void testDisplayDistinct(void);
void testDisplayDistinctWithCounts(void);
void testRemove(void);
void testSortInsertion1(void);
void testAssignOperator(void);
void testInsertionOperator(void);
void testNotEqualOperator(void);
void testIsEmpty(void);
void testAdd(void);
void testSub(void);
void testAddMultiple(void);
////////////////////////////////////////////////////////////
// Class CSortedList
////////////////////////////////////////////////////////////
class CSortedList
{
private:
int m_array[ARRAY_SIZE];
int m_count;
int m_min;
int m_max;
public:
CSortedList(void);
CSortedList(char ch);
CSortedList(int n); //2002.10.02
void display(void) const;
bool insert(int x);
bool isSorted(void) const;
void sortBubble1(void);
void sortBubble2(void);
void sortInsertion1(void); //2002.10.07
void shuffle(void);
int searchSeq(int x) const;
int searchBinary(int x) const; //2002.09.23
int searchBinaryLM(int x) const; //2002.09.25
void displayDistinct(void) const; //2002.10.21
void displayDistinctWithCounts(void) const; //2002.10.23
bool remove(int x); //2002.09.30
int getAt(int p); //2002.10.02
int getCount(void); //2002.10.04
bool operator ==(CSortedList list2); //2002.10.09
friend ostream & operator << //2002.10.17
(ostream & bob, const CSortedList &aList);
bool operator !=(CSortedList list2); //2002.10.17
friend bool isEmpty(const CSortedList &aList);//2002.10.18
//Assignment #4, Due 10/25/2002
// c = a + b; no duplicate values in c, add(a, b, c);
friend void add(const CSortedList &aList,
const CSortedList &bList, CSortedList &cList);
// c = a - b; all elements of a that are not in b, sub(a,b,c);
friend void sub(const CSortedList &aList,
const CSortedList &bList, CSortedList &cList);
//printed source code of the functions you create and the output
//Assignment #5 Due 11/08/2002
friend void addMultiple(const CSortedList aList[], int listCount,
CSortedList &mList);
};
////////////////////////////////////////////////////////////
// main function
////////////////////////////////////////////////////////////
void main(void)
{
srand(time(NULL));
//testSortBubble2();
//testSearchSeq();
//testSearchBinary();
//testSearchBinaryLM();
//testRemove();
//testSortInsertion1();
//testAssignOperator();
//testInsertionOperator();
//testNotEqualOperator();
testAdd();
testSub();
//testIsEmpty();
//testDisplayDistinct();
//testDisplayDistinctWithCounts();
//testAddMultiple();
}
void addMultiple(const CSortedList inList[], int listCount,
CSortedList &outList)
{
//code to be supplied by you
}
void testAddMultiple(void)
{
const int m = 6;
for (int j=0; j<TEST_COUNT; j++)
{
CSortedList myLists[m];
for (int i= 0; i<m; i++)
{
myLists[i] = CSortedList(rand()%10);
cout << "List " << i << ": " << myLists[i];
}
CSortedList finalList;
cout << "FINAL: " ;
finalList.display();
addMultiple(myLists, m, finalList);
cout << "After addMultiple(myLists, m, finalList);\n";
for (i= 0; i<m; i++)
cout << "List " << i << ": " << myLists[i];
cout << "FINAL: " ;
finalList.display();
cout << "==================================\n";
}
}
////////////////////////////////////////////////////////////
// displayDistinct()
////////////////////////////////////////////////////////////
void CSortedList::displayDistinct(void) const
{
/*
Cases: empty, one value, more than one value
i = 0
p= i
display value at p
s1: if i< count-1 then
i = i+1
if value at i is not same as value at p then
p= i
display value at p
endif
goto s1:
i = 0
p = i
display value at p
while i< count-1
i = i+1
if value at i is not same as value at p then
p = i
display value at p
endif
end while
for i=0 to count-1
print the value if it is the first or not the same as previous
if i=0 or value[i]<>value[i-1] then display it
end for
*/
cout << "Distinct: ";
for (int i=0; i<this->m_count; i++)
if ((0==i) || (m_array[i]!=m_array[i-1]))
cout << m_array[i] << ' ';
cout << endl;
}
////////////////////////////////////////////////////////////
// testDisplayDistinct()
////////////////////////////////////////////////////////////
void testDisplayDistinct(void)
{
{
CSortedList myList;
myList.display();
myList.displayDistinct();
cout << "-----------------\n";
}
for (int j=1; j<=TEST_COUNT; j++)
{
CSortedList myList('r');
myList.display();
myList.displayDistinct();
cout << "-----------------\n";
}
}
////////////////////////////////////////////////////////////
// isEmpty
////////////////////////////////////////////////////////////
bool isEmpty(const CSortedList &aList)
{
return (0 == aList.m_count);
}
////////////////////////////////////////////////////////////
// testIsEmpty
////////////////////////////////////////////////////////////
void testIsEmpty(void)
{
cout << "testIsEmpty\n";
cout << "-------\n";
for (int i=0; i<TEST_COUNT; i++)
{
CSortedList aL('r'), bL;
cout << "aL = " << aL;
cout << "bL = " << bL;
if (isEmpty(aL))
cout << "aL is empty\n";
else
cout << "aL is not empty\n";
if (isEmpty(bL))
cout << "bL is empty\n";
else
cout << "bL is not empty\n";
cout <<"=================\n";
}
}
////////////////////////////////////////////////////////////
// add
////////////////////////////////////////////////////////////
void add(const CSortedList &aList,
const CSortedList &bList, CSortedList &cList)
{
//put in c distinct values from a and b
//a={1, 3, 5, 5}, b={3, 3, 4, 6, 6} then
//c={1, 3, 4, 5, 6}
/*
Algorithm:
empty cList
for each value in aList
if the value is not in cList then
insert the value to cList
for each value in bList
if the value is not in cList then
insert the value to cList
*/
cList.m_count = 0;
for (int i=0; i<aList.m_count; i++)
if (cList.searchBinary(aList.m_array[i]) == -1)
cList.insert(aList.m_array[i]);
for (i=0; i<bList.m_count; i++)
if (cList.searchBinary(bList.m_array[i]) == -1)
cList.insert(bList.m_array[i]);
}
////////////////////////////////////////////////////////////
// testAdd
////////////////////////////////////////////////////////////
void testAdd(void)
{
cout << "testAdd\n";
cout << "-------\n";
int m1;
int m2;
for (int i=0; i<TEST_COUNT; i++)
{
m1 = rand()%(ARRAY_SIZE/2);
m2 = rand()%(ARRAY_SIZE/2);
CSortedList aL(m1), bL(m2), cL('r');
cout << "aL = " << aL;
cout << "bL = " << bL;
cout << "cL = " << cL;
add(aL, bL, cL);
cout << "After add(aL, bL, cL);\n";
cout << "aL = " << aL;
cout << "bL = " << bL;
cout << "cL = " << cL;
cout <<"=================\n";
}
}
////////////////////////////////////////////////////////////
// sub
////////////////////////////////////////////////////////////
void sub(const CSortedList &aList,
const CSortedList &bList, CSortedList &cList)
{
//put in c distinct values from a not in b
//a={1, 3, 5, 5}, b={3, 3, 4, 6, 6} then
//c={1, 5}
/*
Algorithm:
empty cList
for each value in aList
if the value is not in bList then
if the value is not in cList then
insert the value in cList
*/
cList.m_count = 0;
for (int i=0; i<aList.m_count; i++)
if (bList.searchBinary(aList.m_array[i]) == -1)
if (cList.searchBinary(aList.m_array[i]) == -1)
cList.insert(aList.m_array[i]);
}
////////////////////////////////////////////////////////////
// testSub
////////////////////////////////////////////////////////////
void testSub(void)
{
cout << "testSub\n";
cout << "-------\n";
for (int i=0; i<TEST_COUNT; i++)
{
CSortedList aL('r'), bL('r'), cL('r');
cout << "aL = " << aL;
cout << "bL = " << bL;
cout << "cL = " << cL;
sub(aL, bL, cL); // cL = aL-bL;
cout << "After sub(aL, bL, cL);\n";
cout << "aL = " << aL;
cout << "bL = " << bL;
cout << "cL = " << cL;
cout <<"=================\n";
}
}
////////////////////////////////////////////////////////////
// operator !=
////////////////////////////////////////////////////////////
bool CSortedList::operator !=(CSortedList list2)
{
return !(*this==list2);
}
////////////////////////////////////////////////////////////
// testNotEqualOperator
////////////////////////////////////////////////////////////
void testNotEqualOperator(void)
{
CSortedList myList('r'), yourList(4), hisList('r');
cout << "myList\n";
myList.display();
cout << "yourList\n";
yourList.display();
cout << "hisList\n";
hisList.display();
if (myList.operator != (yourList))
cout << "myList != yourList\n";
else
cout << "myList == yourList\n";
myList = yourList = hisList;
cout << "After myList = yourList = hisList;\n";
cout << "myList\n";
myList.display();
cout << "yourList\n";
yourList.display();
cout << "hisList\n";
hisList.display();
int a=3, b=4, c=5;
cout << a << ' ' << b << ' ' << c << endl;
a = b = c;
cout << a << ' ' << b << ' ' << c << endl;
if (myList != yourList)
cout << "myList != yourList\n";
else
cout << "myList == yourList\n";
}
////////////////////////////////////////////////////////////
// operator <<
////////////////////////////////////////////////////////////
ostream & operator << (ostream & bob, const CSortedList &aList)
{
bob << "SortedList[" << aList.m_count << "]= ";
for (int i=0; i<aList.m_count; i++)
bob << aList.m_array[i] << ' ';
bob << endl;
return bob;
}
////////////////////////////////////////////////////////////
// testInsertionOperator
////////////////////////////////////////////////////////////
void testInsertionOperator(void)
{
CSortedList myList('r');
CSortedList yourList('r');
cout << myList << yourList;
}
////////////////////////////////////////////////////////////
// EqualOperator
////////////////////////////////////////////////////////////
bool CSortedList::operator ==(CSortedList list2)
{
if (this->m_count != list2.m_count)
return false;
for (int i=0; i<this->m_count; i++)
if (this->m_array[i] != list2.m_array[i])
return false;
return true;
}
////////////////////////////////////////////////////////////
// testAssignOperator
////////////////////////////////////////////////////////////
void testAssignOperator(void)
{
CSortedList myList('r'), yourList(4), hisList('r');
cout << "myList\n";
myList.display();
cout << "yourList\n";
yourList.display();
cout << "hisList\n";
hisList.display();
if (myList.operator == (yourList))
cout << "myList == yourList\n";
else
cout << "myList != yourList\n";
myList = yourList = hisList;
cout << "After myList = yourList = hisList;\n";
cout << "myList\n";
myList.display();
cout << "yourList\n";
yourList.display();
cout << "hisList\n";
hisList.display();
int a=3, b=4, c=5;
cout << a << ' ' << b << ' ' << c << endl;
a = b = c;
cout << a << ' ' << b << ' ' << c << endl;
if (myList == yourList)
cout << "myList == yourList\n";
else
cout << "myList != yourList\n";
}
////////////////////////////////////////////////////////////
// sortInsertion1
////////////////////////////////////////////////////////////
void CSortedList::sortInsertion1(void)
{
int i, temp;
bool sorted = false;
while (!sorted)
{
sorted = true;
for (i=m_count-2; i>=0; i--)
{
if (m_array[i] > m_array[i+1])
{
temp = m_array[i];
m_array[i] = m_array[i+1];
m_array[i+1] = temp;
sorted = false;
}
} //end for
}//end while
}
////////////////////////////////////////////////////////////
// testSortInsertion1
////////////////////////////////////////////////////////////
void testSortInsertion1(void)
{
for (int i=1; i<=10; i++)
{
CSortedList myList('r');
cout << "Original list\n";
myList.display();
if (myList.isSorted())
cout << " List is SORTED\n";
else
cout << " List is NOT SORTED\n";
myList.shuffle();
cout << "Shuffled list\n";
myList.display();
if (myList.isSorted())
cout << " List is SORTED\n";
else
cout << " List is NOT SORTED\n";
myList.sortInsertion1();
cout << "After sortInsertion1\n";
myList.display();
if (myList.isSorted())
cout << " List is SORTED\n";
else
cout << " List is NOT SORTED\n";
cout << "-------------------\n";
}
}
////////////////////////////////////////////////////////////
// getAt(int p)
////////////////////////////////////////////////////////////
int CSortedList::getAt(int p)
{
if ((p < m_count) && (p >= 0))
return this->m_array[p];
else
return UNDEFINED;
};
////////////////////////////////////////////////////////////
// getCount(void)
////////////////////////////////////////////////////////////
int CSortedList::getCount(void)
{
return this->m_count;
};
////////////////////////////////////////////////////////////
// CSortedList(int n)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(int n)
{
this->m_count = 0;
int x;
for (int i=0; i<n; i++)
{
x = rand()%(MAX_VALUE+1);
this->insert(x);
}
}
////////////////////////////////////////////////////////////
// remove(x)
////////////////////////////////////////////////////////////
/*
Algorithm0:
Search for x
if not found return false
put position of x in p
shiftLeft all values on right of p
return true
Algorithm1:
Search for x
if not found return false
put position of x in p
for i= p to count-2
array[i] = array[i+1]
end for
count--
return true
*/
bool CSortedList::remove(int x)
{
int p = searchSeq(x);
if (-1 == p)
return false;
//shift left starting at p+1
for (int i=p; i<=m_count-2; i++)
m_array[i] = m_array[i+1];
this->m_count--;
return true;
}
////////////////////////////////////////////////////////////
// testRemove()
////////////////////////////////////////////////////////////
void testRemove(void)
{
/*
TEST CASES0:
list with count=0
list with count=1, x is not in the list
list with count=1, x is in the list
list with count=2, x is not in the list
list with count=2, x is at 0 position
list with count=2, x is at count-1 position
list with count>2, x is not in the list
list with count>2, x is at 0 position
list with count>2, x is at count-1 position
list with count>2, x is at position [1..count-2]
-------------------------------------------------
TEST CASES1:
list with count=0
list with count=1, x is not in the list
list with count=1, x is in the list
list with count>1, x is not in the list
list with count>1, x is at 0 position
list with count>1, x is at count-1 position
list with count>2, x is at position [1..count-2]
*/
cout << "Case0: Random cases:\n\n";
for (int j=1; j<=5; j++)
{
CSortedList myList('r');
int x;
bool result;
myList.display();
for (int i=0; i<10; i++)
{
x = rand()%(MAX_VALUE+1);
result = myList.remove(x);
if (result)
cout << x << " was deleted from the list\n";
else
cout << x << " could not be deleted from the list\n";
myList.display();
cout << endl;
}
cout << "----------------------------------\n";
}
//list with count=0
{
cout << "Case1: //list with count=0\n\n";
CSortedList myList;
int x;
bool result;
myList.display();
x = rand()%(MAX_VALUE+1);
result = myList.remove(x);
if (result)
cout << x << " was deleted from the list\n\n";
else
cout << x << " could not be deleted from the list\n";
myList.display();
cout << "********************************" << endl;
}
//list with count=1, x is not in the list
{
cout << "Case2: //list with count=1, x is not in the list\n\n";
CSortedList myList(1);
int x = MAX_VALUE+1;
bool result;
myList.display();
result = myList.remove(x);
if (result)
cout << x << " was deleted from the list\n";
else
cout << x << " could not be deleted from the list\n";
myList.display();
cout << "********************************" << endl;
}
//list with count=1, x is in the list
{
cout << "Case3: //list with count=1, x is in the list\n\n";
CSortedList myList(1);
int x = myList.getAt(0);
bool result;
myList.display();
result = myList.remove(x);
if (result)
cout << x << " was deleted from the list\n";
else
cout << x << " could not be deleted from the list\n";
myList.display();
cout << "********************************" << endl;
}
//list with count>1, x is not in the list
{
cout << "Case4: //list with count>1, x is not in the list\n\n";
CSortedList myList(rand()%(ARRAY_SIZE-1) + 2);
int x = rand()%MAX_VALUE + MAX_VALUE + 1;
bool result;
myList.display();
result = myList.remove(x);
if (result)
cout << x << " was deleted from the list\n";
else
cout << x << " could not be deleted from the list\n";
myList.display();
cout << "********************************" << endl;
}
//list with count>1, x is at 0 position
{
cout << "Case5: //list with count>1, x is at 0 position\n\n";
CSortedList myList(rand()%(ARRAY_SIZE-1) + 2);
int x = myList.getAt(0);
bool result;
myList.display();
result = myList.remove(x);
if (result)
cout << x << " was deleted from the list\n";
else
cout << x << " could not be deleted from the list\n";
myList.display();
cout << "********************************" << endl;
}
//list with count>1, x is at count-1 position
{
cout << "Case6: //list with count>1, x is at count-1 position\n\n";
CSortedList myList(rand()%(ARRAY_SIZE-1) + 2);
int x = myList.getAt(myList.getCount()-1);
bool result;
myList.display();
result = myList.remove(x);
if (result)
cout << x << " was deleted from the list\n";
else
cout << x << " could not be deleted from the list\n";
myList.display();
cout << "********************************" << endl;
}
//list with count>2, x is at position [1..count-2]
{
cout << "Case7: //list with count>2, x is at position [1..count-2]\n\n";
CSortedList myList(rand()%(ARRAY_SIZE-1) + 2);
int p = 1 + rand()%(myList.getCount()-2);
int x = myList.getAt(p);
bool result;
myList.display();
result = myList.remove(x);
if (result)
cout << x << " was deleted from the list\n";
else
cout << x << " could not be deleted from the list\n";
myList.display();
cout << "********************************" << endl;
}
}
////////////////////////////////////////////////////////////
// displayDistinctWithCounts()
////////////////////////////////////////////////////////////
void CSortedList::displayDistinctWithCounts(void) const
{
int copies;
/*
for (int i=0; i<this->m_count; i++)
{
if (0==i)
copies = 1;
if ((i!=0) && (this->m_array[i] != this->m_array[i-1]))
{
cout << copies << ' ' << this->m_array[i-1] << endl;
copies = 1;
}
if ((i!=0) && (this->m_array[i] == this->m_array[i-1]))
copies++;
if (i == (this->m_count-1))
cout << copies << ' ' << this->m_array[i] << endl;
}
*/
/*
for (int i=0; i<this->m_count; i++)
{
if (0==i)
copies = 1;
else
{
if (this->m_array[i] != this->m_array[i-1])
{
cout << copies << ' ' << this->m_array[i-1] << endl;
copies = 1;
}
else
copies++;
}
if (i == (this->m_count-1))
cout << copies << ' ' << this->m_array[i] << endl;
}
*/
int total = 0;
for (int i=0; i<this->m_count; i++)
{
if (0==i)
copies = 1;
else if (this->m_array[i] != this->m_array[i-1])
{
cout << copies << ' ' << this->m_array[i-1] << endl;
total += copies;
copies = 1;
}
else
copies++;
if (i == (this->m_count-1))
{
cout << copies << ' ' << this->m_array[i] << endl;
total += copies;
}
}
cout << "Total = " << total << endl;
}
////////////////////////////////////////////////////////////
// testDisplayDistinctWithCounts()
////////////////////////////////////////////////////////////
void testDisplayDistinctWithCounts(void)
{
{
CSortedList myList;
myList.display();
myList.displayDistinctWithCounts();
cout << "-----------------\n";
}
for (int j=1; j<=TEST_COUNT; j++)
{
CSortedList myList('r');
myList.display();
myList.displayDistinctWithCounts();
cout << "-----------------\n";
}
}
////////////////////////////////////////////////////////////
// searchBinaryLM(x)
////////////////////////////////////////////////////////////
/*
Given sorted array[0..count-1], x
[12, 23, 23, 29, 32], 23 => 1
[12, 23, 27, 27, 32], 24 => 2
Algorithm0:
Find the position of x in p using binary search
if not found then return -1
while (value at p-1 is same as at p)
p--
end while
*/
int CSortedList::searchBinaryLM(int x) const
{
int p;
p = this->searchBinary(x);
if (-1 == p)
return -1;
while((p>0) && (this->m_array[p] == this->m_array[p-1]))
p--;
return p;
}
////////////////////////////////////////////////////////////
// testSearchBinaryLM
////////////////////////////////////////////////////////////
void testSearchBinaryLM(void)
{
for (int j=1; j<=5; j++)
{
CSortedList myList('r');
int x, p1, p2;
myList.display();
for (int i=0; i<10; i++)
{
x = rand()%(MAX_VALUE+1);
p1 = myList.searchBinaryLM(x);
cout << x << " was found at position " << p1 << endl;
p2 = myList.searchSeq(x);
cout << x << " was found at position " << p2 << endl;
if (p1 != p2)
cout << "***************************\n";
cout << endl;
}
cout << "-----------------\n";
}
}
////////////////////////////////////////////////////////////
// searchBinary(x)
////////////////////////////////////////////////////////////
/*
Given sorted array[0..count-1], x
[12, 23, 27, 29, 32], 27 => 2
[12, 23, 27, 29, 32], 24 => -1
Algorithm0:
while there is a list to be searched
calculate mid point of the list to be searched
if x = array[mid] then return mid
find out which half of the list to be searched
end while
*/
int CSortedList::searchBinary(int x) const
{
int lower, upper, mid;
lower = 0;
upper = this->m_count-1;
while (lower <= upper)
{
mid = (lower+upper)/2;
if (x == this->m_array[mid])
return mid;
if (x < this->m_array[mid])
upper = mid-1;
if (x > this->m_array[mid])
lower = mid+1;
}
return -1;
}
////////////////////////////////////////////////////////////
// testSearchBinary
////////////////////////////////////////////////////////////
void testSearchBinary(void)
{
for (int j=1; j<=5; j++)
{
CSortedList myList('r');
int x, p;
myList.display();
for (int i=0; i<10; i++)
{
x = rand()%(MAX_VALUE+1);
p = myList.searchBinary(x);
cout << x << " was found at position " << p << endl;
p = myList.searchSeq(x);
cout << x << " was found at position " << p << endl;
}
cout << "-----------------\n";
}
}
////////////////////////////////////////////////////////////
// searchSeq(x)
////////////////////////////////////////////////////////////
/*Given sorted array[0..count-1], x
[12, 23, 27, 29, 32], 27 => 2
[12, 23, 27, 29, 32], 24 => -1
Algorithm0:
search for x from left to right in array[]
if found return the position
return -1
Algorithm1:
for i=0 to count-1 do the following
if x = array[i] then return i
end for
return -1
Algorithm2:
for i=0 to count-1 do the following
if x = array[i] then return i
if x < array[i] then exit for loop
end for
return -1
*/
int CSortedList::searchSeq(int x) const
{
for (int i=0; i<=this->m_count-1; i++)
{
if (x == m_array[i])
return i;
if (x < this->m_array[i])
break;
}
return -1;
}
////////////////////////////////////////////////////////////
// testSearchSeq
////////////////////////////////////////////////////////////
void testSearchSeq(void)
{
for (int j=1; j<=5; j++)
{
CSortedList myList('r');
int x, p;
myList.display();
for (int i=0; i<10; i++)
{
x = rand()%(MAX_VALUE+1);
p = myList.searchSeq(x);
cout << x << " was found at position " << p << endl;
}
cout << "-----------------\n";
}
}
////////////////////////////////////////////////////////////
// CSortedList(void)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(void)
{
this->m_count = 0;
this->m_min = UNDEFINED;
this->m_max = UNDEFINED;
}
////////////////////////////////////////////////////////////
// CSortedList(char ch)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(char ch)
{
this->m_count = 0;
int x, n;
if ('r' == ch)
{
n = rand()%ARRAY_SIZE+1;
for (int i=0; i<n; i++)
{
x = rand()%(MAX_VALUE+1);
this->insert(x);
}
}
}
////////////////////////////////////////////////////////////
// display(void)
////////////////////////////////////////////////////////////
void CSortedList::display(void) const
{
cout << "SortedList(" << this->m_count << ")= ";
for (int i=0; i<this->m_count; i++)
cout << this->m_array[i] << ' ';
cout << endl;
}
////////////////////////////////////////////////////////////
// insert(int x)
////////////////////////////////////////////////////////////
bool CSortedList::insert(int x)
{
//allow duplicate values
/*
there is no room then return false
there is room then add to the end, sort, return true
*/
if (ARRAY_SIZE == this->m_count)
return false;
else
{
this->m_array[m_count] = x;
this->m_count++;
this->sortInsertion1();
return true;
}
}
////////////////////////////////////////////////////////////
// sortBubble1(void)
////////////////////////////////////////////////////////////
void CSortedList::sortBubble1(void)
{
int j;
for (int i=1; i<=this->m_count-1; i++)
{
for (j=0; j<=this->m_count-2; j++)
{
if (this->m_array[j] > this->m_array[j+1])
{
int temp = this->m_array[j];
this->m_array[j] = this->m_array[j+1];
this->m_array[j+1] = temp;
}
}
}
}
////////////////////////////////////////////////////////////
// sortBubble2(void)
////////////////////////////////////////////////////////////
/*
Algorithm0:
do
swaps =0
make one pass trying to put items in order
until swaps == 0
Algorithm1:
sorted = false
while not sorted
sorted = true
make one pass trying to put items in order
end while
Algorithm2:
sorted = false
while not sorted
sorted = true
for i= 0 to m_count-2 do the following
if m_array[i] > m_array[i+1] then
swap m_array[i], m_array[i+1]
sorted = false
end if
end for
end while
*/
void CSortedList::sortBubble2(void)
{
int i, temp;
bool sorted = false;
while (!sorted)
{
sorted = true;
for (i= 0; i<=m_count-2; i++)
{
if (m_array[i] > m_array[i+1])
{
temp = m_array[i];
m_array[i] = m_array[i+1];
m_array[i+1] = temp;
sorted = false;
}
} //end for
}//end while
}
////////////////////////////////////////////////////////////
// testSortBubble2(void)
////////////////////////////////////////////////////////////
void testSortBubble2(void)
{
for (int i=1; i<=10; i++)
{
CSortedList myList('r');
cout << "Original list\n";
myList.display();
if (myList.isSorted())
cout << " List is SORTED\n";
else
cout << " List is NOT SORTED\n";
myList.shuffle();
cout << "Shuffled list\n";
myList.display();
if (myList.isSorted())
cout << " List is SORTED\n";
else
cout << " List is NOT SORTED\n";
myList.sortBubble2();
cout << "After sortBubble2\n";
myList.display();
if (myList.isSorted())
cout << " List is SORTED\n";
else
cout << " List is NOT SORTED\n";
cout << "-------------------\n";
}
}
////////////////////////////////////////////////////////////
// isSorted(void)
////////////////////////////////////////////////////////////
bool CSortedList::isSorted(void) const
{
for (int i=0; i<=this->m_count-2; i++)
if (this->m_array[i] > this->m_array[i+1])
return false;
return true;
}
////////////////////////////////////////////////////////////
// shuffle(void)
////////////////////////////////////////////////////////////
void CSortedList::shuffle(void)
{
int picked, temp;
for (int i=0; i<=this->m_count-1; i++)
{
picked = rand()%this->m_count;
temp = this->m_array[0];
this->m_array[0] = this->m_array[picked];
this->m_array[picked] = temp;
}
}
/*
SAMPLE RUN:
SortedList(0)=
Total = 0
-----------------
SortedList(5)= 2 2 4 5 5
2 2
1 4
2 5
Total = 5
-----------------
SortedList(7)= 1 1 3 4 5 5 5
2 1
1 3
1 4
3 5
Total = 7
-----------------
SortedList(3)= 2 3 5
1 2
1 3
1 5
Total = 3
-----------------
SortedList(10)= 0 0 0 1 2 2 3 4 5 5
3 0
1 1
2 2
1 3
1 4
2 5
Total = 10
-----------------
SortedList(8)= 1 2 3 4 4 5 5 5
1 1
1 2
1 3
2 4
3 5
Total = 8
-----------------
SortedList(5)= 0 2 2 4 5
1 0
2 2
1 4
1 5
Total = 5
-----------------
SortedList(7)= 0 0 0 1 2 2 3
3 0
1 1
2 2
1 3
Total = 7
-----------------
SortedList(2)= 4 4
2 4
Total = 2
-----------------
SortedList(8)= 1 2 2 3 4 4 5 5
1 1
2 2
1 3
2 4
2 5
Total = 8
-----------------
SortedList(4)= 0 1 2 5
1 0
1 1
1 2
1 5
Total = 4
-----------------
SortedList(2)= 0 0
2 0
Total = 2
-----------------
SortedList(2)= 0 2
1 0
1 2
Total = 2
-----------------
SortedList(7)= 0 0 1 1 1 4 5
2 0
3 1
1 4
1 5
Total = 7
-----------------
SortedList(3)= 0 1 2
1 0
1 1
1 2
Total = 3
-----------------
SortedList(7)= 0 0 1 2 2 3 4
2 0
1 1
2 2
1 3
1 4
Total = 7
-----------------
SortedList(4)= 2 2 4 5
2 2
1 4
1 5
Total = 4
-----------------
SortedList(5)= 0 1 3 4 5
1 0
1 1
1 3
1 4
1 5
Total = 5
-----------------
SortedList(2)= 0 2
1 0
1 2
Total = 2
-----------------
SortedList(9)= 0 1 2 3 3 3 4 4 5
1 0
1 1
1 2
3 3
2 4
1 5
Total = 9
-----------------
SortedList(5)= 1 2 2 3 4
1 1
2 2
1 3
1 4
Total = 5
-----------------
Press any key to continue
*/
|