Recursion - Advanced Topics in Java: Core Concepts in Data Structures - page 154

for (j = 0; j < hi-lo+1; j++) A[lo + j] = T[j];
} //end merge

} //end class MergeSortTest

When run, the program produces the following output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

In passing, we note that merge sort is a much faster sorting method than either selection sort or insertion sort.

5.8 Counting Organisms
Consider the following arrangement:

0 1 0 1 1 1 0
0 0 1 1 0 0 0
1 1 0 1 0 0 1
1 0 1 0 0 1 1
1 1 0 0 0 1 0

Assume that each 1 represents a cell of an organism; 0 means there is no cell. Two cells are contiguous if they are
next to each other in the same row or same column. An organism is defined as follows:

• An organism contains at least one

1 .

1 s belong to the same organism.
There are five organisms in the arrangement shown. Count them!
Given an arrangement of cells in a grid, we want to write a program to count the number of organisms present.
A glance at the grid will reveal that, given a cell ( 1 ), the organism can extend in either of four directions. For
each of these, it can extend in either of four directions, giving 16 possibilities. Each of these gives rise to four more
possibilities, and so on. How do we keep track of all these possibilities, knowing which have been explored and which
are still waiting to be explored?
The easiest way to do this is to let the recursive mechanism keep track for us.
To count the number of organisms, we need a way to determine which cells belong to an organism. To begin, we
must find a 1 . Next, we must find all 1 s that are contiguous to this 1 , then 1 s that are contiguous to those, and so on.
To find contiguous 1 s, we must look in four directions—north, east, south, and west (in any order). When we look,
there are four possibilities:

• Two contiguous

1. We are outside the grid, and there is nothing to do.

2. We see a 0, and there is nothing to do.

3. We see a 1 that has been seen previously; there is nothing to do.

4. We see a 1 for the first time; we move into that position and look in four directions

from there.

Step 3 implies that when we meet a 1 for the first time, we would need to mark it in some way so that if we come
across this position later, we will know it has been met before and we will not attempt to process it again.
The simplest thing we can do is to change the value from 1 to 0 ; this ensures that nothing is done if this position
is met again. This is fine if all we want to do is count the organisms. But if we also want to identify which cells make up
an organism, we will have to mark it differently.