Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

READ DIRECTIONS CAREFULLY Your program will sort a two dimensional array (5 * 4) based on the following: The entire array should be sorted using

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 1st 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 2nd 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 3rd 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 5th row in ascending order and display the entire array

Ask the user for a number, search for that number in the 5th 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 5th 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;

}

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database And Expert Systems Applications 24th International Conference Dexa 2013 Prague Czech Republic August 2013 Proceedings Part 2 Lncs 8056

Authors: Hendrik Decker ,Lenka Lhotska ,Sebastian Link ,Josef Basl ,A Min Tjoa

2013th Edition

3642401724, 978-3642401725

More Books

Students also viewed these Databases questions

Question

an aggregation of physical Ethernets connected by switches

Answered: 1 week ago

Question

Design a job advertisement.

Answered: 1 week ago