/* 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()


/* 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++)
      if (arr[i] == val)		// if true, found it!
         return i;			// if found, return the index

   // if I'm still IN the function at this point, loop has ended
   //  and I still haven't found what I'm looking for
   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 mid, low = 0, high = size-1;
   
   while (low <= high)
   {
      // compute the "middle" item of the [low,high] range
      mid = (low + high) / 2;
      if (arr[mid] < val)   // midpoint too small, throw out low half
          low = mid+1;
      else if (arr[mid] > val)	// midpoint too big, throw out high half
          high = mid-1;
      else
	  return mid;
   }

   // if you make it here, you didn't find the thing.
   return -1;
}

void BubbleSort(int arr[], int size)
{
   for (int i = 0 ; i < size-1; i++)	// this does size-1 total "passes"
   {
      for (int j = 0; j < size-1; j++)	// this is ONE pass through the array
      {
         if (arr[j] > arr[j+1])		// is j out of order with neighbor j+1
         {
            int temp = arr[j];		// swap them
            arr[j] = arr[j+1];
            arr[j+1] = temp;
         }
      }
   }
}

void SelectionSort(int arr[], int size)
// try filling in this one
// strategy:  find smallest item in array, swap into slot 0.
// Now repeat for slot 1 through end, swap into slot 1.
// keep repeating for each slot in sequence.
{




}