READ DIRECTIONS CAREFULLY

Your program will sort a two dimensional array (5 * 4) based on the following:

The entire array should be sorted using bubble sort based on the 1^st column in ascending order and display the entire array.

Reset the array to its original contents. The entire array should again be sorted using selection sort based on the 2^nd column in descending order and display the entire array.

Reset the array to its original contents. The entire array should again be sorted using shell sort based on the 3^rd column in ascending order and display the entire array

Reset the array to its original contents. The entire array should again be sorted using insertion sort based on the 5^th row in ascending order and display the entire array

Ask the user for a number, search for that number in the 5^th row of the array that was sorted via insertion sort, using binary search. Display the entire column.

Your array could be declared as a global variable since it is being used everywhere.

****When sorting columns, row items MUST stay together. This means when comparing columns, if there is a swap, all row items associated with column must also be swapped so that all row content stays together while sorting columns. OUTPUT MUST MIMIC EXAMPLES BELOW.

For example, given the following array:

5	3	2	16
9	8	10	17
4	7	11	18
2	5	9	12
7	9	4	10

	5	3	2	16
	9	8	10	17
	4	7	11	18
	2	5	9	12
5th row Insertion Ascending	7	9	4	10
	1st column Bubble Ascending	2nd column Selection Descending	3rd column Shell Ascending

After bubble sort

2	5	9	12
4	7	11	18
5	3	2	16
7	9	4	10
9	8	10	17

After selection sort (Descending order)

7	9	4	10
9	8	10	17
4	7	11	18
2	5	9	12
5	3	2	16

Do the same kind of thing for shell sort (Ascending order based on the 3rd column)

After Insertion sort

2	5	3	16
10	9	8	17
11	4	7	18
9	2	5	12
4	7	9	10

What number are you searching for in the 5^th row? 9

3

8

7

5

9

Make sure to modularize your program. Each of the sorts and searches must happen in their own functions. Reset the array to its original contents after each sort.

FUNCTION TEMPLATES

void selection(int arr[], int limit)

{

int temp, index_of_largest,index;

//This loop is used to determine the number of passes

for(;limit > 0;limit--){

index_of_largest=0 ;

//This loop is used to determine the number of

//comparisons for each pass

for (index=1; index<=limit; index++) {

//To change to descending order just change the

//relational operator to <.

if (arr[index] > arr[index_of_largest])

index_of_largest=index; //Store the

//index of

//array element

}

//Swap element at the end of pass if needed

if (limit !=index_of_largest){

temp=arr[limit];

arr[limit]=arr[index_of_ largest];

arr[index_of_ largest]=temp;

}

}

}

int main()

{

int arr[size] ={43,22,17,36,16} ;

int effective_size=5;

selection(arr,effective_size-1); //Pass entire array

for (int i=0; i

cout << arr[i]<

}

}

void insertion_sort(int arr[])

{

int i, j ,tmp;

for (i = 1; i < SIZE; i++) {

for (j=i; j>0 && arr[j] < arr[j-1];j--){

tmp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = tmp;

}

}

}

void display(int a[], int n){

for (int i=0; i

cout<

}

void shell(int a[], int n){

int temp;

for (int gap=n/2; gap>=1; gap=gap/2)

for(int i=gap; i

for (int j=i; j>=gap && a[j-gap]>a[j];j=j-gap){

temp=a[j-gap];

a[j-gap]=a[j];

a[j]=temp;

}

display(a,n);

}

int binary_search(int A[], int key)

{

int high = SIZE-1, low = 0, mid;

bool found=false;

while (high >= low && !found){

// calculate the midpoint for roughly equal partition

mid = low + (high - low) / 2;

if (key>A[mid] )

low = mid + 1;

else if (key

high = mid - 1;

else

found=true;

}

return found;

}