Solution for
Programming Exercise 8.2
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.
Exercise 8.2:
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.
Discussion
The sample program ReverseWithDynamicArray.java
from Section 8.3 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 8.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 8.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 8.4, modified to
work with an array of doubles instead of an array of
ints.
The Solution
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 Test {
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.
TextIO.putln("Enter up to 100 positive numbers; Enter 0 to end");
while (true) { // Get the numbers and put them in the array.
TextIO.put("? ");
num = TextIO.getlnDouble();
if (num <= 0)
break;
numbers[numCt] = num;
numCt++;
}
selectionSort(numbers, numCt); // Sort the numbers.
TextIO.putln("\nYour numbers in sorted order are:\n");
for (int i = 0; i < numCt; i++) {
TextIO.putln( numbers[i] );
}
} // end main();
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
} // 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 Test {
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.
TextIO.putln("Enter up to 100 positive numbers; Enter 0 to end");
while (true) { // Get the numbers and insert them into the array.
TextIO.put("? ");
num = TextIO.getlnDouble();
if (num <= 0)
break;
insert(numbers, numCt, num);
numCt++;
}
TextIO.putln("\nYour numbers in sorted order are:\n");
for (int i = 0; i < numCt; i++) {
TextIO.putln( numbers[i] );
}
} // end main();
static void insert(double[] A, int itemsInArray, double newItem) {
// Assume that A contains itemsInArray in increasing order.
// Insert newItem into its correct position in the sorted array.
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 SortInputNumbers
[ Exercises
| Chapter Index
| Main Index
]
