Complete the following programming assignment. Use good programming style and all the concepts previously covered. Submit the .java files and a UML class diagram electronically by the above due date. Also include Requirements (optional for this problem), Pseudo-Code (which also includes your algorithm and should be in Word format) Remember to submit the .zip file electronically by the above due date (in a Windows zip file). Submission Net: include Source Code (.java files), Pseudo-Code, and UML in Word format. Problem Assignment: Modify the programs presented in Chapter 23 ( ATTACHED FILE) that perform the Insertion Sort, Bubble Sort, Merge Sort, and Quick Sort algorithms on an int array, such that each program keeps a count of the number of swaps it makes. Then, write an application that uses four identical arrays of a least 20 integers. It should call each method (using the same array), and display the number of exchanges made by each algorithm. Also, explain in detail how each sort algorithm works (use word doc format).
Chapter 15 Multithreading Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * Chapter 23 Sorting Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * Objectives To study and analyze time complexity of various sorting algorithms (§§23.2–23.7). To design, implement, and analyze insertion sort (§23.2). To design, implement, and analyze bubble sort (§23.3). To design, implement, and analyze merge sort (§23.4). To design, implement, and analyze quick sort (§23.5). To design and implement a binary heap (§23.6). To design, implement, and analyze heap sort (§23.7). To design, implement, and analyze bucket sort and radix sort (§23.8). To design, implement, and analyze external sort for files that have a large amount of data (§23.9). Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * why study sorting? Sorting is a classic subject in computer science. There are three reasons for studying sorting algorithms. First, sorting algorithms illustrate many creative approaches to problem solving and these approaches can be applied to solve other problems. Second, sorting algorithms are good for practicing fundamental programming techniques using selection statements, loops, methods, and arrays. Third, sorting algorithms are excellent examples to demonstrate algorithm performance. Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * what data to sort? The data to be sorted might be integers, doubles, characters, or objects. §7.8, “Sorting Arrays,” presented selection sort and insertion sort for numeric values. The selection sort algorithm was extended to sort an array of objects in §11.5.7, “Example: Sorting an Array of Objects.” The Java API contains several overloaded sort methods for sorting primitive type values and objects in the java.util.Arrays and java.util.Collections class. For simplicity, this section assumes: data to be sorted are integers, data are sorted in ascending order, and data are stored in an array. The programs can be easily modified to sort other types of data, to sort in descending order, or to sort data in an ArrayList or a LinkedList. Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * Insertion Sort int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted The insertion sort algorithm sorts a list of values by repeatedly inserting an unsorted element into a sorted sublist until the whole list is sorted. 2 9 5 4 8 1 6 Step 1: Initially, the sorted sublist contains the first element in the list. Insert 9 into the sublist. Step 7: The entire list is now sorted. 1 2 4 5 8 9 6 Step 5: The sorted sublist is {2, 4, 5, 8, 9}. Insert 1 into the sublist. 2 4 5 8 9 1 6 Step 4: The sorted sublist is {2, 4, 5, 9}. Insert 8 into the sublist. 2 4 5 9 8 1 6 Step 3: The sorted sublist is {2, 5, 9}. Insert 4 into the sublist. 2 5 9 4 8 1 6 Step2: The sorted sublist is {2, 9}. Insert 5 into the sublist. 1 2 4 5 6 8 9 Step 6: The sorted sublist is {1, 2, 4, 5, 8, 9}. Insert 6 into the sublist. 2 9 5 4 8 1 6 Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * https://liveexample.pearsoncmg.com/dsanimation/InsertionSortNeweBook.html Insertion Sort Animation animation Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * Insertion Sort int[] myList = {2, 9, 5, 4, 8, 1, 6}; // Unsorted animation 2954816 2954816 2594816 2458916 1245896 2459816 1245689 Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * How to Insert? The insertion sort algorithm sorts a list of values by repeatedly inserting an unsorted element into a sorted sublist until the whole list is sorted. Step 2: Move list[2] to list[3] list [0] [1] [2] [3] [4] [5] [6] 2 4 5 9 list [0] [1] [2] [3] [4] [5] [6] Step 1: Save 4 to a temporary variable currentElement Step 3: Move list[1] to list[2] 2 5 9 [0] [1] [2] [3] [4] [5] [6] list 2 5 9 list Step 4: Assign currentElement to list[1] 2 5 9 4 [0] [1] [2] [3] [4] [5] [6] Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * From Idea to Solution for (int i = 1; i < list.length;="" i++)="" {="" insert="" list[i]="" into="" a="" sorted="" sublist="" list[0..i-1]="" so="" that="" list[0..i]="" is="" sorted="" }="" list[0]="" list[0]="" list[1]="" list[0]="" list[1]="" list[2]="" list[0]="" list[1]="" list[2]="" list[3]="" list[0]="" list[1]="" list[2]="" list[3]="" ...="" liang,="" introduction="" to="" java="" programming,="" eleventh="" edition,="" (c)="" 2017="" pearson="" education,="" inc.="" all="" rights="" reserved.="" *="" from="" idea="" to="" solution="" for="" (int="" i="1;" i="">< list.length;="" i++)="" {="" insert="" list[i]="" into="" a="" sorted="" sublist="" list[0..i-1]="" so="" that="" list[0..i]="" is="" sorted="" }="" expand="" double="" currentelement="list[i];" int="" k;="" for="" (k="i" -="" 1;="" k="">= 0 && list[k] > currentElement; k--) { list[k + 1] = list[k]; } // Insert the current element into list[k + 1] list[k + 1] = currentElement; Run InsertionSort Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * Bubble Sort Bubble sort time: O(n2) Run BubbleSort 2 9 5 4 8 1 2 5 9 4 8 1 2 5 4 8 9 1 2 5 4 9 8 1 2 5 4 8 1 9 (a) 1st pass (b) 2nd pass (c) 3rd pass 2 4 5 1 8 9 2 4 5 8 1 9 2 4 5 8 1 9 2 5 4 8 1 9 (d) 4th pass 2 4 1 5 8 9 2 4 5 1 8 9 2 4 5 1 8 9 (e) 5th pass 2 1 4 5 8 9 2 4 1 5 8 9 1 2 4 5 8 9 Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * Bubble Sort Animation https://liveexample.pearsoncmg.com/dsanimation/BubbleSortNeweBook.html Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * Merge Sort Run MergeSort 2 9 5 4 8 1 6 7 1 8 4 5 6 7 2 5 4 split 1 8 8 1 6 7 2 9 8 1 6 7 4 5 split split 9 6 7 2 9 5 4 merge 2 9 1 6 7 8 2 4 5 9 1 2 4 5 6 7 8 9 merge merge divide conquer Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * Merge Sort mergeSort(list): firstHalf = mergeSort(firstHalf); secondHalf = mergeSort(secondHalf); list = merge(firstHalf, secondHalf); Liang, Introduction to Java Programming, Eleventh Edition, (c) 2017 Pearson Education, Inc. All rights reserved. * Merge Two Sorted Lists Animation for Merging Two Sorted Lists 2 4 5 9 current1 1 current2 1 6 7 8 current3 current3