NOB_List04
[ Home ] [ Up ]

//Date:   2003.09.12
//File:   NOB_List04.cpp
//Author: AOU

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


/*
maintain an ordered list of integeres
*/

const int MAX_SIZE = 25;
const int TEST_COUNT = 19;
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 shuffle(int a[], int n);


void testInsert(void);


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


/*Algorithm

a[]={12, 14, 20, 21];

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

  }


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


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

  cout << endl;
  }