Solution for Programming Exercise 7.5
This page contains a sample solution to one of the exercises from Introduction to Programming Using Java.
Exercise 7.5:
Write a program that will read a sequence of positive real numbers entered by the user and will print the same numbers in sorted order from smallest to largest. The user will input a zero to mark the end of the input. Assume that at most 100 positive numbers will be entered. Do not use any built-in function such as Arrays.sort(). Do the sorting yourself.
The sample program ReverseWithDynamicArray.java from Subsection 7.2.4 reads in up to 100 positive integers from the user and outputs them in the reverse of the order in which the user entered them. This is similar to what we have to do for this exercise, except that the numbers we have to read are real numbers (of type double) and they have to be output in sorted order.
There are two basic approaches to this problem. The first is to store all the numbers in an array in the order in which they are input. After all the numbers have been input, the array can be sorted, and then the contents of the array can be output. The second approach is to always keep the array in sorted order as numbers are added to it. When a new number is input, that number must be inserted into its correct location in the array, in order to keep the array sorted. After all the numbers have been input, the contents of the array are ready to be printed.
Two solutions to the exercise, based on these two approaches, are shown below. They use techniques for sorting and inserting that were covered in Section 7.4. In my first program, I've chosen to use Selection Sort to sort the array. Insertion Sort would work just as well. The Selection Sort subroutine is taken from Section 7.4 with two changes: It sorts an array of double values instead of an array of ints, and it has been modified to work with a "partially full" array. In order to make the subroutine work with a partially full array, it is necessary to add a parameter that tells the subroutine how many entries in the array are in use. The modified Selection Sort routine is as follows, with changes from the original version shown in red
static void selectionSort(double[] A, int count) { // Sort the numbers in A[0], A[1], ..., A[count-1] into // increasing order using Selection Sort. for ( int lastPlace = count - 1; lastPlace > 0; lastPlace-- ) { int maxLoc = 0; for (int j = 1; j <= lastPlace; j++) { if (A[j] > A[maxLoc]) { maxLoc = j; } } double temp = A[maxLoc]; A[maxLoc] = A[lastPlace]; A[lastPlace] = temp; } } // end selectionSort
In the first version of the program, this subroutine is called just after all the numbers have been input from the user.
The second version of the program is straightforward. It uses the insert() subroutine from Section 7.4, modified to work with an array of doubles instead of an array of ints.
First solution, with Selection Sort:
/**
* This program reads up to 100 positive integers from the user and
* prints them in sorted order. Input ends when the user enters a
* non-positive integer. The numbers are read and stored in an array.
* That array is sorted using selection sort, and then the array is
* printed.
*/
public class SortInputNumbers {
public static void main(String[] args) {
double[] numbers; // An array for storing the input values.
int numCt; // The number of numbers saved in the array.
double num; // One of the numbers input by the user.
numbers = new double[100]; // Space for 100 numbers.
numCt = 0; // No numbers have been saved yet.
System.out.println("Enter up to 100 positive numbers; Enter 0 to end");
while (true) { // Get the numbers and put them in the array.
System.out.print("? ");
num = TextIO.getlnDouble();
if (num <= 0)
break;
numbers[numCt] = num;
numCt++;
}
selectionSort(numbers, numCt); // Sort the numbers.
System.out.println("\nYour numbers in sorted order are:\n");
for (int i = 0; i < numCt; i++) {
System.out.println( numbers[i] );
}
} // end main();
/**
* Sort the numbers in A[0], A[1], ..., A[count-1] into
* increasing order using Selection Sort.
*/
static void selectionSort(double[] A, int count) {
for ( int lastPlace = count - 1; lastPlace > 0; lastPlace-- ) {
int maxLoc = 0;
for (int j = 1; j <= lastPlace; j++) {
if (A[j] > A[maxLoc]) {
maxLoc = j;
}
}
double temp = A[maxLoc];
A[maxLoc] = A[lastPlace];
A[lastPlace] = temp;
}
} // end selectionSort
} // end class SortInputNumbers
Second solution, with Insert:
/**
* This program reads up to 100 positive integers from the user and
* prints them in sorted order. Input ends when the user enters a
* non-positive integer. The numbers are read and inserted into
* an array. The array is maintained at all times in sorted order.
*/
public class SortInputNumbers2 {
public static void main(String[] args) {
double[] numbers; // An array for storing the input values.
int numCt; // The number of numbers saved in the array.
double num; // One of the numbers input by the user.
numbers = new double[100]; // Space for 100 numbers.
numCt = 0; // No numbers have been saved yet.
System.out.println("Enter up to 100 positive numbers; Enter 0 to end");
while (true) { // Get the numbers and insert them into the array.
System.out.print("? ");
num = TextIO.getlnDouble();
if (num <= 0)
break;
insert(numbers, numCt, num);
numCt++;
}
System.out.println("\nYour numbers in sorted order are:\n");
for (int i = 0; i < numCt; i++) {
System.out.println( numbers[i] );
}
} // end main();
/**
* Assume that A contains itemsInArray in increasing order.
* Insert newItem into its correct position in the sorted array.
*/
static void insert(double[] A, int itemsInArray, double newItem) {
int loc = itemsInArray - 1;
while (loc >= 0 && A[loc] > newItem) {
// Move the item from A[loc] up one space.
A[loc + 1] = A[loc];
loc = loc - 1;
}
A[loc + 1] = newItem; // Put newItem in the last vacated space.
} // end insert
} // end class SortInputNumbers2