Question

NEED: INSERTION SORT AND BINARY SEARCH

IMMEDIATE NEED: Implement 2 searches and 2 sorts, and write test
programs to convince someone that you did them right.
DIRECTIONS:
You have been provided:
1. Function stubs for searching and sorting algorithms:
Utility functions: swap, shift right/left, show array,
insertion point.
Searching: linear seach, binary search
Sorting: bubble sort, insertion sort, selection sort.
2. Main program providing a pattern for testing youour
functions, including:
- sample arrays, each providing a different test case.
- sample test for one function.
You are expected to:
1. Complete the function stubs needed to implement the
searches/sorts you can implement.

#include
#include
using namespace std;

//-------------------------------------------------------------------------
// Filename: test_XXXX.cpp
// Purpose: Implement one search or sort functions, and provide a main
// to test the function.
// NOTE: Write a separate program for each function.
// When bubble sort is written:
// complete BubbleSort function.
// complete main to call BubbleSort with various arrays.
// file name is: test_BubbleSort.cpp
// ---------------------------------------------------------------------------

// Utility: Swap values of two variables.
void Swap(int & x, int & y)
{
nt temp=x;
x=y;
y=temp;
}//Swap

// Utility: Display array values ON ONE LINE.
void ShowArray(int X[], int Xsize)
{

}//ShowArray

// Utility: Shift LEFT one position, starting at index PIVOT.

// Utility: Shift RIGHT one position, starting at index PIVOT.
// Note: This INCREMENTS the size of the array.
void ShiftRight(int A[], int & Asize, int PIVOTindex)
{
  
}//ShiftRight

// Utility: Shift LEFT one position, starting at index PIVOT.
// Note: This DECREMENTS size of the array.
void ShiftLeft(int A[], int & Asize, int PIVOTindex)
{

} //ShiftRight

// Utility: Return index of first value in array that is >= key.
int InsertionPoint(int key, int A[], int Asize)
{

} //InsertionPoint

// Bubble sort.
void BubbleSort(int A[], int Asize)
{
for(int i=0; i for(int j=i+1;j if(A[i]>A[j]){
swap(A[i],A[j]);
}
}
}
}//BubbleSort

// Selection sort.
void SelectionSort(int B[], int Bsize)
{

}//SelectionSort

// Insertion sort.
void InsertionSort(int B[], int Bsize)
{

}//InsertionSort

// Linear search.
bool LinearSearch(int key, int C[], int Csize)
{
{
for(int i=0; i if(C[i]==key)return true;
}
return false;
}//LinearSearch

// Binary Search (RECURSIVE).
bool BinarySearch(int key, int C[], int LOindex, int HIindex)
{

}//BinarySearch

//==================== MAIN BELOW ====================

int main()
{
int numbers[] ={56,43,87,99,12,45,23,58,93,23,36,41};
int size = sizeof(numbers)/sizeof(int);
cout<<"Unsorted Array: "< for(int i=0; i cout<   
}//main

Answer 1

// C++ program to implement InsertionSort and BinarySearch functions

#include <iostream>

using namespace std;

// Insertion sort.

void InsertionSort(int B[], int Bsize);

// Binary Search (RECURSIVE).

bool BinarySearch(int key, int C[], int LOindex, int HIindex);

int main()

{

       int numbers[] ={56,43,87,99,12,45,23,58,93,23,36,41};

       int size = sizeof(numbers)/sizeof(int);

       cout<<"Unsorted Array: "<<endl;

       for(int i=0; i<size;i++)

             cout<<numbers[i]<<" ";

       cout<<endl;

       InsertionSort(numbers,size);

       cout<<"Sorted Array: "<<endl;

       for(int i=0; i<size;i++)

             cout<<numbers[i]<<" ";

       cout<<endl;

       cout<<boolalpha<<BinarySearch(5,numbers,0,size-1)<<endl;

       cout<<boolalpha<<BinarySearch(41,numbers,0,size-1);

       return 0;

}

// Insertion sort.

void InsertionSort(int B[], int Bsize)

{

       int i,j;

       int key;

       for(i=1;i<Bsize;i++)

       {

             j = i-1;

             key = B[i];

             while((j>=0) && (B[j]>key))

             {

                    B[j+1] = B[j];

                    j--;

             }

             B[j+1] = key;

       }

}

// Binary Search (RECURSIVE).

bool BinarySearch(int key, int C[], int LOindex, int HIindex)

{

       if(LOindex > HIindex)

             return false;

       int mid = (int)((LOindex+HIindex)/2);

       if(C[mid] == key)

             return true;

       else if(C[mid] > key)

             return BinarySearch(key,C,LOindex,mid-1);

       else

             return BinarySearch(key,C,mid+1,HIindex);

}

//end of program

Output: