//Date: 2003.09.15
//File: NOB_List06.cpp
//Author: AOU
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
/*
project 01: 09/17/2003 - 09/24/2003
implement the following fnctions with
corresponding test functions:
bool deleteAtPos(int a[], int &n, int p);
int deleteDupes(int a[], int &n)
Submit the following (on paper and disk)
for each function:
5 description
5 examples (2)
5 algorithm
5 properly indented function
5 properly indented test function
5 properly labeled output
*/
/*
maintain an ordered list of integeres
*/
////////////////////////////////////////
//constants
////////////////////////////////////////
const int MAX_SIZE = 25;
const int TEST_COUNT = 19;
const int MAX_VALUE = 15;
const int UNDEFINED = -911;
////////////////////////////////////////
//prototypes
////////////////////////////////////////
void display(int a[], int n);
void initialize(int a[], int n);
bool insert(int a[], int &n, int x);
void swap(int &x, int &y);
bool isSorted(int a[], int n);
void shuffle(int a[], int n);
void testShuffle(void);
void populate(int a[], int n);
void sortBubble(int a[], int n);
void testSortBubble(void);
void testInsert(void);
////////////////////////////////////////
//main
////////////////////////////////////////
void main(void)
{
srand(time(NULL));
testInsert();
testShuffle();
testSortBubble();
}
////////////////////////////////////////
//testSortBubble
////////////////////////////////////////
void testSortBubble(void)
{
cout << "++++++++++++++\n";
cout << "testSortBubble\n";
cout << "++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
int values[MAX_SIZE];
initialize(values, MAX_SIZE);
int n = rand()%(MAX_SIZE+1);
populate(values, n);
cout << "Original list\n";
display(values, n);
shuffle(values, n);
cout << "After shuffle\n";
display(values, n);
cout << "After sortBubble\n";
sortBubble(values, n);
display(values, n);
cout << "*****************\n";
}
}
////////////////////////////////////////
//sortBubble
////////////////////////////////////////
/*
Description:
Puts the values in increasing order by using
the bubble sort method
Example:
[23, 13, 67, 12] => [12, 13, 23, 67]
Algorithm:
do
swaps = 0
from i=0 to n-2
if a[i] > a[i+1] then
swap (a[i], a[i+1])
swaps++
end if
end loop
until swps = 0
*/
void sortBubble(int a[], int n)
{
int swaps;
do
{
swaps = 0;
for (int i=0; i<=n-2; i++)
if (a[i] > a[i+1])
{
swap(a[i], a[i+1]);
swaps++;
}
} while (swaps!=0);
}
////////////////////////////////////////
//testShuffle
////////////////////////////////////////
void testShuffle(void)
{
cout << "+++++++++++\n";
cout << "testShuffle\n";
cout << "+++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
int values[MAX_SIZE];
initialize(values, MAX_SIZE);
int n = rand()%(MAX_SIZE+1);
populate(values, n);
display(values, n);
shuffle(values, n);
cout << "After shuffle\n";
display(values, n);
cout << "*****************\n";
}
}
////////////////////////////////////////
//populate
////////////////////////////////////////
void populate(int a[], int n)
{
int m=0;
for (int i=1; i<=n; i++)
{
int x = rand()%(MAX_VALUE+1);
insert(a, m, x);
}
}
////////////////////////////////////////
//shuffle
////////////////////////////////////////
/*
Description:
Examples:
a[]={12, 14, 20, 21];
Algorithm:
do the following n*n time
pick a number in pick randomly between 0 and n-1
swap a[0] with a[pick]
*/
void shuffle(int a[], int n)
{
for (int i=1; i<=n*n; i++)
{
int pick = rand()%n;
swap (a[0], a[pick]);
}
}
////////////////////////////////////////
//isSorted
////////////////////////////////////////
/*
Description:
Examples:
Algorithm:
*/
bool isSorted(int a[], int n)
{
for (int i=0; i<=n-2; i++)
if (a[i] > a[i+1])
return false;
return true;
}
////////////////////////////////////////
////////////////////////////////////////
void swap(int &x, int &y)
{
if (x != y)
{
int temp = x;
x = y;
y = temp;
}
}
void testInsert(void)
{
int values[MAX_SIZE];
initialize(values, MAX_SIZE);
int n = 0;
for (int c=1; c<=TEST_COUNT; c++)
{
int x = rand()%(MAX_VALUE+1);
bool result = insert(values, n, x);
if (result == true)
cout << "Insertion of " << x << " was a success\n";
else
cout << "Insertion of " << x << " was NOT a success\n";
display(values, n);
if (isSorted(values, n) == true)
cout << "List is sorted\n";
else
cout << "List is NOT sorted\n";
int p1 = rand()%n;
int p2 = rand()%n;
swap(values[p1], values[p2]);
display(values, n);
if (isSorted(values, n) == true)
cout << "List is sorted\n";
else
cout << "List is NOT sorted\n";
swap(values[p1], values[p2]);
display(values, n);
cout << "***********************\n";
}
}
/*
insert x in a[]
Cases:
if n = 0 then ...
if n = MAX_SIZE then ...
if n > 0 then
a[n] = x
n++
for i=n-1 to 1 step -1
if a[i] >= a[i-1] then get out of the for loop/function
swap(a[i], a[i-1])
end for
end if
*/
bool insert(int a[], int &n, int x)
{
if (0 == n)
{
a[n] = x;
n++;
return true;
};
if (MAX_SIZE == n)
return false;
if (n > 0)
{
a[n] = x;
n++;
for (int i=n-1; i>=1; i--)
{
if (a[i] >= a[i-1]) return true;
swap(a[i], a[i-1]);
}
return true;
}
return false;
}
void initialize(int a[], int n)
{
for (int i=0; i<=n-1; i++)
a[i] = UNDEFINED;
}
void display(int a[], int n)
{
cout << "a[" << n << "]: ";
for (int i=0; i<=n-1; i++)
cout << a[i] << ' ';
cout << endl;
}
/*
SAMPLE RUN:
Insertion of 10 was a success
a[1]: 10
List is sorted
a[1]: 10
List is sorted
a[1]: 10
***********************
Insertion of 8 was a success
a[2]: 8 10
List is sorted
a[2]: 10 8
List is NOT sorted
a[2]: 8 10
***********************
Insertion of 15 was a success
a[3]: 8 10 15
List is sorted
a[3]: 8 15 10
List is NOT sorted
a[3]: 8 10 15
***********************
Insertion of 14 was a success
a[4]: 8 10 14 15
List is sorted
a[4]: 14 10 8 15
List is NOT sorted
a[4]: 8 10 14 15
***********************
Insertion of 9 was a success
a[5]: 8 9 10 14 15
List is sorted
a[5]: 14 9 10 8 15
List is NOT sorted
a[5]: 8 9 10 14 15
***********************
Insertion of 4 was a success
a[6]: 4 8 9 10 14 15
List is sorted
a[6]: 4 8 9 10 14 15
List is sorted
a[6]: 4 8 9 10 14 15
***********************
Insertion of 0 was a success
a[7]: 0 4 8 9 10 14 15
List is sorted
a[7]: 9 4 8 0 10 14 15
List is NOT sorted
a[7]: 0 4 8 9 10 14 15
***********************
Insertion of 3 was a success
a[8]: 0 3 4 8 9 10 14 15
List is sorted
a[8]: 4 3 0 8 9 10 14 15
List is NOT sorted
a[8]: 0 3 4 8 9 10 14 15
***********************
Insertion of 14 was a success
a[9]: 0 3 4 8 9 10 14 14 15
List is sorted
a[9]: 4 3 0 8 9 10 14 14 15
List is NOT sorted
a[9]: 0 3 4 8 9 10 14 14 15
***********************
Insertion of 0 was a success
a[10]: 0 0 3 4 8 9 10 14 14 15
List is sorted
a[10]: 0 0 3 15 8 9 10 14 14 4
List is NOT sorted
a[10]: 0 0 3 4 8 9 10 14 14 15
***********************
Insertion of 6 was a success
a[11]: 0 0 3 4 6 8 9 10 14 14 15
List is sorted
a[11]: 3 0 0 4 6 8 9 10 14 14 15
List is NOT sorted
a[11]: 0 0 3 4 6 8 9 10 14 14 15
***********************
Insertion of 14 was a success
a[12]: 0 0 3 4 6 8 9 10 14 14 14 15
List is sorted
a[12]: 0 0 3 14 6 8 9 10 4 14 14 15
List is NOT sorted
a[12]: 0 0 3 4 6 8 9 10 14 14 14 15
***********************
Insertion of 10 was a success
a[13]: 0 0 3 4 6 8 9 10 10 14 14 14 15
List is sorted
a[13]: 0 0 3 10 6 8 9 10 4 14 14 14 15
List is NOT sorted
a[13]: 0 0 3 4 6 8 9 10 10 14 14 14 15
***********************
Insertion of 3 was a success
a[14]: 0 0 3 3 4 6 8 9 10 10 14 14 14 15
List is sorted
a[14]: 0 0 3 3 4 6 10 9 8 10 14 14 14 15
List is NOT sorted
a[14]: 0 0 3 3 4 6 8 9 10 10 14 14 14 15
***********************
Insertion of 11 was a success
a[15]: 0 0 3 3 4 6 8 9 10 10 11 14 14 14 15
List is sorted
a[15]: 3 0 3 0 4 6 8 9 10 10 11 14 14 14 15
List is NOT sorted
a[15]: 0 0 3 3 4 6 8 9 10 10 11 14 14 14 15
***********************
Insertion of 12 was a success
a[16]: 0 0 3 3 4 6 8 9 10 10 11 12 14 14 14 15
List is sorted
a[16]: 0 8 3 3 4 6 0 9 10 10 11 12 14 14 14 15
List is NOT sorted
a[16]: 0 0 3 3 4 6 8 9 10 10 11 12 14 14 14 15
***********************
Insertion of 15 was a success
a[17]: 0 0 3 3 4 6 8 9 10 10 11 12 14 14 14 15 15
List is sorted
a[17]: 0 0 3 3 4 6 8 9 10 10 11 14 14 12 14 15 15
List is NOT sorted
a[17]: 0 0 3 3 4 6 8 9 10 10 11 12 14 14 14 15 15
***********************
Insertion of 10 was a success
a[18]: 0 0 3 3 4 6 8 9 10 10 10 11 12 14 14 14 15 15
List is sorted
a[18]: 0 0 3 3 4 6 15 9 10 10 10 11 12 14 14 14 8 15
List is NOT sorted
a[18]: 0 0 3 3 4 6 8 9 10 10 10 11 12 14 14 14 15 15
***********************
Insertion of 14 was a success
a[19]: 0 0 3 3 4 6 8 9 10 10 10 11 12 14 14 14 14 15 15
List is sorted
a[19]: 0 0 3 3 4 14 8 9 10 10 10 11 12 14 14 6 14 15 15
List is NOT sorted
a[19]: 0 0 3 3 4 6 8 9 10 10 10 11 12 14 14 14 14 15 15
***********************
+++++++++++
testShuffle
+++++++++++
a[19]: 0 2 2 4 6 6 6 8 9 9 10 11 12 12 12 14 15 15 15
After shuffle
a[19]: 15 8 6 6 12 12 0 12 15 6 9 4 10 11 15 9 2 2 14
*****************
a[16]: 0 1 2 2 2 4 5 5 7 8 8 11 14 15 15 15
After shuffle
a[16]: 5 4 11 5 2 15 1 7 2 0 15 8 2 15 8 14
*****************
a[23]: 1 2 3 3 4 6 7 7 8 9 9 10 10 10 11 11 12 13 13 14 14 14 14
After shuffle
a[23]: 10 2 4 9 14 13 14 6 3 7 10 9 7 8 11 11 14 10 1 13 14 3 12
*****************
a[23]: 0 2 2 3 3 5 5 5 5 7 7 9 9 10 10 11 11 11 11 13 14 15 15
After shuffle
a[23]: 11 7 5 7 2 11 5 10 3 9 15 0 5 3 2 14 15 13 11 5 10 11 9
*****************
a[23]: 0 1 1 2 2 2 3 4 5 5 6 7 7 8 8 9 9 10 11 11 12 14 14
After shuffle
a[23]: 11 6 4 11 2 5 3 7 1 7 12 8 14 14 5 0 8 2 9 9 1 10 2
*****************
a[4]: 0 2 8 13
After shuffle
a[4]: 13 0 2 8
*****************
a[10]: 1 2 3 3 3 4 4 5 5 15
After shuffle
a[10]: 2 4 5 3 15 4 5 3 3 1
*****************
a[4]: 0 3 4 9
After shuffle
a[4]: 0 3 4 9
*****************
a[7]: 1 6 7 8 12 12 13
After shuffle
a[7]: 8 7 12 13 12 1 6
*****************
a[13]: 0 1 4 5 8 8 9 12 13 13 13 14 14
After shuffle
a[13]: 5 8 9 14 1 0 13 8 4 13 14 13 12
*****************
a[14]: 0 1 3 6 6 6 6 9 9 9 12 13 15 15
After shuffle
a[14]: 6 1 15 6 13 0 6 3 9 9 9 6 15 12
*****************
a[17]: 0 1 2 3 4 5 5 6 7 9 11 13 14 14 14 14 15
After shuffle
a[17]: 14 6 1 14 7 14 13 3 4 0 14 2 5 9 11 5 15
*****************
a[10]: 0 0 0 3 3 4 10 12 12 14
After shuffle
a[10]: 0 12 0 10 14 4 3 0 3 12
*****************
a[21]: 0 1 1 1 2 2 6 6 7 8 9 9 9 9 12 13 14 14 15 15 15
After shuffle
a[21]: 6 15 9 2 6 7 9 9 15 1 14 13 14 1 8 9 2 1 15 0 12
*****************
a[12]: 0 0 0 1 5 6 7 8 8 8 8 11
After shuffle
a[12]: 5 6 8 11 0 8 8 0 1 7 8 0
*****************
a[10]: 0 1 3 3 4 4 11 12 12 15
After shuffle
a[10]: 3 12 12 4 4 15 1 0 11 3
*****************
a[2]: 2 4
After shuffle
a[2]: 2 4
*****************
a[5]: 0 4 6 6 6
After shuffle
a[5]: 0 6 6 6 4
*****************
a[17]: 0 0 1 2 4 7 8 9 9 10 10 11 12 13 14 15 15
After shuffle
a[17]: 0 10 10 13 12 7 1 15 2 11 9 9 4 0 15 8 14
*****************
++++++++++++++
testSortBubble
++++++++++++++
Original list
a[23]: 0 1 1 2 2 3 3 4 5 5 6 7 9 10 13 13 13 13 13 14 14 14 14
After shuffle
a[23]: 4 2 7 6 1 14 13 13 14 5 5 13 2 3 9 14 13 3 1 0 13 10 14
After sortBubble
a[23]: 0 1 1 2 2 3 3 4 5 5 6 7 9 10 13 13 13 13 13 14 14 14 14
*****************
Original list
a[1]: 11
After shuffle
a[1]: 11
After sortBubble
a[1]: 11
*****************
Original list
a[6]: 1 2 3 7 9 15
After shuffle
a[6]: 15 7 2 9 1 3
After sortBubble
a[6]: 1 2 3 7 9 15
*****************
Original list
a[12]: 1 2 3 4 4 5 6 7 8 11 11 14
After shuffle
a[12]: 8 4 1 11 7 2 14 6 4 3 11 5
After sortBubble
a[12]: 1 2 3 4 4 5 6 7 8 11 11 14
*****************
Original list
a[24]: 0 2 3 5 8 8 8 9 9 9 10 11 13 13 13 14 14 14 14 14 14 14 15 15
After shuffle
a[24]: 15 3 14 14 9 14 11 14 8 10 15 13 14 13 14 9 8 14 5 9 2 0 8 13
After sortBubble
a[24]: 0 2 3 5 8 8 8 9 9 9 10 11 13 13 13 14 14 14 14 14 14 14 15 15
*****************
Original list
a[22]: 0 1 2 2 2 3 4 5 5 5 6 9 9 10 11 11 11 12 12 13 14 14
After shuffle
a[22]: 14 9 13 5 4 11 6 12 9 2 2 3 2 10 14 0 12 11 1 5 11 5
After sortBubble
a[22]: 0 1 2 2 2 3 4 5 5 5 6 9 9 10 11 11 11 12 12 13 14 14
*****************
Original list
a[7]: 2 3 3 8 10 11 13
After shuffle
a[7]: 2 3 13 8 11 10 3
After sortBubble
a[7]: 2 3 3 8 10 11 13
*****************
Original list
a[9]: 1 1 6 7 8 9 12 12 12
After shuffle
a[9]: 12 7 12 1 1 6 8 12 9
After sortBubble
a[9]: 1 1 6 7 8 9 12 12 12
*****************
Original list
a[3]: 6 11 13
After shuffle
a[3]: 13 6 11
After sortBubble
a[3]: 6 11 13
*****************
Original list
a[4]: 2 5 8 12
After shuffle
a[4]: 8 5 2 12
After sortBubble
a[4]: 2 5 8 12
*****************
Original list
a[13]: 1 6 8 8 9 10 10 10 11 12 12 12 14
After shuffle
a[13]: 8 10 11 9 14 12 10 10 1 8 12 12 6
After sortBubble
a[13]: 1 6 8 8 9 10 10 10 11 12 12 12 14
*****************
Original list
a[6]: 0 1 4 12 12 13
After shuffle
a[6]: 13 0 1 12 4 12
After sortBubble
a[6]: 0 1 4 12 12 13
*****************
Original list
a[23]: 0 1 1 3 4 5 5 5 6 8 8 9 9 9 10 11 12 12 13 14 14 14 15
After shuffle
a[23]: 1 12 8 9 9 4 12 14 5 10 14 5 11 15 1 8 13 0 14 9 6 5 3
After sortBubble
a[23]: 0 1 1 3 4 5 5 5 6 8 8 9 9 9 10 11 12 12 13 14 14 14 15
*****************
Original list
a[0]:
After shuffle
a[0]:
After sortBubble
a[0]:
*****************
Original list
a[4]: 2 3 5 5
After shuffle
a[4]: 5 2 5 3
After sortBubble
a[4]: 2 3 5 5
*****************
Original list
a[13]: 1 2 3 5 7 7 9 9 10 10 12 12 15
After shuffle
a[13]: 10 3 1 12 9 5 15 7 7 9 12 2 10
After sortBubble
a[13]: 1 2 3 5 7 7 9 9 10 10 12 12 15
*****************
Original list
a[5]: 3 8 10 11 14
After shuffle
a[5]: 10 3 14 11 8
After sortBubble
a[5]: 3 8 10 11 14
*****************
Original list
a[21]: 0 0 2 3 3 3 3 3 5 5 7 7 7 9 9 10 10 11 11 13 15
After shuffle
a[21]: 3 9 3 0 11 15 3 10 9 5 7 10 7 0 13 3 11 3 5 7 2
After sortBubble
a[21]: 0 0 2 3 3 3 3 3 5 5 7 7 7 9 9 10 10 11 11 13 15
*****************
Original list
a[14]: 0 0 0 1 2 3 5 5 7 9 13 13 14 15
After shuffle
a[14]: 7 14 15 5 0 1 5 0 9 3 13 2 13 0
After sortBubble
a[14]: 0 0 0 1 2 3 5 5 7 9 13 13 14 15
*****************
*/
|