Ai giúp minh lam bai nay với Computers are often used to sort lists of numbers, especially when this list is long. Many different sorting techniques are available to cope with different types of data to be sorted and to increase the efficiency of the sort. In this assignment you will use selection sort, modify the sorting procedure to include merges, and compare how effectively these modifications work on a large list of integers. An important part of the assignment is to make comparisons on the computational complexity of the modifications. You have been learned the selection sort. You are to use this as the basis for the code required for the assignment. We will deal with integer values only in the assignment and this code will take an array of integers which are unsorted and produce a sorted array of integers in ascending order. You should write the code that will create an array of integers in random order. The length of the array is arbitrary but should be specified at run time. Duplicates are allowed in the array. As a first step, make sure that the array can be sorted correctly into ascending order using the selection sort. Then the following modification should be made. The list of random integers should be split into two equal parts. Each part should then be sorted with selection sort and finally, the two parts should be merged into one list which is the original list in sorted order. You need to provide the code which merges two sorted lists into one sorted list. Obviously we could break the list into more than two equal parts, for example 3 equal sublists, 4 equal sublists, 8 equal sublists, and so on. You need to write the code which will prompt the user on the number of times the lists are to be split into smaller lists and the number of sublists that each list will become when it is split. The original list will be divided into the number of sublists specified and each sublist sorted with selection sort. The sorted sublists will then be merged, two sublists at a time, until only one sorted list remains that contains all of the integers in the original list. You should merge lists of equal size so that it is easier to see relationships during the analysis. Note that 4 sublists will require 3 merges to obtain the final list. In addition, your code should also keep track of the total number of comparisons of two digits required and the total number of data moves required for each sort and each merge. The sublists used will then be split again and the process repeated. Eventually the sublists will be very small. Analysis A major part of this assignment is an analysis of the performance of the sorting procedures with the modifications. You will need to be sure that your code will provide the information that you need to answer the questions below. The actual data will vary depending on the number of integers in the list and how you split the data on each successive run. Intelligent choices on the number of items and how the splitting occurs will make it easier to do the analysis. 1. What is the computational complexity of the selection sort when used on the total list of integers. You should express this as O, but should be able to substantiate this with the data from actual runs. 2. When you continue to break the list into smaller sublists, there is a point where the amount of comparisons to do the merges is as great or greater than the comparisons to do the selection sort for the small sublists. Determine the approximate size of sublist at which this occurs. 3. Create a graph that shows your information on a number of compares for the sorts and the merges for different sizes of sublists. 4. Is the point at which the compares for all of the selection sorts and the compares for the merges is about the same something that depends on the size of the original list or is the sublist size relatively independent? Explain using both the theoretical analysis and your experimental data. pài lập trình java thầy cho.híc.có ai biết làm không giúp mình với
Posted on: Sat, 22 Mar 2014 17:13:53 +0000
Recently Viewed Topics
© 2015