The Java HotSpot Virtual Machine

Algorithms

Computers run programs; programs implement algorithms. A good working definition of an algorithm for the purpose of this book is that an algorithm is a recipe for getting something done on a computer. Pretty much every line of source code you write is considered part of an algorithm. What I’d like to do in this brief section is bring to your attention the concept of good vs. bad algorithms.

Good vs. Bad Algorithms

There are good ways to do something in source code and there are bad ways to do the same exact thing. A good example of this can be found in the act of sorting. Suppose you want to sort in ascending order the following list of integers:

 1,10,7,3,9,2,4,6,5,8,0,11

One algorithm for doing the sort might go something like this:

• Step 1: Select the first integer position in the list

• Step 2: Compare the selected integer with its immediate neighbor

• Step 2.2: If the selected integer is greater than its neighbor swap the two integers

• Step 2.3: Else, leave it where it is

• Step 3: Continue comparing selected integer position with all other integers repeating steps 2.2–2.3

• Step 4: Select the second integer position on the list and repeat the procedure beginning at step 2

Continue in this fashion until all integers have been compared to all other integers in the list and have been placed in their proper position.

This algorithm is simple and straightforward. It also runs pretty fast for small lists of integers but it is really slow given large lists of integers to sort. Another sorting algorithm to sort the same list of integers goes as follows:

• Step 1: Split the list into two equal sublists

• Step 2: Repeat step 1 if any sublist contains more than two integers

• Step 3: Sort each sublist of two integers

• Step 4: Combine sorted sublists until all sorted sublists have been combined

This algorithm runs a little slow on small lists because of all the list splitting going on but sorts large lists of integers way faster than the first algorithm. The first algorithm lists the steps for a routine I call dumb sort. Example 4.1 gives the source code for a short program that implements the dumb sort algorithm.

Example 4.1: DumbSort.java

 1        public class DumbSort{ 2         public static void main(String[] args){ 3 4            int a[]={1,10,7,3,9,2   ,4,6,5,8,0,11}; 5 6            int innerloop=0; 7            int outerloop=0; 8            int swaps=0; 9 10           for(int i=0; i<12; i++){ 11             outerloop++; 12               for(int j=1; j<12; j++){ 13                 innerloop++; 14                   if (a[j-1] > a[j]) { 15                        int temp=a[j-1]; 16                        a[j-1]=a[j] ; 17                        a[j]=temp; 18                        swaps++;}}} 19 20           for(int i=0; i<12; i++) 21               System.out .print (a[i]+" "); 22 23           System.out.println(); 24           System.out.println("Outer loop executed "+outerloop+"times."); 25           System.out.println("Inner loop executed "+innerloop+"times."); 26           System.out.println(swaps+"swaps completed."); 27        } 28       }

Included in the dumb sort test source code are a few variables intended to help collect statistics during execution. These are innerloop, outerloop, and swaps declared on lines 6, 7, and 8 respectively. Figure 4-10 gives the results from running the dumb sort test program.

Figure 4-10: Dumb Sort Results 1

Notice that the inner loop executed 132 times and that 30 swaps were conducted. Can the algorithm run any better? One way to check is to rearrange the order of the integers in the array. What if the list of integers is already sorted? Figure 4-11 gives the results of running dumb sort on an already sorted list of integers:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

Figure 4-11: Dumb Sort Results 2

It appears that both the outer loop and inner loop are executed the same number of times in each case, which is of course the way the source code is written, but it did run a little faster because fewer swaps were necessary.

Can the algorithm run any worse? What if the list of integers is completely unsorted? Figure 4-12 gives the results of running dumb sort on a completely unsorted list:

11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

Figure 4-12: Dumb Sort Results 3

The outer loop and inner loop executed the same number of times but 66 swaps were necessary to put everything in ascending order. So it did run a little slower this time.

In dumb sort, because we’re sorting a list of 12 integers, the inner loop executes 12 times for every time the outer loop executes. If dumb sort needed to sort 10,000 integers then the inner loop would need to execute 10,000 times for every time the outer loop executed. To generalize the performance of dumb sort you could say that for some number N integers to sort, dumb sort executes the inner loop roughly N x N times. There is some other stuff going on besides loop iterations but when N gets really large, the loop iteration becomes the overwhelming measure of dumb sort’s performance as a sorting algorithm. Computer scientists would say that dumb sort has order N² performance. Saying it another way, for a really large list of integers to sort, the time it takes dumb sort to do its job is approximately the square of the number N of integers that need to be sorted.

When an algorithm’s running time is a function of the size of its input the term used to describe the growth in time to perform its job vs. the size of the input is called the growth rate. Figure 4-13 shows a plot of algorithms with the following growth rates: log n, n, n log n, n², n3, nⁿ

Figure 4-13: Algorithmic Growth Rates

As you can see from the graph, dumb sort, with a growth rate of n², is a bad algorithm, but not as bad as some other algorithms. The good thing about dumb sort is that no matter how big its input grows, it will eventually sort all the integers. Sorting problems are easily solved. There are some problems, however, that defy straightforward algorithmic solution.

Don’t Reinvent The Wheel!

If you are new to programming the best advice I can offer is for you to seek the knowledge of those who have come before you. There are many good books on algorithms, some of which are listed in the reference section. Studying good algorithms helps you write better code.