Reference no: EM132306149

Algorithms and Data Structures Assignment - Sorting and Searching

Learning Outcomes - Implement common data structures and algorithms.

Question 1 -

SETUP - for this entire assignment;

You are required to write a console application with an Algorithm class.

This class should contain a Numbers array which contains 50 integer elements.

These elements are to be generated at random.

You are to write a Display method, which will display the contents of this array to the screen.

Add the appropriate code to Main, so the numbers are displayed.

The particular challenge for this question is to then add a findMaximum method to your program that will receive two parameters:

• an array
• an integer (n = number of maximum elements to be found)

This method has the job of displaying the n largest elements in the array it receives and displaying it to the screen as shown in the sample program attached.

NOTE: Do not use the array sort method to complete this challenge.

Question 2 -

When using a sequential search algorithm (such as linear) to find a value, it will always find the first occurrence of that item in the array.

For example consider an array intArray with values 2, 4, 8, 6, 18, 4, 9, 4, 3.

If the user wanted to search for the number 4 in the array, a sequential search algorithm will return the first occurrence of 4 (that is at index 1 in the intArray).

For this question you are required to extend the program and class created in question 1 by adding a NumOccuranceSearch method, which is a modified sequential search that receives three parameters:

• an array
• an integer (the value the user wants to search for i.e. 4)
• and a second integer (the occurrence of the item they want to search for i.e. 2nd).

The method is to display the index of the occurrence of that number to the screen as shown in the sample program attached.

Question 3 -

For this question you are required to extend the program and class even further by adding a LastOccuranceSearch method, which finds the last occurrence of the searched item.

The method should receive two parameters:

• an array
• an integer (the value the user wants to search for i.e. 4)

And return the index of the last occurrence to Main, so it can be displayed.

Question 4 -

As you know the bubble sort algorithm isn't the fastest method for sorting data, but it could be improved.

The challenge for this question is to look at improving the bubble sort. Consider the following:

You will notice after the first pass of the algorithm the highest number is "in place", after the second pass the two highest numbers are "in place" and so on. Consider as the array elements are moved so the highest numbers in place, do we need to continue to make 49 passes of a 50 element array? Or can this be reduced?

For this question you are required to extend your program and class again by adding the following two methods:

• bubbleSort ()
• improvedBubbleSort ()

The bubbleSort () method will implement the standard bubble sort algorithm and time how long the takes to sort the values in your array.

The improvedBubbleSort () method will implement the following two improvements and time how long it takes to sort the same data:

1. Modify the algorithm so instead of making 49 comparisons on every pass of a 50 element array, it will now make 48 comparisons on the second pass, 47 on the third pass and so on.

2. Also modify the algorithm to check at the end of each pass whether any swaps have been made. If none have been made, the data must already be in the proper order, so the algorithm should terminate.

Both methods should output the resulting times to the screen to see if any improvement in times has been achieved.

Attachment:- Assignment File.rar