NOB_List05
[ Home ] [ Up ]

//Date:   2003.09.15
//File:   NOB_List05.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 testShuffle(void);
void populate(int a[], int n);
void sortBubble(int a[], int n);
void testSortBubble(void);


void testInsert(void);


void main(void)
  {
  srand(time(NULL));
  //testInsert();
  //testShuffle();
  testSortBubble();
  }


/*
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 testSortBubble(void)
  {
  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 << "After sortBubble\n";
    sortBubble(values, n);
    display(values, n);

    cout << "*****************\n";

    }
  }


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

  }

void testShuffle(void)
  {
  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";

    }
  }


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


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