SortedList03
[ Home ] [ Up ]

//sortedList03.cpp
//date: 09/13/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<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>


const int ARRAY_SIZE = 10;
const int UNDEFINED  = -9999;


class CSortedList
  {
  private:
    int array[ARRAY_SIZE];
    int count;
    int min;
    int max;
    void sortBubble1(void);
    void sortBubble2(void);
  public:
    CSortedList(void);
    CSortedList(char ch);
    void display(void);
    bool insert(int x); 
    bool isSorted(void);
  };


void main(void)
  {
  srand(time(NULL));
    /*
    {
    CSortedList myList;
    myList.display();
    }
    */

    {
    CSortedList myList('r');
    myList.display();
    }

    /*
    {
    CSortedList myList;
    myList.display();
    myList.insert(64);
    myList.display();
    myList.insert(14);
    myList.display();
    myList.insert(16);
    myList.display();
    myList.insert(78);
    myList.display();
    //myList.sortBubble1();
    }
    */
  }


CSortedList::CSortedList(void)
  {
  count = 0;
  min = UNDEFINED;
  max = UNDEFINED;
  } 


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


void CSortedList::display(void)
  {
  cout << "SortedList(" << count << ")= ";
  for (int i=0; i<count; i++)
    cout << array[i] << ' ';

  cout << endl;
  }


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


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


/*
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)
  {
  }