For part one of the lab you need to implement program to sort an array of integers in a fixed range (e.g., 0 through 19) using the "swap sort" technique described in class, and reviewed here:
For example, assume A = {12,5,14,5,11,12,18,2,4,5}. You need to first create a method "int findmindex(int startIndex)" that searches the array starting from startIndex, and returns the INDEX of the smallest number that it encountered. Be sure that you understand that findmindex returns the INDEX, or the position in the array that the smallest number was found, and not the number itself. Your program will contain a primary loop for(i=0;i<A.length;i++) that steps through the array, and for each step, call findmindex(i), which will return the index of the smallest number in the array starting from initial index i. You then swap the smallest number with the original ith element.
So during the first iteration of the loop (i=0), you will call findmindex(0) which will return 7, which is the array index where the smallest number (2) is stored. You then swap 7 with A[0], which will leave you with
A = {2,5,14,5,11,12,18,12,4,5}
During the second iteration of the loop (i=1), you will call findmindex(1), which will return 9, the index of the smallest element (4) of the array starting at index 1. You then swap 4 with A[1], giving you
A = {2,4,14,5,11,12,18,12,5,5}
Note that now the first two elements are in the right order. After the last iteration of the loop, you will have a sorted array:
A = {2,4,5,5,5,11,12,12,14,18}
Refer to the sample program posted on the web page for help.
Part 2 of the assignment asks you to conduct several experiments on the running time of your algorithm. You are to create five data files containing 1000, 2000, 3000, 4000, and 5000 randomly generated integers (between 0 and 9999). The code to create and read these files have been provided for you. Use the System.currentTimeMillis() function to find out how much time it took for your algorithm to work. Be sure that the timing samples are taken immediately before and after the call to your method. Also, make sure that no printing or IO of any kind is performed between time samplings, as these operations usually take much longer than pure computation.
Run all experiments on the same machine. Make sure all other applications (editors, web browsers, etc...) are closed before running your program. For each sample data file, run your program at least five times, and record the best result. This should help to factor out unforseen operating system interference while your program is running. It should be emphasized that each file should be created only ONCE - for example, you should create a file with 2000 integers ONCE, then comment out the makedata method call before running more tests and taking the best result.
Your are then to prepare a lab report following the format of the attached sample. List your data in the report, and plot them on a chart. Be neat. Answer the following questions: