SortedList06
[ Home ] [ Up ]

//sortedList06.cpp
//date: 09/16/2002
//author: AOU

//Assignment #2
//Date assigned 9/13/2002
//Date due      9/23/2002
//Implement sortBubble2 
//Algorithm and Implementation for isSorted
//Supply detailed documentation for each member function
//Test functions will be supplied and published


////////////////////////////////////////////////////////////
// Include files
////////////////////////////////////////////////////////////
#include<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>


////////////////////////////////////////////////////////////
// Constants
////////////////////////////////////////////////////////////
const int ARRAY_SIZE = 40;
const int UNDEFINED  = -9999;


////////////////////////////////////////////////////////////
// Test function prototypes
////////////////////////////////////////////////////////////
void testSortBubble2(void);
void testSearchSeq(void);


////////////////////////////////////////////////////////////
// Class CSortedList
////////////////////////////////////////////////////////////
class CSortedList
  {
  private:
    int m_array[ARRAY_SIZE];
    int m_count;
    int m_min;
    int m_max;
    void sortBubble1(void);
  public:
    CSortedList(void);
    CSortedList(char ch);
    void display(void);
    bool insert(int x); 
    bool isSorted(void);
    void sortBubble2(void);
    void shuffle(void);
    int searchSeq(int x);
  };


////////////////////////////////////////////////////////////
// main function
////////////////////////////////////////////////////////////
void main(void)
  {
  srand(time(NULL));
  //testSortBubble2();
  testSearchSeq();
  }



////////////////////////////////////////////////////////////
// searchSeq(x)
////////////////////////////////////////////////////////////
/*Given sorted array[0..count-1], x
  [12, 23, 27, 29, 32], 27 => 2
  [12, 23, 27, 29, 32], 24 => -1

  Algorithm0:
  search for x from left to right in array[]
    if found return the position

  return -1


  Algorithm1:
  for i=0 to count-1 do the following
    if x = array[i] then return i
    end for

  return -1


  Algorithm2:
  for i=0 to count-1 do the following
    if x = array[i] then return i
    if x < array[i] then exit for loop
    end for

  return -1

*/
int CSortedList::searchSeq(int x)
  {
  for (int i=0; i<=this->m_count-1; i++)
    {
    if (x == m_array[i])
      return i;
    if (x < this->m_array[i])
      break;
    }

  return -1;
  }


void testSearchSeq(void)
  {
  for (int j=1; j<=5; j++)
    {
    CSortedList myList('r');
    int x, p;
    myList.display();

    for (int i=0; i<10; i++)
      {
      x = rand()%100;
      p = myList.searchSeq(x);
      cout << x << " was found at position " << p << endl;
      }
    cout << "-----------------\n";
    }
  }

////////////////////////////////////////////////////////////
// CSortedList(void)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(void)
  {
  this->m_count = 0;
  this->m_min = UNDEFINED;
  this->m_max = UNDEFINED;
  } 


////////////////////////////////////////////////////////////
// CSortedList(char ch)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(char ch)
  {
  this->m_count = 0;
  int x, n;
  if ('r' == ch)
    {
    n = rand()%ARRAY_SIZE+1;
    for (int i=0; i<n; i++)
      {
      x = rand()%100;
      this->insert(x);// or (*this).insert();
      }
    }
  }


////////////////////////////////////////////////////////////
// display(void)
////////////////////////////////////////////////////////////
void CSortedList::display(void)
  {
  cout << "SortedList(" << this->m_count << ")= ";
  for (int i=0; i<this->m_count; i++)
    cout << this->m_array[i] << ' ';

  cout << endl;
  }


////////////////////////////////////////////////////////////
// insert(int x)
////////////////////////////////////////////////////////////
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 == this->m_count) 
      return false;
    else
      {
      this->m_array[m_count] = x;
      this->m_count++;
      this->sortBubble1();
      return true;
      }
  }


////////////////////////////////////////////////////////////
// sortBubble1(void)
////////////////////////////////////////////////////////////
void CSortedList::sortBubble1(void)
  {
  int j;
  for (int i=1; i<=this->m_count-1; i++)
    {
    for (j=0; j<=this->m_count-2; j++)
      {
      if (this->m_array[j] > this->m_array[j+1])
        {
        int temp = this->m_array[j];
        this->m_array[j] = this->m_array[j+1];
        this->m_array[j+1] = temp;
        }
      }
    }
  }


////////////////////////////////////////////////////////////
// sortBubble2(void)
////////////////////////////////////////////////////////////
/*
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 m_count-2 do the following
    if m_array[i] > m_array[i+1] then
      swap m_array[i], m_array[i+1]
      sorted = false
      end if
    end for
  end while

*/
void CSortedList::sortBubble2(void)
  {
  }


////////////////////////////////////////////////////////////
// testSortBubble2(void)
////////////////////////////////////////////////////////////
void testSortBubble2(void)
  {
  for (int i=1; i<=10; i++)
    {
    CSortedList myList('r');

    cout << "Original list\n";
    myList.display();
    if (myList.isSorted())
        cout << "   List is SORTED\n";
      else
        cout << "   List is NOT SORTED\n";

    myList.shuffle();
    cout << "Shuffled list\n";
    myList.display();
    if (myList.isSorted())
        cout << "   List is SORTED\n";
      else
        cout << "   List is NOT SORTED\n";

    myList.sortBubble2();
    cout << "After sortBubble2\n";
    myList.display();
    if (myList.isSorted())
        cout << "   List is SORTED\n";
      else
        cout << "   List is NOT SORTED\n";

    cout << "-------------------\n";
    }
  }
    

////////////////////////////////////////////////////////////
// isSorted(void)
////////////////////////////////////////////////////////////
bool CSortedList::isSorted(void)
  {
  return true;
  }


////////////////////////////////////////////////////////////
// shuffle(void)
////////////////////////////////////////////////////////////
void CSortedList::shuffle(void)
  {
  int picked, temp;
  for (int i=0; i<=this->m_count-1; i++)
    {
    picked = rand()%this->m_count;
    temp = this->m_array[0];
    this->m_array[0] = this->m_array[picked];
    this->m_array[picked] = temp;
    }
  }