/* Example of array searching and sorting
 * 
 */


#include <iostream>
using namespace std;

void PrintArray (const int arr[], const int size);
void FillArray(int arr[], const int size);

// Search will look through the array for val, and will return
//  the index where it was first found.  Returns -1 if not found
int LinearSearch(const int arr[], int size, int val);

int BinarySearch(const int arr[], int size, int val);

// these functions put the array into ascending order
void BubbleSort(int arr[], int size);
void SelectionSort(int arr[], int size);


/* Add your own function prototypes here */


int main()
{
   const int SIZE = 15;
   int number, answer;

   int list1[SIZE];
   int list2[SIZE] = {23, 48, 59, 62, 75, 81, 83, 88, 90, 92, 94, 
                          96, 97, 98, 99 };

   FillArray(list1, SIZE);
   cout << "The two lists:\n";
   PrintArray(list1, SIZE);
   PrintArray(list2, SIZE);

   // try our searches
   cout << "Enter a value to search for: ";
   cin >> number;
   answer = LinearSearch(list1, SIZE, number);
   cout << "Search result for list1 = " << answer << '\n';
   answer = LinearSearch(list2, SIZE, number);
   cout << "Search result for list2 = " << answer << '\n';
   
   cout << "Now trying binary search on list 2\n";
   answer = BinarySearch(list2, SIZE, number);
   cout << "Search result for list2 = " << answer << '\n';

   BubbleSort(list1, SIZE);
   SelectionSort(list2, SIZE);
   cout << "The two lists, after sorting:\n";
   PrintArray(list1, SIZE);
   PrintArray(list2, SIZE);

  


   return 0;
}					// end main()


/* Add in the definitions of your own 5 functions */








/* Definitions of PrintArray and FillArray below
 *  Written by Bob Myers for C++			*/

void PrintArray(const int arr[], const int size)
// this function prints the contents of the array
{
   cout << "\nThe array:\n { ";
   for (int i = 0; i < size-1; i++)	// print all but last item
      cout << arr[i] << ", ";

   cout << arr[size-1] << " }\n";	// print last item
}

void FillArray(int arr[], const int size)
// this function loads the contents of the array with user-entered values
{
   cout << "Please enter " << size 
	<< " integers to load into the array\n> ";

   for (int i = 0; i < size; i++)
	cin >> arr[i];			// enter data into array slot
}


int LinearSearch(const int arr[], int size, int val)
// search arr for the value (val), and return index where found
//  return -1 if NOT found
{
   for (int i = 0; i < size; i++)
   {
//      cout << "      ** Loop iteration " << i+1 << "**\n";
      if (arr[i] == val)
	  return i;		// if we just found it, return the index
   }
          
   // we didn't find it while running loop.  So now return the "not 
   //   found" indication
   return -1;

}

int BinarySearch(const int arr[], int size, int val)
// for this to work, array must be sorted already (in ascending order)
// searches for val in the array, returns index where found (-1 if not 
//  found)
{
   int low = 0;			// track current low index
   int high = size-1;		// track current high index
   int mid;			// for computing midpoint
   int counter = 0;

   while (low <= high)		// while the indices are still in order
   {
/*
      cout << "      ** Loop iteration " << counter+1 << "**\n";
      counter++;
*/   
      mid = (low + high) / 2;	// compute midpoint of current range
      if (arr[mid] == val)	// if found, return index where found
	  return mid;
      else if (val < arr[mid])	// value is in low half
          high = mid - 1;
      else 			// (val is bigger, so in top half)
          low = mid + 1;
   }

   return -1;			// wasn't found
}

void BubbleSort(int arr[], int size)
{

   for (int j = 0; j < size - 1; j++)	// run process size-1 times
   {
     // this loop will "bubble" the high value to the top
     for (int i = 0; i < size-1-j; i++)
     {
        if (arr[i] > arr[i+1])	// if this one is bigger than his neighber
        {				//  swap them
            int temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
         }
     }
   }
}

void SelectionSort(int arr[], int size)
{
   int smallindex;
   for (int j = 0; j < size - 1; j++)		// run process size-1 times
   {
       // find smallest element (from index j upwards)
       smallindex = j;
       for (int i = j; i < size; i++)
       {
          if (arr[i] < arr[smallindex])
                smallindex = i;
       }
   
       // swap with slot j
       int temp = arr[j];
       arr[j] = arr[smallindex];
       arr[smallindex] = temp;
   }
}