//sortedList05.cpp
//date: 09/16/2002
//author: AOU
//Assignment #2
//Date assigned 9/13/2002
//Date due 9/20/2002
//Implement sortBubble2
//Algorithm and Implementation for isSorted
//Supply detailed documentation for each member function
//Test functions will be supplied and published
////////////////////////////////////////////////////////////
// Include files
////////////////////////////////////////////////////////////
#include<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
////////////////////////////////////////////////////////////
// Constants
////////////////////////////////////////////////////////////
const int ARRAY_SIZE = 10;
const int UNDEFINED = -9999;
////////////////////////////////////////////////////////////
// Test function prototypes
////////////////////////////////////////////////////////////
void testSortBubble2(void);
////////////////////////////////////////////////////////////
// Class CSortedList
////////////////////////////////////////////////////////////
class CSortedList
{
private:
int m_array[ARRAY_SIZE];
int m_count;
int m_min;
int m_max;
void sortBubble1(void);
public:
CSortedList(void);
CSortedList(char ch);
void display(void);
bool insert(int x);
bool isSorted(void);
void sortBubble2(void);
void shuffle(void);
};
////////////////////////////////////////////////////////////
// main function
////////////////////////////////////////////////////////////
void main(void)
{
srand(time(NULL));
testSortBubble2();
}
////////////////////////////////////////////////////////////
// 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()%100;
this->insert(x);// or (*this).insert();
}
}
}
////////////////////////////////////////////////////////////
// display(void)
////////////////////////////////////////////////////////////
void CSortedList::display(void)
{
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->sortBubble1();
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)
{
}
////////////////////////////////////////////////////////////
// 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)
{
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:
Original list
SortedList(7)= 7 37 37 48 65 84 98
List is SORTED
Shuffled list
SortedList(7)= 65 37 7 48 37 84 98
List is NOT SORTED
After sortBubble2
SortedList(7)= 7 37 37 48 65 84 98
List is SORTED
-------------------
Original list
SortedList(4)= 7 23 32 90
List is SORTED
Shuffled list
SortedList(4)= 32 23 7 90
List is NOT SORTED
After sortBubble2
SortedList(4)= 7 23 32 90
List is SORTED
-------------------
Original list
SortedList(2)= 36 98
List is SORTED
Shuffled list
SortedList(2)= 36 98
List is SORTED
After sortBubble2
SortedList(2)= 36 98
List is SORTED
-------------------
Original list
SortedList(6)= 4 14 42 64 74 89
List is SORTED
Shuffled list
SortedList(6)= 89 42 14 64 74 4
List is NOT SORTED
After sortBubble2
SortedList(6)= 4 14 42 64 74 89
List is SORTED
-------------------
Original list
SortedList(3)= 11 28 74
List is SORTED
Shuffled list
SortedList(3)= 74 28 11
List is NOT SORTED
After sortBubble2
SortedList(3)= 11 28 74
List is SORTED
-------------------
Original list
SortedList(2)= 31 43
List is SORTED
Shuffled list
SortedList(2)= 43 31
List is NOT SORTED
After sortBubble2
SortedList(2)= 31 43
List is SORTED
-------------------
Original list
SortedList(4)= 1 27 36 56
List is SORTED
Shuffled list
SortedList(4)= 27 36 1 56
List is NOT SORTED
After sortBubble2
SortedList(4)= 1 27 36 56
List is SORTED
-------------------
Original list
SortedList(1)= 68
List is SORTED
Shuffled list
SortedList(1)= 68
List is SORTED
After sortBubble2
SortedList(1)= 68
List is SORTED
-------------------
Original list
SortedList(10)= 10 13 36 42 59 62 76 76 85 89
List is SORTED
Shuffled list
SortedList(10)= 76 13 10 89 76 62 42 85 59 36
List is NOT SORTED
After sortBubble2
SortedList(10)= 10 13 36 42 59 62 76 76 85 89
List is SORTED
-------------------
Original list
SortedList(1)= 43
List is SORTED
Shuffled list
SortedList(1)= 43
List is SORTED
After sortBubble2
SortedList(1)= 43
List is SORTED
-------------------
Press any key to continue
*/
|