Featured White Papers

• Measuring Risk to Improve Java Software Quality
• Do You Really Get Classloaders?
• Pragmatic Continuous Delivery with Jenkins, Nexus, and LiveRebel
• Your Next Java Web App: Less XML, No Long Restarts, Fewer Hassles
• Coding with JRebel, Java Forever Changed
• 2012 Developer Productivity Report: Java Tools, Tech, Devs, and Data

Sponsored Links

• Graph databases are 1000x faster than relational.

  Learn More!

• Career opportunities at Harman- Careers That'll Rock Your Socks Off.

  Learn More!

• Developer-friendly Java PDF libraries by Qoppa Software

  Live Demos

• Stop blaming your app! Diagnose Java performance issues.

  Free tool >

• UrbanCode: Go From Continuous Integration to
  Continuous Delivery

  Learn More!

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

Datastructures and algorithms, Part 1

Explore datastructures, algorithms, flowcharts, pseudocode, and arrays

By Jeff Friesen, JavaWorld.com, 05/02/03

Page 6 of 7

DECLARE INTEGER x [] = [ -5, 12, 15, 20, 30, 72, 456 ]
DECLARE INTEGER loIndex = 0
DECLARE INTEGER hiIndex = LENGTH (x) - 1
DECLARE INTEGER midIndex, srch = 72
WHILE loIndex <= hiIndex
   midIndex = (loIndex + hiIndex) / 2
   IF srch > x [midIndex] THEN
      loIndex = midIndex + 1
   ELSE
   IF srch < x [midIndex] THEN
      hiIndex = midIndex - 1
   ELSE
      EXIT WHILE
   END IF
END WHILE
IF loIndex > hiIndex THEN
   PRINT srch, " not found"
ELSE
   PRINT srch, " found"
END IF
END            

Listing 2 presents the Java equivalent to the pseudocode above:

Listing 2. BSearchDemo.java

// BSearchDemo.java
class BSearchDemo
{
   public static void main (String [] args)
   {
      int [] x = { -5, 12, 15, 20, 30, 72, 456 };
      int loIndex = 0;
      int hiIndex = x.length - 1;
      int midIndex, srch = 72;
      while (loIndex <= hiIndex)
      {
         midIndex = (loIndex + hiIndex) / 2;
         if (srch > x [midIndex])
             loIndex = midIndex + 1;
         else
         if (srch < x [midIndex])
             hiIndex = midIndex - 1;
         else
             break;
      }
      if (loIndex > hiIndex)
          System.out.println (srch + " not found");
      else
          System.out.println (srch + " found");
   }
}

BSearchDemo produces the following output:

72 found

Binary-search's sole advantage is the reduced time spent examining elements. The maximum number of elements to examine is log2n (where n is the one-dimensional array's length). For example, a one-dimensional array with 1,048,576 elements requires binary-search to examine a maximum of 20 elements. Binary-search's two disadvantages are increased complexity and the need to presort the one-dimensional array.

When it comes to sorting data items, bubble-sort is one of the simplest algorithms. The bubble-sort algorithm makes various passes over a one-dimensional array. For each pass, that algorithm compares adjacent data items to determine which is numerically larger or smaller. Either the larger data item (for ascending order) or the smaller data item (for descending order) swaps with the adjacent data item and moves toward the bottom of the one-dimensional array. By the end of the pass, the largest/smallest data item has moved toward the array's end. This "bubbling" effect is the origin of the bubble-sort algorithm's name. The following pseudocode demonstrates this algorithm (in an ascending sort context):

DECLARE INTEGER i, pass
DECLARE INTEGER x [] = [ 20, 15, 12, 30, -5, 72, 456 ]
FOR pass = 0 TO LENGTH (x) - 2
    FOR i = 0 TO LENGTH (x) - pass - 2
        IF x [i] > x [i + 1] THEN
           SWAP x [i], x [i + 1]
        END IF
    NEXT i
NEXT pass
END

Figure 5 illustrates bubble-sort placing a four-element one-dimensional array into ascending order. There are three passes: pass 0 performs three compares and two swaps, pass 1 performs two compares and one swap, and pass 2 performs one compare and one swap.

Listing 3 presents the Java equivalent to the pseudocode above:

Listing 3. BSortDemo.java

// BSortDemo.java
class BSortDemo
{
   public static void main (String [] args)
   {
      int i, pass;
      int [] x = { 20, 15, 12, 30, -5, 72, 456 };
      for (pass = 0; pass < = x.length - 2; pass++)
           for (i = 0; i < = x.length - pass - 2; i++)
                if (x [i] >  x [i + 1])
                {
                    int temp = x [i];
                    x [i] = x [i + 1];
                    x [i + 1] = temp;
                }
      for (i = 0; i <  x.length; i++)
           System.out.println (x [i]);
   }
}

BSortDemo produces the following output:

 -5
12
15
20
30
72
456

Although bubble-sort is one of the simplest sorting algorithms, it's also one of the slowest. Faster algorithms include quick-sort and heap-sort. Examine a computer science textbook to learn more about those sorting algorithms.

Two-dimensional arrays

A two-dimensional array, also known as a table or a matrix, where each element associates with a pair of indexes, is another simple array. We conceptualize a two-dimensional array as a rectangular grid of elements divided into rows and columns, and we use the (row, column) notation to identify a specific element. Figure 6 illustrates this conceptual view and the element-specifying notation.

Java provides three techniques for creating a two-dimensional array: use only an initializer, use only keyword new, and use keyword new with an initializer.

Use only an initializer to create a two-dimensional array. That technique requires either of the following syntaxes:

type variable_name '[' ']' '[' ']' '=' 
    '{' [ rowInitializer [ ',' ... ] ] '}' ';'
type '[' ']' '[' ']' variable_name '=' 
    '{' [ rowInitializer [ ',' ... ] ] '}' ';'

where rowInitializer has the following syntax:

'{' [ initial_value [ ',' ... ] ] '}'

Either syntax:

• Specifies variable_name as the name of the two-dimensional array variable.
• Specifies type as the type of each element. Because the two-dimensional array variable holds a reference to the two-dimensional array, the variable's type is type [ ] [ ].
• Specifies zero or more row initializers between a pair of brace characters ({ }). If no row initializers are specified, the two-dimensional array is empty. Each row initializer specifies zero or more initial values for that row's column entries. If no initial values are specified for that row, the row is empty.
• Specifies = to assign the two-dimensional array's reference to variable_name.

The following code fragment uses only an initializer to create a two-dimensional array that stores data items based on a primitive type:

double [][] temperatures = { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }; // Celsius temperatures

double [][] temperatures declares a two-dimensional array variable (temperatures) along with that variable's type (double [][]). The double [][] reference type signifies that each element must contain a data item of the double-precision floating-point primitive type. { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } } specifies a two-row by three-column two-dimensional array, where the first row contains column data items 20.5, 30.6, and 28.3, and the second row contains column data items -38.7, -18.3, and -16.2. Behind the scenes, memory is allocated and initialized to those data items. Operator equal-to assigns the two-dimensional array's reference to temperatures. Figure 7 illustrates the resulting two-dimensional array from a conceptual and memory view.

Use only keyword new to create a two-dimensional array. That technique requires either of the following syntaxes:

type variable_name '[' ']' '[' ']' '=' 
    'new' type '[' integer_expression ']' '[' ']' ';'
type '[' ']' '[' ']' variable_name '=' 
    'new' type '[' integer_expression ']' '[' ']' ';'

Either syntax:

• Specifies variable_name as the name of the two-dimensional array variable.
• Specifies type as the type of each element. Because the two-dimensional array variable holds a reference to the two-dimensional array, the variable's type is type [ ] [ ].
• Specifies keyword new, followed by type, followed by integer_expression between square brackets, which identifies the number of row elements. new allocates memory for a one-dimensional row array and zeroes all bits in each element's bytes, which means that each element contains a null reference. You must create a separate one-dimensional column array and assign its reference to each row element.
• Specifies = to assign the two-dimensional array's reference to variable_name.

The following code fragment uses only keyword new to create a two-dimensional array that stores data items based on a primitive type:

double [][] temperatures = new double [2][]; // Allocate two rows.
temperatures [0] = new double [3]; // Allocate three columns for row 0
temperatures [1] = new double [3]; // Alllocate three columns for row 1
temperatures [0][0] = 20.5; // Populate row 0
temperatures [0][1] = 30.6;
temperatures [0][2] = 28.3;
temperatures [1][0] = -38.7; // Populate row 1
temperatures [1][1] = -18.3;
temperatures [1][2] = -16.2;

Use keyword new with an initializer to create a two-dimensional array. That technique requires either of the following syntaxes:

type variable_name '[' ']' '[' ']' '=' 
    'new' type '[' ']' '[' ']' '{' [ rowInitializer [ ',' ... ] ] '}' ';'
type '[' ']' '[' ']' variable_name '=' 
    'new' type '[' ']' '[' ']' '{' [ rowInitializer [ ',' ... ] ] '}' ';'

where rowInitializer has the following syntax:

'{' [ initial_value [ ',' ... ] ] '}'

Either syntax:

• Specifies variable_name as the name of the two-dimensional array variable.
• Specifies type as the type of each element. Because the two-dimensional array variable holds a reference to the two-dimensional array, the variable's type is type [ ] [ ].
• Specifies keyword new, followed by type, followed by two pairs of empty square brackets, followed by zero or more row initializers between a pair of brace characters. If no row initializers are specified, the two-dimensional array is empty. Each row initializer specifies zero or more initial values for that row's column entries. If no initial values are specified for that row, the row is empty.
• Specifies = to assign the two-dimensional array's reference to variable_name.

The following code fragment uses keyword new with an initializer to create a two-dimensional array that stores data items based on a primitive type:

double [][] temperatures = new double [][] { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } };

The code fragment above behaves identically to the earlier double [][] temperatures = new double [][] { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }; code fragment.

After you create a two-dimensional array, store and retrieve data items in its elements. Accomplish that task with the syntax below:

variable_name '[' integer_expression1 ']' '[' integer_expression2 ']'

integer_expression1 identifies an element's row index and ranges from 0 to one less than the two-dimensional array's length, which variable_name.length returns. Similarly, integer_expression2 identifies an element's column index and ranges from 0 to one less than the length of any row. Because all rows have the same length, you might find it convenient to specify variable_name [0].length to return the number of columns for any row. The following code fragment stores a data item to and retrieves a data item from a two-dimensional array element:

double [][] temperatures = { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } };
temperatures [0][1] = 18.3; // Replace 30.6 with 18.3
System.out.println (temperatures [1][2]); // Output: -16.2

Matrix-multiplication algorithm

Multiplying one matrix by a second matrix is a common operation in fields ranging from computer graphics, to economics, to the transportation industry. Developers usually use the matrix-multiplication algorithm to complete that multiplication. How does that algorithm work? Let A represent a matrix with m rows and p columns. Similarly, let B represent a matrix with p rows and n columns. Multiply A by B to produce a matrix C, with m rows and n columns, where each c_ij entry in C is obtained by multiplying all entries in A's ith row by corresponding entries in B's jth column and adding the results. Figure 8 illustrates those operations.

The following pseudocode demonstrates the matrix-multiplication algorithm:

// ==      ==   == ==   ==                     ==
// | 10  30 |   | 5 |   | 10 x 5 + 30 x 7 (260) |
// |        | X |   | = |                       | 
// | 20  40 |   | 7 |   | 20 x 5 + 40 * 7 (380) | 
// ==      ==   == ==   ==                     ==
DECLARE INTEGER a [][] = [ 10, 30 ] [ 20, 40 ]
DECLARE INTEGER b [][] =  [ 5, 7 ]
DECLARE INTEGER m = 2 // Number of rows in left matrix (a)
DECLARE INTEGER p = 2 // Number of columns in left matrix (a)
                      // Number of rows in right matrix (b)
DECLARE INTEGER n = 1 // Number of columns in right matrix (b)
// Note: cs1 must equal rs2
DECLARE INTEGER c [m][n] // c holds 2 rows by 1 columns
                         // All elements initialize to 0
FOR i = 0 TO m - 1
    FOR j = 0 TO n - 1
        FOR k = 0 TO p - 1
            c [i][j] = c [i][j] + a [i][k] * b [k][j]
        NEXT k
    NEXT j
NEXT i

The pseudocode above requires three FOR loops to perform the multiplication. The innermost FOR loop multiplies a single row in matrix A with a single column in matrix B and adds the result to a single entry in matrix C (as Figure 8 illustrates). Listing 4 presents the Java equivalent to that pseudocode:

Listing 4. MatMultDemo.java

// MatMultDemo.java
class MatMultDemo
{
   public static void main (String [] args)
   {
      int [][] a = {{ 10, 30 }, { 20, 40 }};
      int [][] b = {{ 5 }, { 7 }};
      dump (a);
      System.out.println ();
      dump (b);
      System.out.println ();
      int [][] c = multiply (a, b);
      dump (c);
   }
   static void dump (int [][] x)
   {
      if (x == null)
      {
          System.err.println ("array is null");
          return;
      }
      // Dump the matrix's element values to the standard output device
      // in a tabular order
      for (int i = 0; i < x.length; i++)
      {
           for (int j = 0; j < x [0].length; j++)
                System.out.print (x [i][j] + " ");
           System.out.println ();
      }
   }
   static int [][] multiply (int [][] a, int [][] b)
   {
      // =========================================================
      // 1. a.length contains a's row count
      //
      // 2. a [0].length (or any other a [x].length for a valid x)
      //    contains a's column count
      //
      // 3. b.length contains b's row count
      //
      // 4. b [0].length (or any other b [x].length for a valid x)
      //    contains b's column count
      // =========================================================
      // If a's column count != b's row count, bail out
      if (a [0].length != b.length)
      {
          System.err.println ("a's column count != b's row count");
          return null;
      }
      // Allocate result matrix with a size equal to a's row count x b's
      // column count
      int [][] result = new int [a.length][];
      for (int i = 0; i < result.length; i++)
           result [i] = new int [b [0].length];
      // Perform the multiplication and addition
      for (int i = 0; i < a.length; i++)
           for (int j = 0; j < b [0].length; j++)
                for (int k = 0; k < a [0].length; k++) // Or k < b.length
                     result [i][j] += a [i][k] * b [k][j];
      // Return the result matrix
      return result;
   }
}

MatMultDemo produces the following output:

10 30 
20 40 
5 
7 
260 
380 

Let's explore a problem where matrix-multiplication is needed to obtain a solution. A fruit grower in Florida loads a couple of semitrailers with 1,250 boxes of oranges, 400 boxes of peaches, and 250 boxes of grapefruit. A chart of market prices, on a per-box basis, for each kind of fruit in four different cities appears in Figure 9.

To obtain maximum gross income, to which city should the fruit grower send the semitrailers? To solve that problem, first consider Figure 9's chart as a four-row by three-column price matrix. We then construct a three-row by one-column quantity matrix, which appears below:

==    ==
| 1250 |
|      |
|  400 |
|      |
|  250 | 
==    ==

Now that we have both matrices, we simply multiply the price matrix by the quantity matrix to produce a gross income matrix:

==                  ==              ==        ==
| 10.00  8.00  12.00 |   ==    ==   | 18700.00 | New York
|                    |   | 1250 |   |          |
| 11.00  8.50  11.55 |   |      |   | 20037.50 | Los Angeles
|                    | X |  400 | = |          |
|  8.75  6.90  10.00 |   |      |   | 16197.50 | Miami 
|                    |   |  250 |   |          |
| 10.50  8.25  11.75 |   ==    ==   | 19362.50 | Chicago
==                  ==              ==        ==

Sending both semitrailers to Los Angeles produces the highest gross income. But when distance and fuel costs are considered, perhaps New York is a better bet for yielding the highest net income.

Ragged arrays

Suppose your source code contains the following matrix declaration: int [][] x = new int [5][];. The declaration yields an integer matrix that contains five rows, and x.length returns that row count. Normally, you complete that matrix's creation by specifying the same number of column elements for each row. For example, specify 10 columns for each row via the following code fragment:

for (int i = 0; i < x.length; i++)
     x [i] = new int [10];

In contrast to many computer languages, Java does not force you to specify the same number of columns for each row. Using the previous code fragment, assign three columns to row 0, two columns to row 1, three columns to row 2, five columns to row 3, and one column to row 4; which the following code fragment demonstrates: