//sortedList18.cpp
//date: 10/25/2002
//author: AOU
////////////////////////////////////////////////////////////
// Include files
////////////////////////////////////////////////////////////
#include<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
////////////////////////////////////////////////////////////
// Constants
////////////////////////////////////////////////////////////
const int ARRAY_SIZE = 10;
const int UNDEFINED = -9999;
const int MAX_VALUE = 5;
const int TEST_COUNT = 20;
////////////////////////////////////////////////////////////
// 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);
////////////////////////////////////////////////////////////
// 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
};
////////////////////////////////////////////////////////////
// main function
////////////////////////////////////////////////////////////
void main(void)
{
srand(time(NULL));
//testSortBubble2();
//testSearchSeq();
//testSearchBinary();
//testSearchBinaryLM();
//testRemove();
//testSortInsertion1();
//testAssignOperator();
//testInsertionOperator();
//testNotEqualOperator();
//testAdd();
//testSub();
//testIsEmpty();
//testDisplayDistinct();
testDisplayDistinctWithCounts();
}
////////////////////////////////////////////////////////////
// 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}
cList.m_count = aList.m_count + bList.m_count;
cout << "NOT IMPLEMENTED\n";
}
////////////////////////////////////////////////////////////
// testAdd
////////////////////////////////////////////////////////////
void testAdd(void)
{
cout << "testAdd\n";
cout << "-------\n";
int m1 = rand()%(ARRAY_SIZE/2);
int m2 = rand()%(ARRAY_SIZE/2);
for (int i=0; i<TEST_COUNT; i++)
{
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}
cout << "NOT IMPLEMENTED\n";
}
////////////////////////////////////////////////////////////
// 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
*/
|