Collections

Exercises

1. We'll start, as usual, by running the lablet and watching it in its current working condition. Then, we'll play around with it to illustrate some common mistakes in dealing with arrays and loops.
   Compile and run Sortmeister now. Click on the applet's "Reset" button to load new integer values, and then sort them by clicking "Sort." You can determine which sorting algorithm is used by choosing either "Selection" or "Shell" from the choice box provided.
   
   
2. The lablet makes extensive use of arrays and loops, in almost all phases of its processing. Let's focus on these features as we introduce some errors into the applet. Some of the changes listed below will result in compiler errors. Others will not keep the applet from compiling, but will cause it to run differently or incorrectly. Make each of these changes to the original version of Sortmeister, and then record what happens when you try to compile and run the revised applet.
   
   
   1. In the data declarations at the start of the Sortmeister class, change the line
      private int data[];
      to
      private int data;
      Answer:
      
      
      
   2. In the init() method, change the line
      data = new int[SIZE];
      to
      data = new int[];
      Answer:
      
      
      
   3. Change the header of the shuffle() method from
      private void shuffle(int[] a)
      to
      private void shuffle(int a)
      Answer:
      
      
      
   4. In the shuffle() method, change the first for loop header from
      for (int i = 0; i < a.length; i++)
      to
      for (int i = 0; i <= a.length; i++)
      Answer:
      
      
      
   5. In the same line, change the loop header from
      for (int i = 0; i < a.length; i++)
      to
      for (int i = 0; i < a.length; )
      Answer:
      
      
      
   6. In the next loop in shuffle(), change the header from
      for (int i = 0; i < a.length - 1; i++)
      to
      for (i = 0; i < a.length - 1; i++)
      Answer:
      
      
      
3. Now that we've investigated some of the syntax and semantics of arrays and loops, let's take a closer look at how the sorting routines work.
   
   
   1. In the shuffle() method, we spend most of the time swapping array elements, using the code

         int temp = a[i];
         a[i] = a[index];
         a[index] = temp;
      

      What happens when we replace that swapping code with this simpler version?

         a[i] = a[index];
         a[index] = a[i];
      

      Answer:
      
      
      
   2. In selectionSort(), we encounter a very common programming idiom, using a linear search through the array, from position i + 1 to the end of the array, recording the position of the smallest array element in the local variable minPos.
      
      
      1. What happens if we change the search region, by replacing the line
         for (int j = i + 1; j < a.length; j++)
         to
         for (int j = i + 2; j < a.length; j++)
         Answer:
         
         
         
      2. What happens when we change the line
         minPos = j;
         to
         minPos = i;
         Answer:
         
         
         
      3. What happens when we change the line
         if (a[j] < a[minPos])
         to
         if (a[j] > a[minPos])
         Answer:
         
         
         
   3. While we're looking at selectionSort(), let's see what the purpose of stall() is, by commenting out all three of those method calls. What happens?
      Answer:
      
      
      
   4. The insertionSort() method is used by shellSort(). It uses an outer loop to "walk" the current position, i, upward through the array and uses an inner loop to walk a position j downwards through the array, in increments of the step size k, to place the current element where it belongs.
      
      
      1. There are two conditions that control the inner loop, index >= k and
         currentValue < a[index - k]. What is the purpose of each?
         

         Answer:

         
         
      2. Inside the inner loop, we have two statements,

            a[index] = a[index - k];
            index -= k;
         

         What is the purpose of each?
         

         Answer:

         
         
   5. shellSort(), sometimes called diminishing increment sort, uses several calls to insertionSort() to partially sort the array. Let's see what happens when we change the increments.
      
      
      1. What happens when we change the first increment, by changing
         int increment = a.length / 2;
         to
         int increment = a.length / 4;
         Answer:
         
         
         
      2. What happens when we eliminate the last increment, by changing
         while (increment >= 1)
         to
         while (increment > 1)
         Answer:
         
         
         
4. The Display class describes an object, derived from Canvas, where the sorting animation takes place. When the display needs to be updated, the applet calls display.draw() (from its stall() method), which forces a call to display's paint() method. This draws a collection of lines, one for each data element, with width proportional to the value of the data.
   
   
   1. The default update() method, as you know, erases everything and then calls paint(). We've overridden the default update() method, eliminating the erasing step. Why don't we do the erasing? Comment out the entire update() method and run the applet. What happens?
      Answer:
      
      
      
   2. In the paint() method, we begin by establishing the vertical distance between lines (unitY) and the amount corresponding to a single unit of the data (unitX).
      
      
      1. What happens when you change the line
         int unitY = size.height / data.length;
         to
         int unitY = 2;
         Answer:
         
         
         
      2. What happens when you change the line
         double unitX = (size.width - 2.0 * INSET) / data.length;
         to
         double unitX = 1.0;
         Answer:
         
         
         
      3. Comment out the lines

            g.setColor(getBackground();
            g.drawLine(INSET, y, INSET + (int)(unitX * data.length), y);
         

         What happens?
         Answer:
         
         
         
5. Here are some relatively straightforward changes to the program--that is, they can be made without disrupting the structure of the original applet. Try them one at a time, Compile and run your revised applet to test them out.
   
   
   1. Change the applet so that sorting (using either algorithm) sorts the data in descending (as opposed to ascending) order.
      
      
   2. There are two places in the applet where we swap array elements. Any time we have duplicated code, the first thing we should think of is the possibility of "factoring out" the code into a separate method. Write a method private swap(int[] a, int i, int j) that will swap the values a[i] and a[j], and replace the swapping code in methods shuffle() and selectionSort() with appropriate calls to swap().
      
      
   3. If we call insertionSort(a, 1), we will sort the array a using "ordinary" insertion sort. Add this new sorting method to your applet, so that the user can choose "Selection," "Insertion," or "Shell" as a sorting method.
      
      
      
6. The extensions below are a bit more adventurous than those above in that they involve changes to both the algorithms and the user interface of the lablet. Try these one at a time, and run your revised applet to test them out.
   
   
   1. Add a timer to your applet, so that it records the time it took to do the sorting and displays the result in a TextField at the bottom, like this:
      
      
      To do this, you'll need the Date class in the java.util package (which, of course, you'll need to import). In the doSort() method, you'll add the following code:

      Date start = new Date();            // Make a new Date object for the current time.
      long startTime = start.getTime();   // Get the current time, in miliseconds.
         
      // Do the sorting, using the existing code.
         
      Date finish = new Date();           // Make another Date object for this time.
      long elapsed = finish.getTime() - startTime;
      // Display the elapsed time in your TextField
      

   2. Change the Display class, so that it displays the data as a collection of dots, rather than a collection of lines. In this new version, the dots corresponding to the array elements will be arranged from left to right, rather than from top to bottom, and the height of each dot will be proportional to the value of the array element itself.
      For example, the picture at the right is a reduced view of what the display would look like, partially through the selection sort algorithm.
      
      
      
   3. Add another sorting algorithm to the list of available sorts, and (of course) implement the algorithm. Look up any existing sorting algorithm (like, for instance, Bubble Sort), or develop one of your own.

      Note: if you can find it, watch the video "Sorting Out Sorting." This is a delightful in-depth look at various sorting algorithms.