// ALGORTHM.CPP



void CreateRandomList(ListType &List, int N)
// Precondition:   List is instantiated empty
// Postcondition:  List is resized to N elements in range [1000..9999]
{
   List.resize(N);
   int K;
   for (K = 0; K < N; K++)
      List[K] = random(9000) + 1000;
}


void DisplayList(const ListType &List)
//  Purpose:  Displays elements of one-dimensional List
{
   int N = List.length();
   int K;
   for (K = 0; K < N; K++)
      cout << setw(5) << List[K];
   cout << endl;
   getch();
}


void CreateRandomMatrix(MatrixType &Matrix, int NR, int NC)
//  Precondition:   Matrix is instantiated empty
//  Postcondition:  Matrix is resized to NR rows and NC cols
//                  containing elements in range [1000..9999]
{
   Matrix.resize(NR,NC);
   int R,C;
   for (R = 0; R < NR; R++)
      for (C = 0; C < NC; C++)
	 Matrix[R][C] = random(9000) + 1000;
}


void DisplayMatrix(const MatrixType &Matrix)
//  Purpose:  Displays elements of two-dimensional Matrix
{
   int NR = Matrix.numrows();
   int NC = Matrix.numcols();
   int R,C;
   for (R = 0; R < NR; R++)
   {
      for (C = 0; C < NC; C++)
	 cout << setw(5) << Matrix[R][C];
      cout << endl;
   }
}


void LinearSearch(const ListType &List, int SearchNumber, int &Index)
// Precondition:   List is instantiated with N integer elements
// Postcondition:  If (List[K] == SearchNumber)
//                 Index returns K, otherwise Index returns -1
{
   int N = List.length();
   int K;
   bool Found = false;
   K = 0;
   while (K < N && !Found)
   {
     if (List[K] == SearchNumber)
	Found = true;
     else
	K++;
   }
   if (Found)
      Index = K;
   else
      Index = -1;
}


void DeleteItem(ListType &List, int Index)
// Precondition:   List is instantiated with N integer elements
//                 List[Index] needs to be removed
// Postcondition:  List[Index] is removed
//                 List is resized to N-1 elements
{
   int J;
   int N = List.length();
   for (J = Index; J < N-1; J++)
      List[J] = List[J+1];
   List.resize(N-1);
}


void Swap(int &A, int &B)
// Postcondition:  Integers A and B are exchanged
{
   int T;
   T = A; A = B; B = T;
}


void BubbleSort(ListType &List)
// Precondition:   List is instantiated with N random integers
// Postcondition:  List is returned with N integers in ascending order
{
   int P,Q;
   bool Sorted;
   int N = List.length();
   P = 0;
   do
   {
      Sorted = true;
      for (Q = 0; Q < N-P-1; Q++)
	 if (List[Q] > List[Q+1])
	 {
	    Swap(List[Q],List[Q+1]);
	    Sorted = false;
	 }
   }
   while (!Sorted);
}


void SelectionSort(ListType &List)
// Precondition:   List is instantiated with N random integers
// Postcondition:  List is returned with N integers in ascending order
{
   int P,Q;
   int Smallest;
   int N = List.length();
   for (P = 0; P < N-1; P++)
   {
      Smallest = P;
      for (Q = P+1; Q < N; Q++)
	 if (List[Q] < List[Smallest])
	    Smallest = Q;
      if (List[P] != List[Smallest])
	 Swap(List[P],List[Smallest]);
   }
}

void SearchPosition(const ListType &List, int SearchNumber, int &Index)
// Precondition:   List is instantiated with N integer elements
// Postcondition:  Index returns the search position
{
   int N = List.length();
   Index = 0;
   while (Index < N && SearchNumber > List[Index])
      Index++;
}

void InsertItem(ListType &List, int SearchNumber, int Index)
// Precondition:   List is instantiated with N integer elements
// Postcondition:  List[Index] = SearchNumber
//                 List is resized to N+1 elements

{
   int K;
   int N = List.length();
   List.resize(N+1);
   for (K = N; K > Index; K--)
      List[K] = List[K-1];
   List[Index] = SearchNumber;
}


void InsertionSort(ListType &List, int AddItem)
// Precondition:  List is instantiated with N elements in ascending order
// Postcondition: List is resized to N+1 elements
//                AddItem is inserted, such that List maintains
//                ascending order
{
   int K;
   int N = List.length();
   int Index;
   SearchPosition(List,AddItem,Index);
   InsertItem(List,AddItem,Index);
}


void BinarySearch(const ListType &List, int SearchNumber, int &Index)
// Precondition:   List is instantiated with N integer elements
// Postcondition:  If (List[Middle] == SearchNumber)
//                 Index returns Middle, otherwise Index returns -1
{
   cout << endl << endl;
   int N = List.length();
   bool Found = false;
   int Small = 0;
   int Large = N-1;
   int Middle;

   while (Small < Large+1 && !Found)
   {
      Middle = (Small + Large) / 2;
      if (List[Middle] == SearchNumber)
	 Found = true;
      else
	 if (List[Middle] > SearchNumber)
	    Large = Middle-1;
	 else
	    Small = Middle+1;
   }
   if (Found)
      Index = Middle;
   else
      Index = -1;
}