I need this assignment completed there's two different questions Lab8 A and Lab8 B, they needed to be coded in java and I need the final Java source code.
CS 2301/03 – Spring 2010 Page 1 of 3 CSE 1321L: Programming and Problem Solving I Lab Lab 8 Searching and Sorting Algorithms What students will learn: • Declaring and initializing 1D arrays (review) • Searching arrays using different techniques • How to visualize searching and sorting Overview: In the last lab, you worked with 1D arrays to perform basic operations (e.g. initializing them, reading from them, and comparing two arrays to see if they were equal). In this lab, we’re going to build on those concepts to better understand searching and sorting. Recall from lecture that we studied two different ways to search a 1D array of n elements (e.g. if there are 10 elements in the array, then n == 10). The thing we’re searching for is called the target. If the data is unsorted, then a linear search is required – which scans across all elements and therefore runs in “n” steps. However, if the data is sorted, you can run a binary search. This search starts in the middle of the array and compares it with the target. If the target is greater than that element, then we know to search the right half of the array. If not, we search the left half of the array (or we found the element). We continue to “chop the array in half” – progressively working on less and less data. This search runs in log2n, which is unbelievably fast. For sorting, we’re going to rearrange the array into a particular order. The three most common “beginner” sorts are Bubble, Insertion and Selection. For this lab, we’re going to focus on Bubble and count the number of total swaps that this sort has done as well as visualize the array after the inner loop has finished. That is, once an element has “bubbled” its way to the correct spot, you’re going to print the array and the total number of swaps that have occurred. As always, your filenames and class names should follow the conventions we’ve used all semester (i.e. filenames should be Lab8A(.java, .cs or .cpp)) and class names should be either Lab8A or Lab8B. Lastly, don’t forget your new mad skillz in using the debugger if you get stuck! It’s a great way to visualize the state of the array (or values of counters). Page 2 of 3 Lab8A: For this part of the lab, refer to the lecture slides for a review of Bubble Sort. Practice re-coding the program given in lecture. Write a program that prompts the user to enter 10 numbers and stores the input in a 1D array of size 10. Now, use Bubble Sort to sort the array—continuously pushing the largest elements to the right side of the array. Every time you swap two elements in the array, you need to increment a counter. After the inner loop has completed, you need to print out the current state of the array and the total number of swaps that have occurred. The sample outputs are shown below and the user input is in bold. Note: Sample output #1 shows the “worst case scenario” because it has the maximum number of swaps possible. Sample output #2 shows the “average” scenario because it has approximately half the number of swaps. Sample output #1 Enter slot 0: 10 Enter slot 1: 9 Enter slot 2: 8 Enter slot 3: 7 Enter slot 4: 6 Enter slot 5: 5 Enter slot 6: 4 Enter slot 7: 3 Enter slot 8: 2 Enter slot 9: 1 9|8|7|6|5|4|3|2|1|10| Num swaps: 9 8|7|6|5|4|3|2|1|9|10| Num swaps: 17 7|6|5|4|3|2|1|8|9|10| Num swaps: 24 6|5|4|3|2|1|7|8|9|10| Num swaps: 30 5|4|3|2|1|6|7|8|9|10| Num swaps: 35 4|3|2|1|5|6|7|8|9|10| Num swaps: 39 3|2|1|4|5|6|7|8|9|10| Num swaps: 42 2|1|3|4|5|6|7|8|9|10| Num swaps: 44 1|2|3|4|5|6|7|8|9|10| Num swaps: 45 1|2|3|4|5|6|7|8|9|10| Num swaps: 45 Sample output #2 Enter slot 0: 5 Enter slot 1: 10 Enter slot 2: 8 Enter slot 3: 2 Enter slot 4: 1 Enter slot 5: 6 Enter slot 6: 7 Enter slot 7: 3 Enter slot 8: 9 Enter slot 9: 4 5|8|2|1|6|7|3|9|4|10| Num swaps: 8 5|2|1|6|7|3|8|4|9|10| Num swaps: 14 2|1|5|6|3|7|4|8|9|10| Num swaps: 18 1|2|5|3|6|4|7|8|9|10| Num swaps: 21 1|2|3|5|4|6|7|8|9|10| Num swaps: 23 1|2|3|4|5|6|7|8|9|10| Num swaps: 24 1|2|3|4|5|6|7|8|9|10| Num swaps: 24 1|2|3|4|5|6|7|8|9|10| Num swaps: 24 1|2|3|4|5|6|7|8|9|10| Num swaps: 24 1|2|3|4|5|6|7|8|9|10| Num swaps: 24 Page 3 of 3 Lab8B: For this part of the lab, you will practice using Linear Search and Binary Search. Please review the lecture slides and try to re-code them. The goal of this lab is for you to perform these two searches and visualize the behavior. For this first part of the lab, write a program that prompts the user to enter 15 numbers in sorted order (meaning the user enters them in ascending order). Store the inputted numbers into a 1D array of size 15. Then, ask the user for a number to search for in the array (i.e. the “target”). Now, print the array. Next, use Linear Search to search the array. Print out each of the indices (or “indexes”) that are being examined until the algorithm finds the target. Finally, use Binary Search to search the array. Print out each of the indices (or “indexes”) that are being examined until the algorithm finds the target. Note: After the “target” is entered by the user, the program needs to print 1) the array, 2) the indices of a linear search and 3) the indices of a binary search. Your output should look like the sample output below. User input is in bold. Sample output #1 Enter slot 0: 0 Enter slot 1: 1 Enter slot 2: 2 Enter slot 3: 3 Enter slot 4: 4 Enter slot 5: 5 Enter slot 6: 6 Enter slot 7: 7 Enter slot 8: 8 Enter slot 9: 9 Enter slot 10: 10 Enter slot 11: 11 Enter slot 12: 12 Enter slot 13: 13 Enter slot 14: 14 Enter a target: 15 0|1|2|3|4|5|6|7|8|9|10|11|12|13|14| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 7 11 13 14 Sample output #2 Enter slot 0: 3 Enter slot 1: 11 Enter slot 2: 45 Enter slot 3: 57 Enter slot 4: 81 Enter slot 5: 125 Enter slot 6: 129 Enter slot 7: 311 Enter slot 8: 333 Enter slot 9: 361 Enter slot 10: 402 Enter slot 11: 412 Enter slot 12: 475 Enter slot 13: 499 Enter slot 14: 501 Enter a target: 402 3|11|45|57|81|125|129|311|333|361|402|412|475|499|501| 0 1 2 3 4 5 6 7 8 9 10 7 11 9 10 Instructions: • Programs must be working correctly. • Programs must be saved in files with the correct file name. • If working in Java or C#, class names must be correct. • Programs must be working and checked by the end of the designated lab session. • Programs (.java, .cs or .cpp files) must be uploaded to Gradescope by due date.