void insort(int * input, int length)

    {

     int S[100];

     S[0] = input[0];

     for (int i = 1; i < length; i++)

         {

         int temp = input[i];

         int j = i - 1;

         while (( S[j] > temp) && (j>=0))

             {

             S[j+1] = S[j];

             j--;

             }

             S[j+1] = temp;

             }

             for (int k = 0; k < length; k++)

                 {

                 input[k] = S[k];

                 }

            }

            void quicksort(int * input, int first, int last)

                {

                 int temp;

                 if (first < last)

                     {

                     int pivot = input[first];

                     int i = first;

                     int j = last;

                     while (i < j)

                         {

                         while (input[i] <= pivot && i < last)

                             {

                             i += 1;

                             }

                             while (input[j] >= pivot && j > first)

                                 {

                                 j -= 1;

                                 }

                                 if (i < j)

                                     {

                                     temp = input[i];

                                     input[i] = input[j];

                                     input[j] = temp;

                                     }

                                     }

                                     temp = input[first];

                                     input[first] = input[j];

                                     input[j] = temp;

                                     quicksort(input, first, j-1);

                                     quicksort(input, j +1, last);

                                     }

                                }

                                int binarysearch(int key, int * input, int first, int last)

                                    {

                                     int head = first;

                                     int tail = last;

                                     int middle = last - first;

                                     if (key == input[middle])

                                         {

                                         return middle;

                                         }

                                         if (key > input[middle])

                                             {

                                             return binarysearch(key, input, middle + 1, last);

                                             }

                                             if (key < input[middle])

                                                 {

                                                 return binarysearch(key, input, first, middle - 1);

                                                 }

                                                 return (-1);

                                            }

                                            int main(int argc, char* argv[])

                                                {

                                                 int * input = new int[5];

                                                 int one, two, three, four, five;

                                                 int choice;

                                                 cout << "Enter five numbers seperated by spaces: ";

                                                 cin >> one >> two >> three >> four >> five;

                                                 input[0] = one;

                                                 input[1] = two;

                                                 input[2] = three;

                                                 input[3] = four;

                                                 input[4] = five;

                                                 cout << "\n Would you like to [1] Quick sort [2] Insertion sort: ";

                                                 cin >> choice;

                                                 switch(choice)

                                                     {

                                                     case 1:

                                                     quicksort(input, 0, 1);

                                                     break;

                                                     case 2:

                                                     insort(input, 2);

                                                     break;

                                                     default:

                                                     cout << "Invalid, Exiting...\n\n";

                                                     break;

                                                     }

                                                     cout << "What number would you like to find? : ";

                                                     int num;

                                                     cin >> num;

                                                     int place = binarysearch(num, input, 0, 4);

                                                     cout << "\n\n" << num << " is at [" << place << "] in the array.\n";

                                                     return 0;

                                                }