Assignment 15

Task

Store and sort a list of user-entered integers.

Concepts: Review of arrays and loops.

Steps

Ask the user to enter a series of integers. Store these integers in an int[]. When you declare this array, give it an initial size of 5 elements. Each time you would exceed the current capacity of the array, instead replace the array with a new array of double the size.

When the user is done (indicated by entering nothing--as with A12), print on one line all the numbers they entered in sorted order: highest to lowest value.

Sample Output

This program will sort the numbers you enter.
Enter an integer (or nothing to stop): 0
Enter an integer (or nothing to stop): 12
Enter an integer (or nothing to stop): 5
Enter an integer (or nothing to stop): -2
Enter an integer (or nothing to stop): 12.5
Bad input: please enter only whole numbers (or, to quit, just hit enter).
Enter an integer (or nothing to stop): nothing
Bad input: please enter only whole numbers (or, to quit, just hit enter).
Enter an integer (or nothing to stop): 5
Enter an integer (or nothing to stop):

You entered: 12 5 5 0 -2

Sorting Hints

Note that sorting is worth only 1.0 points (which is equivalent to the late penalty), so worry about this last. Remember that you only need to print the numbers in sorted order, not necessarily get the array itself into that sorted order. Also, if you haven't filled your array to capacity, it will still contain 0s in the unused elements. So be careful not to sort these in among your real data.

Here are some different ideas on how you might achieve sorted output:

• Just load everything into the array in the order given by the user. Then, after the user is done, manually sort the array. This can be rather tricky: loop through the array list looking for the largest value. Once found, print that value and remove it from the list (so that you don't print it again). The fastest way to remove the element is to copy the last valid data element of your list into the "empty" spot and then decrement your count of data elements. Keep doing this until all values have been removed and printed:

    while (there are still elements in the list) {
      find the largest element in the list.  (This requires a loop and conditional)
      remove the largest element from the list and print it
    }
  

  This is a simple variation of the selection sort algorithm. You could also sort the array into a second array or even sort the elements in place within the array itself.
• Rather than trying to sort the array later, it's actually easier to just add each new item to the array in sorted order. Each time the user enters a number, search through the array to find where it should go. Shift right everything from that position onwards, and add the new item. When the user is done entering numbers, your array will already be sorted.
• Sorting a list seems like something someone might want to do pretty regularly. Perhaps there's something useful in the API that will do it for you? (Hint: java.util.Arrays; remember again that your array may not always be full, so you may need to sort only a subset of it.)

What to Submit

Upload your UsernameA15.java file to Tamarin.

Grading [5 points]

1 - Compiles + Coding Standards

Your program compiles successfully (no errors). Your code follows Java coding standards.

1.5 - Array

Your program uses an int[] to store the numbers read in from the user (0.5). You initially declare this array to be of size 5 (0.5). You double its size (and copy over all elements) each time the array capacity is exceeded (0.5).

1.5 - Input/Output

Your program prompts the user to enter integers, stopping if the user enters nothing (empty string) (0.5). Your program ignores bad input and prompts the user again (0.5). Your program then prints out a list on one line of all the numbers the user entered (0.5).

1 - Correctly sorted.

When the program prints out the entered numbers, they are in sorted order, from highest to lowest value.

FAQs

Demo code?

Here are two different versions of the same basic thing:

• ToDoListMain.java
• ToDoList.java

Both of them use an array (called todo) to store data entered by the user. To do this effectively, another variable (count) is used to designate how many elements in that array are actually entries given by the user.

The first program (ToDoListMain) does everything in the main method. (This is the example we did on Thursday in Sections 001 & 003.) Most of the program is user-input details; the array manipulations are only on a couple lines here and there.

The second program (ToDoList) makes the ToDoList its own object. This takes a bit more code to do, so the advantage of doing it this way is probably not obvious at first. Some advantages would be:

• I can now create multiple, separate ToDoLists very easily. Suppose I wanted to expand this program to a tabbed GUI with a different ToDoList in each tab. This would be much easier to do starting with ToDoList instead of ToDoListMain.
• The details of ToDoList are encapsulated. For example, the code in the main method cannot accidently change count separately from the contents of todo, which reduces the chance of bugs. Also, I could change how the ToDoList is implemented (such as switch it to using an ArrayList instead of an int[] array) and code in main would not be affected. Encapulation becomes important in larger projects.
• ToDoList is more reusable. I could reuse the whole class in another program. I could also call the methods from multiple locations within the same program. For example, if I needed to print out the list in two different places in the code of ToDoListMain, I'd have to write two different for loops (and such duplicated code is a frequent source of bugs). With ToDoList, I can just call the toString() method with one line from each of the two locations where I need to print the list.

Hopefully seeing the same program in both a procedural and OOP (object-oriented programming) forms will help you come to grips with OOP, which we will return to next week. However, since the focus of this assignment in on working with arrays, you are not required to use an OOP approach; you may just have everything in main if you want to.

Something to consider

Imagine trying to do this assignment without arrays, but only with a number of int variables. First, sorting would be a nightmare (remember dealing with only 3 numbers in A06?), especially since you wouldn't be able to use a loop to traverse a series of separate variables. Secondly, you would be limited by the numbers of variables you defined. To handle a list of 10 numbers, you'd have to declare 10 variables, and (unlike arrays) there'd be no way to change this limit while the program is running.

Argh, I'm stuck! How do I add the numbers to the array? How do I "double the size of the array"?

Here's a summary. (The grey /* comments */ refer to code you'll have to figure out on your own, which may take multiple lines.)

  int nums = new int[5];
  int count = 0;  //tracks how many numbers have been added to nums

  /* while user keeps entering numbers */
    int number = /* user's entered number */

    if (count == nums.length) {
      //nums array is full, so we need to double it's size
      int temp[] = new int[nums.length * 2];  //larger temporary array
      /* copy each value from nums into temp */
      nums = temp;  //replace nums with larger temp array
    }
    //add number to the end of nums
    nums[count] = number;
    count++;
  /* end while */

  /* print entered numbers */

Note that this code does not handle the sorting yet.

My numbers are coming out as all 0s (or maybe with only the last number entered).

Be sure you declare your nums array before the input loop, or else it'll get recreated each time through the loop. Make sure you actually copy the user's input into the array at some point. Also, if this only happens when you enter more than 5 numbers, make sure you copied everything over correctly when doubling the size of the array.

My numbers always include extra 0s at the end, unless I enter exactly 5 numbers.

Sounds like you're printing out the whole array (nums.length, or similar) rather than only those numbers you entered (as recorded in your count variable). In your printing loop, loop only up to count, not to nums.length.

If the 0s only show up after you sort (but not if you print out the array before sorting it), then see the next FAQ.

If I enter a negative number, my sorted output includes a bunch of extra 0s.

Sounds like you confused nums.length and count while sorting. (This is can also happen when you print the array, as explained above.) For example, imagine you've entered 6 numbers and so your array looks like this:

 [7 12 -3 4 7 -1 | 0 0 0 0]

The '|' marks where count is. If you sort the entire array, it'll then look like this:

 [12 7 7 4 0 0 | 0 0 -1 -3 ]

Thus, when you print out the first count numbers, you'll have "lost" some of them.

Instead, you want to sort only up to count, not to nums.length. (If you wrote a separate method to do your sorting, you'll need to pass in a second parameter with this value of how many numbers to sort.) Thus, you should get this:

 [12 7 7 4 -1 -3 | 0 0 0 0 ]

Couldn't I just use Arrays.copyOf to increase the size of the array?

Theoretically, yes. But please don't do it. Tamarin is using Java 1.5, but the copyOf method was added in Java 1.6. (You can find this out by clicking on the method name in the API and going to the full description. It will then list "Since", which is the version of Java at which the method was added. Remember that Java 1.6 == Java 6.) So, if you use this method, your code will not compile when you submit it. Besides, you could probably use more practice with for loops anyway!