NOB_List03
[ Home ] [ Up ]

//Date: 2003.09.10
//File: NOB_List03.cpp
//Author: AOU

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

/*
Assignment 01:
Write a algorithm to test if the values in array a[] are sorted.
Develop and test the function based on the algorithm.
Prototype of the function is
  bool isSorted(int a[], int n);
Print the algorithm and the function on one page and submit it.
*/

/*
maintain an ordered list of integeres
*/

const int MAX_SIZE = 189;
const int TEST_COUNT = 200;
const int MAX_VALUE = 15;


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 testInsert(void);


void main(void)
{
srand(time(NULL));
testInsert();
}


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);
}
}

/*
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] = 0;
}


void display(int a[], int n)
{
cout << "a[" << n << "]: ";
for (int i=0; i<=n-1; i++)
cout << a[i] << ' ';

cout << endl;
}