#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void fillArray(int aData[], int iSize);
void printArray(int aData[], int iSize);
void selectionSort(int aData[], int iSize);
void insertionSort(int aData[], int iSize);
void bubbleSort(int aData[], int iSize);
bool binarySearch (int a[], int iFirst, int iSize, int iTarget);

int main()
{
  const int iSIZE = 10;
  int aData[iSIZE];
  srand(time(NULL));
  int iChoice;
  
  fillArray(aData, iSIZE);
  printArray(aData, iSIZE);
  
  cout << "Selection sort: " << endl;
  selectionSort(aData, iSIZE);
  printArray(aData, iSIZE);
  
  cout << endl;
  
  fillArray(aData, iSIZE);
  printArray(aData, iSIZE);

  cout << "Insertion sort: " << endl;
  insertionSort(aData, iSIZE);
  printArray(aData, iSIZE);
  
  cout << endl;
  
  fillArray(aData, iSIZE);
  printArray(aData, iSIZE);

  cout << "Bubble sort: " << endl;
  bubbleSort(aData, iSIZE);
  printArray(aData, iSIZE);

  cout << "Enter a number to see if it's in the array: ";
  cin >> iChoice;
  if (binarySearch(aData, 0, iSIZE, iChoice))
    cout << "Yes, it is there" << endl;
  else
    cout << "No, it's not there" << endl;
  
  system("PAUSE");
  return 0;    
}

void printArray(int aData[], int iSize)
{
  for (int i = 0; i < iSize; i++)
    cout << aData[i] << " ";
    
  cout << endl;
  
  return;
}

void fillArray(int aData[], int iSize)
{
  for (int i = 0; i < iSize; i++)
    aData[i] = (rand() % 10);
    
  return;
}

void selectionSort(int aData[], int iSize)
{
  int iMin, iTemp;
  for (int i = 0; i < iSize; i++)
  {
    iMin = i;
    
    for (int j = (iSize - 1); j > i; j--)
    {
      if (aData[j] < aData[iMin])
      iMin = j;
    }
  iTemp = aData[i];
  aData[i] = aData[iMin];
  aData[iMin] = iTemp;
  }
  
  return;
}

void insertionSort(int aData[], int iSize)
{
  int iTemp;
  for (int i = 0; i < iSize; i++)
  {
    iTemp = aData[i];
    int j = (i - 1);
    while (iTemp < aData[j] && j >= 0)
    {
      aData[j + 1] = aData[j];
      j--; 
    }
    aData[j + 1] = iTemp;
  }
  return;
}

void bubbleSort(int aData[], int iSize)
{
  int iTemp;
  for (int i = 0; i < iSize; i++)
  {
    for (int j = 0; j < iSize; j++)
    {
      if (aData[j] > aData[j + 1])
      {
        iTemp = aData[j];
        aData[j] = aData[j + 1];
        aData[j + 1] = iTemp;
      }
    }
  }
  
  return;
}

bool binarySearch (int a[], int iFirst, int iSize, int iTarget)
{
  int iMiddle;
  bool bFound = false;
  if (iSize > 0)
  {
    iMiddle = iFirst + (iSize / 2);
    if (a[iMiddle] == iTarget)
      bFound = iMiddle;
    else if (a[iMiddle] > iTarget)
      bFound = binarySearch(a, iFirst, (iSize / 2), iTarget);
    else
      bFound = binarySearch(a, iMiddle + 1, (iSize - 1) / 2, iTarget);
  }
  
  return bFound;
}