Write a java program that reads a user-input number N and then create a matrix of N x N random integers in the range [1, 1000]. Write the following functions

a. The function sortMatrix() that takes into account the created array and returns the sorted matrix in the non- decreasing order (From left to right, and from top to bottom). Use Bubble-Sort for this function.

b. Repeat part a) using Selection Sort instead of Bubble-Sort.

c. The function binarySearch() that takes into account the sorted matrix, a key K and returns the index positions

if K is in the matrix and returns -1 otherwise. Use binary search for this question.

d. Repeat part b) using Linear Search instead of Binary-Search.

Note: Sorting and Searching algorithms we learned applied for arrays. So flatten your matrix (i.e., treat your matrix) as an array to apply these algorithms.

Example

Please enter the number N: 5

13 56 95 11 16

12 23 25 77 83

19 99 21 86 46

34 66 29 67 42

29 20 50 71 83

Bubble Sorted:

11 12 13 16 19

20 21 23 25 29

29 34 42 46 50

56 66 67 71 77

83 83 86 95 99

Selection Sorted:

11 12 13 16 19

20 21 23 25 29

29 34 42 46 50

56 66 67 71 77

83 83 86 95 99

Binary Search Enter the key (0 to stop): 99

The key is found at index (3, 3).

Binary Search Enter the key (0 to stop): 117

The key is NOT found.

Binary Search Enter the key (0 to stop): 0

Linear Search Enter the key (0 to stop): 19

The key is found at index (0, 3).

Linear Search Enter the key (0 to stop): 117

The key is NOT found.

Linear Search Enter the key (0 to stop): 0

All done.