Solution for Programming Exercise 7.3
This page contains a sample solution to one of the exercises from Introduction to Programming Using Java.
Exercise 7.3:
In Subsection 7.4.4, it is mentioned that the standard sorting method Arrays.sort() is much faster and efficient than selection sort. Write a program to test this claim. To be specific, your program should create a large array filled with random real numbers. It should use both Arrays.sort() and selectionSort() to sort the array, and it should time how long it takes to perform each sort. Furthermore, it should do the same thing for a large array of random Strings. To find the times, you can use System.nanoTime() (see Subsection 2.3.1 and the example TimedComputation.java).
This exercise is most interesting for the results of the timing experiments, but one point of interest is how to make a "random string." In my program, I make a string containing uppercase letters, with a random length:
private static String randomString() {
int length = 5 + (int)(21*Math.random());
StringBuilder str = new StringBuilder();
for (int i = 0; i < length; i++) {
char ch = (char)('A' + (int)(26*Math.random())); // a random letter
str.append(ch);
}
return str.toString();
}
This method is then used to fill an array with random strings. I wrote methods for creating random arrays of a given size. I used Arrays.copyOf() to make copies of the arrays. I need two copies of each random array, since I want to apply selectionSort() and Arrays.sort() to identical data. So the arrays are created with
numberList1 = randomNumbers(SIZE); numberList2 = Arrays.copyOf(numberList1, SIZE); stringList1 = randomStrings(SIZE); stringList2 = Arrays.copyOf(stringList1, SIZE);
where SIZE is a constant. (By using a constant here, I can easily adapt the program to run with different array sizes.)
The selection sort algorithm is copied from Subsection 7.4.4. We actually need two selectionSort methods, one to sort numbers an one to sort strings. You will see that my program includes tests of those methods. Without that test, I wouldn't have been confident that my subroutines were sorting the arrays correctly.
The code for timing the sorting algorithms is straightforward. Here are sort times from my program, running on a rather old computer. Note that Arrays.sort() is much faster than selectionSort. Also, it takes longer to sort strings that it takes to sort numbers, since comparing two strings takes longer than comparing two numbers. The advantage of Arrays.sort() is greater for strings than it is for numbers. I'm not sure why that happens.
Seconds to sort 100000 numbers with selectionSort: 12.6222 Seconds to sort 100000 numbers with Arrays.sort(): 0.0656723 Seconds to sort 100000 strings with selectionSort: 265.148 Seconds to sort 100000 strings with Arrays.sort(): 0.157401
You can try running the program with different array sizes. A large difference is noticeable even for arrays of size 1000, although all of the times are rather short in that case. The advantage of Arrays.sort() increases as the array size increases.
import java.util.Arrays;
public class SortExperiments {
final static int SIZE = 100000; // The length of arrays that will be sorted.
/**
* Creates a random string. The length of the string is between 5 and 25,
* and it is made up of randomly selected uppercase letters.
*/
private static String randomString() {
int length = 5 + (int)(21*Math.random());
StringBuilder str = new StringBuilder();
for (int i = 0; i < length; i++) {
char ch = (char)('A' + (int)(26*Math.random()));
str.append(ch);
}
return str.toString();
}
/**
* Creates an array of random real numbers. The items in the array
* are random numbers in the range 0.0 to 1.0.
* @param count The length of the array that is created.
*/
private static double[] randomNumbers(int count) {
double[] numbers = new double[count];
for (int i = 0; i < count; i++)
numbers[i] = Math.random();
return numbers;
}
/**
* Creates an array of random strings. The items in the
* array are created by calling the function randomString();
* @param count the size of the array that is created
*/
private static String[] randomStrings(int count) {
String[] strings = new String[count];
for (int i = 0; i < count; i++)
strings[i] = randomString();
return strings;
}
/**
* Sort an array of real numbers using the selection sort algorithm.
*/
private static void selectionSort(double[] numbers) {
for (int top = numbers.length-1; top > 0; top-- ) {
int maxloc = 0;
for (int i = 1; i <= top; i++) {
if (numbers[i] > numbers[maxloc])
maxloc = i;
}
double temp = numbers[top];
numbers[top] = numbers[maxloc];
numbers[maxloc] = temp;
}
}
/**
* Sort an array of strings using the selection sort algorithm.
*/
private static void selectionSort(String[] numbers) {
for (int top = numbers.length-1; top > 0; top-- ) {
int maxloc = 0;
for (int i = 1; i <= top; i++) {
if (numbers[i].compareTo(numbers[maxloc]) > 0)
maxloc = i;
}
String temp = numbers[top];
numbers[top] = numbers[maxloc];
numbers[maxloc] = temp;
}
}
public static void main(String[] args) {
long startTime; // time when a sort begin.
long endTime; // time when a sort ends.
double[] numberList1; // An array of random numbers.
double[] numberList2; // A copy of numberList1.
String[] stringList1; // An array of random strings.
String[] stringList2; // A copy of stringList1.
/* Make sure the selection sort methods are correct. The outputs
should be correctly sorted. */
System.out.println("First, test that selection sort works on doubles.");
System.out.println("The 10 output numbers should be in increasing order.");
numberList1 = randomNumbers(10);
selectionSort(numberList1);
for (double n : numberList1)
System.out.println( " " + n );
System.out.println();
System.out.println("Next, test that selection sort works on strings.");
System.out.println("The 10 output strings should be in alphabetical order.");
System.out.println("(Also tests that random strings are made correctly.");
stringList1 = randomStrings(10);
selectionSort(stringList1);
for (String str : stringList1)
System.out.println( " " + str );
System.out.println();
System.out.println();
System.out.println("Times for sorting arrays of size " + SIZE + ":");
System.out.println();
/* Create the arrays. */
numberList1 = randomNumbers(SIZE);
numberList2 = Arrays.copyOf(numberList1, SIZE);
stringList1 = randomStrings(SIZE);
stringList2 = Arrays.copyOf(stringList1, SIZE);
/* Do the sorts and output the times. */
startTime = System.nanoTime();
selectionSort(numberList1);
endTime = System.nanoTime();
System.out.printf("Seconds to sort %d numbers with selectionSort: %1.6g%n",
SIZE, (endTime - startTime) / 1e9);
startTime = System.nanoTime();
Arrays.sort(numberList2);
endTime = System.nanoTime();
System.out.printf("Seconds to sort %d numbers with Arrays.sort(): %1.6g%n",
SIZE, (endTime - startTime) / 1e9);
startTime = System.nanoTime();
selectionSort(stringList1);
endTime = System.nanoTime();
System.out.printf("Seconds to sort %d strings with selectionSort: %1.6g%n",
SIZE, (endTime - startTime) / 1e9);
startTime = System.nanoTime();
Arrays.sort(stringList2);
endTime = System.nanoTime();
System.out.printf("Seconds to sort %d strings with Arrays.sort(): %1.6g%n",
SIZE, (endTime - startTime) / 1e9);
System.out.println();
}
}