ITEC 120 2009spring ibarland nokie jmdymacek

home—info—lects—labs—exams—hws
textbook—tutor/PIs—java.lang docs—java.util docs

lect13b
selection sort

We will discuss how to sort an array of doubles. In particular, we'll use an algorithm called “selection sort” so that we can write it in-place.

Working through this by hand, we realize that a handy helper-function would be indexMin; we already wrote the essentially-similar method indexMax earlier.
As we step through our program, we realize that indexMin isn't acutally quite what we want; we don't want the (index of the) minimum of the entire array, but only from location i onward.

It is left to the reader to write indexMinFrom( int[] data, int startFrom ). (This is a good self-check; try writing the method on your own, and come by office hours if you want feedback on what you did. Writing indexMinFrom might make a fine exam problem!) Note that you will not need to come up with this sorting algorithm on your own, but you do need to be able to see the code and understand how it works.

Here is a version using while:

    void selectSort( double[] nums ) {
        int i = 0;
        while (i < nums.length) {
            int indexOfMin = indexMinFrom(nums,i);

            // Now, swap nums[i] with nums[indexOfMin]:
            int tmp = nums[i];
            nums[i] = nums[indexOfMin];
            nums[indexOfMin] = tmp;

            ++i;
        }
    }

    void selectSort( double[] nums ) {
        for ( int i=0;  i < nums.length;  ++i ) {
            int indexOfMin = indexMinFrom(nums,i);

            // Now, swap nums[i] with nums[indexOfMin]:
            int tmp = nums[i];
            nums[i] = nums[indexOfMin];
            nums[indexOfMin] = tmp;
        }
    }

    void selectSort( double[] nums ) {
        for ( int i=0;  i < nums.length;  ++i ) {
            int indexOfMin = indexMinFrom(nums,i);
            swap( nums, i, indexOfMin );
        }
    }

a visualization. Note the code they have: what we did as indexMinFrom is in-lined as a nested loop. (Their variable k corresponds to the so-far variable inside indexMinFrom.)

Two-dimensional arrays

Not covered in class — Well, we just flashed up the picture and talked about it for 3min. We will cover it in lab tomorrow.

We can have arrays of any type, in Java. We've seen, say, array-of-double (double[]). But we might also have array-of-array-of-double (double[][]). We call this a two-dimensional array.

• When to use: to represent a grid — think of a picture, or a map.

  For example: This might be a topographical map of elevations (with a butte near the center-north):

  +----+----+----+----+----+----+----+
  | 22 | 17 | 83 | 80 | 63 | 15 | 10 |
  +----+----+----+----+----+----+----+
  | 19 | 11 | 88 | 72 | 42 | 14 | 14 |
  +----+----+----+----+----+----+----+
  |  8 | 10 | 13 | 52 | 12 | 13 | 12 |
  +----+----+----+----+----+----+----+
  | 10 | 11 | 15 | 18 | 13 | 15 | 10 |
  +----+----+----+----+----+----+----+
  

• How to declare;

  int[][] elevation; elevation = new elevation[4][7]; // #rows, then #columns.

• Draw the memory diagram:

                                           int[] 0    1    2    3    4    5    6
                                              +----+----+----+----+----+----+----+
                                       /----->| 22 | 17 | 83 | 80 | 63 | 15 | 10 |
                                       |      +----+----+----+----+----+----+----+
            +------+                   |
  elevation |  *---|--\                |   int[] 0    1    2    3    4    5    6
            +------+  |     int[][]    |      +----+----+----+----+----+----+----+
                      \---->+-----+    |  /-->| 19 | 11 | 88 | 72 | 42 | 14 | 14 |
                           0| *---|----/  |   +----+----+----+----+----+----+----+
                            +-----+       |
                           1| *---|-------/int[] 0    1    2    3    4    5    6
                            +-----+           +----+----+----+----+----+----+----+
                           2| *---|---------->|  8 | 10 | 13 | 52 | 12 | 13 | 12 |
                            +-----+           +----+----+----+----+----+----+----+
                           3| *---|-----\
                            +-----+     |  int[] 0    1    2    3    4    5    6
                                        |     +----+----+----+----+----+----+----+
                                        \---->| 10 | 11 | 15 | 18 | 13 | 15 | 10 |
                                              +----+----+----+----+----+----+----+
  

  (Even though we'll think of elevation as a grid, the diagram reveals that it is really an array-of-arrays. Some languages do have “true” 2-D arrays, but array-of-array simply uses pre-existing concepts.)
• Consider the number 52, in the above array.
  Which row is it in? (0-based)
  Which column is it in? (0-based)
  Thus we access it by saying elevation[2][3].
• How to initialize (Say: elevation[i][j] = i*j)

  for ( int row=0; row < elevation.length; ++row) { for ( int col=0; col < elevation[row].length; ++col ) { elevation[i][j] = i*j; } }

• Note that Java has some nice syntax for initializing arrays :

  int[] rowZero = { 22, 17, 83, 80, 63, 15, 10 };

  (“Oh great, now you tell us that, after we wrote a bunch of code to initialize arrays from the keyboard!”)

  These array-literals naturally extend to two-dimensional arrays, so we could have written:

  int[][] elevation = { { 22, 17, 83, 80, 63, 15, 10 } { 19, 11, 88, 72, 42, 14, 14 } { 8, 10, 13, 52, 12, 13, 12 } { 10, 11, 15, 80, 13, 15, 10 } };

  (Hey, this makes our code a clear reflection of our data — cool!)

  (These are called “array literals”, just like mentioning 17 in your program is an int literal, and mentioning "hello" is a string literal.)

The book gives an example 2-D arrays to show a tic-tac-toe board in §7.6.

home—info—lects—labs—exams—hws
textbook—tutor/PIs—java.lang docs—java.util docs

©2009, Ian Barland, Radford University Last modified 2009.Apr.23 (Thu)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu