//sortedList04.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 array[ARRAY_SIZE];
int count;
int min;
int 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)
{
count = 0;
min = UNDEFINED;
max = UNDEFINED;
}
////////////////////////////////////////////////////////////
// CSortedList(char ch)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(char ch)
{
count = 0;
int x, n;
if ('r' == ch)
{
n = rand()%ARRAY_SIZE+1;
for (int i=0; i<n; i++)
{
x = rand()%100;
insert(x);
}
}
}
////////////////////////////////////////////////////////////
// display(void)
////////////////////////////////////////////////////////////
void CSortedList::display(void)
{
cout << "SortedList(" << count << ")= ";
for (int i=0; i<count; i++)
cout << 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 == count)
return false;
else
{
array[count] = x;
count++;
sortBubble1();
return true;
}
}
////////////////////////////////////////////////////////////
// sortBubble1(void)
////////////////////////////////////////////////////////////
void CSortedList::sortBubble1(void)
{
int j;
for (int i=1; i<=count-1; i++)
{
for (j=0; j<=count-2; j++)
{
if (array[j] > array[j+1])
{
int temp = array[j];
array[j] = array[j+1];
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 count-2 do the following
if array[i] > array[i+1] then
swap array[i], 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)
{
}
////////////////////////////////////////////////////////////
// shuffle(void)
////////////////////////////////////////////////////////////
void CSortedList::shuffle(void)
{
int picked, temp;
for (int i=0; i<=this->count-1; i++)
{
picked = rand()%this->count;
temp = array[0];
array[0] = array[picked];
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
*/
|