The point of this lab exercise is to run some experiments to compare the run tim

Question

The point of this lab exercise is to run some experiments to compare the run time of some sorting algorithms.

The SlowSort has several static methods for sorting. You should start a new program and add SlowStart.java to that program.
Experiments with Sorting
The SlowSort class defines the following methods for sorting arrays of various types:
public static void selectionSort(double[] A) // sort the entire array
public static void insertionSort(double[] A) // sort the entire array
public static void bubbleSort(double[] A) // sort the entire array
public static void selectionSort(double[] A, int count) // sort A[0]..A[count-1]
public static void insertionSort(double[] A, int count) // sort A[0]..A[count-1]
public static void bubbleSort(double[] A, int count) // sort A[0]..A[count-1]
The class also includes the same set of six methods for sorting arrays of type int[] and arrays of type String[]. All of these methods have run time O(N2), where N is the number of items that is being sorted.
Now, there is a standard class in Java, java.util.Arrays, that includes its own methods for sorting arrays. Arrays.sort(A) can be used to sort an entire array A of numbers or strings. Arrays.sort(A,0,N) can be used to sort the first N items in an array A of numbers or strings. The sorting methods used by the Arrays class have run time O(N*log(N)), at least in the average case. (In fact, this class uses versions of MergeSort algorithm for sorting Objects and of QuickSort algorithm for sorting numbers.)
The goal of this lab is to investigate the run times of the various sorting algorithms and to get a feel for the real difference between O(n2) and O(n*log(n)). To do this, you will construct arrays filled with random values, use various methods to sort them, and measure the run times.
The basic idea is to make an array filled with random numbers or random strings. (You will have to think about how to generate 5 character random strings.) It's a good idea to make multiple copies of an array, so that you can try several sorting algorithms on the same data.
To measure the time that it takes to sort an array, you can use the following pattern:
long startTime = System.currentTimeMillis();
... // Sort the array
long runTime = System.currenTimeMillis() - startTime();
This measures the run time in milliseconds, where 1 millisecond equals 1/1000 second. For a small array, the time might be measured as 1 or 2 or even 0 milliseconds, which is only a very crude measurement of the actual run time. You really want to use arrays that will give a run time of at least, say, a dozen milliseconds or more.
Sorting Lab – Algorithm Analysis
Make sure that you only measure the time that it takes to sort the array. Don't include the time that it takes to fill the array with random values.
You should apply SlowSort.insertionSort, SlowSort.bubbleSort, SlowSort.selectionSort, and Arrays.sort to arrays of type double[], String[], and int[]. You should sort arrays of size 1000, 10000, and 100000, items. For Arrays.sort, you can also sort arrays of several million items for comparison.
You do not have to write one single program to run all the arrays. You can write several programs, or a program that can be easily modified to perform different experiments. Your program should, however, output the results in a clear format.

Explanation / Answer

public class SlowSort { public static void insertionSort(int[] A) { insertionSort(A, A.length); } public static void insertionSort(double[] A) { insertionSort(A, A.length); } public static void insertionSort(String[] A) { insertionSort(A, A.length); } public static void selectionSort(int[] A) { selectionSort(A, A.length); } public static void selectionSort(double[] A) { selectionSort(A, A.length); } public static void selectionSort(String[] A) { selectionSort(A, A.length); } public static void insertionSort(int[] A, int count) { for (int top = 1; top 0 && A[pos-1] > temp) { A[pos] = A[pos-1]; pos--; } A[pos] = temp; } } public static void insertionSort(double[] A, int count) { for (int top = 1; top 0 && A[pos-1] > temp) { A[pos] = A[pos-1]; pos--; } A[pos] = temp; } } public static void insertionSort(String[] A, int count) { for (int top = 1; top 0 && A[pos-1].compareTo(temp) > 0) { A[pos] = A[pos-1]; pos--; } A[pos] = temp; } } public static void selectionSort(int[] A, int count) { for (int top = count-1; top > 0; top--) { int maxLoc = 0; for (int i = 1; i A[maxLoc]) maxLoc = i; } int temp = A[maxLoc]; A[maxLoc] = A[top]; A[top] = temp; } } public static void selectionSort(double[] A, int count) { for (int top = count-1; top > 0; top--) { int maxLoc = 0; for (int i = 1; i A[maxLoc]) maxLoc = i; } double temp = A[maxLoc]; A[maxLoc] = A[top]; A[top] = temp; } } public static void selectionSort(String[] A, int count) { for (int top = count-1; top > 0; top--) { int maxLoc = 0; for (int i = 1; i 0) maxLoc = i; } String temp = A[maxLoc]; A[maxLoc] = A[top]; A[top] = temp; } } }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.