Home Tutorials Training Consulting Books Company Contact us

Get more...

Algorithms in Java. This article describes some very common algorithm in Java.

It could be argued that for most problems someone else has already written an implementation of an algorithm which solves this problem. So rather by copying the implementation and using it you can also solve the problem. While this argumentation is true and while code reuse is important, I believe that having a sound understanding of the basis algorithms for standard problems helps to solve other analytical problems. So please see this article as a kind of brain teaser. Understanding algorithms can be very rewarding.

In addition everybody has to sort Arrays or Lists, so I believe it is important to at least understand the complexity for this problem and the available implementations of these.

1.2. What is an algorithm

An algorithm describes a way of solving a specific problem.

1.3. Complexity

The complexity of an algorithm is dependent on the problem and on the algorithm itself. It can be described using the Big-O notation. An algorithm is said to have a complexity of O(n) if the runtime of solving a problem with this algorithm, depends on the number of elements (n) of this problem. For example a sort algorithm for a list with n elements is said to have the complexity of O(n^2) if the runtime of this algorithm increases exponentially with the number of elements.

A problem is said to be NP-hard (nondeterministic polynomial-time hard) if no algorithm exists which solves the problem in polynomial time.

2. Sort in Java

Sort algorithms are ordering the elements of a list according to a certain order. For the Java examples I will assume that we are sorting an array of integers. The examples for this chapter will be created in a Java project "de.vogella.algorithms.sort". The sorting algorithm will implement the following interface.

package de.vogella.algorithm;

public interface ISort {
    void sort(int[] a);
}

2.1. Quicksort

Quicksort is a fast, recursive, non-stable sort algorithm which works by the divide and conquer principle. It has in average O(n log (n)) and in the worst case O(n2) complexity. Quicksort selects first a pivot elements. It then divides the elements of the list into two lists based on this pivot element. Every element which is smaller than the pivot element is placed in the left list and every element which is larger is placed in the right list. If an element is equal to the pivot element then it can go in any list. After this sorting the algorithm is then called recursively for the left and right list. If a list contains only one (or zero) elements then it sorted. Quicksort does not copy any data it just exchanges the values in the array therefore it does not consume a lot of memory (only on the call stack for the recursive call of the function. The disadvantages of Quicksort is that it does not work well on already sorted lists or an lists with lots of similar values.

package de.vogella.algorithm.quicksort;

public class Quicksort {
    private int[] numbers;
    private int number;

    public void sort(int[] values) {
        this.numbers = values;
        number = values.length;
        quicksort(0, number - 1);
    }

    private void quicksort(int low, int high) {
        int i = low, j = high;
        // Get the pivot element from the middle of the list
        int pivot = numbers[(low + high) / 2];

        // Divide into two lists
        while (i <= j) {
            // If the current value from the left list is smaller then the pivot
            // element then get the next element from the left list
            while (numbers[i] < pivot) {
                i++;
            }
            // If the current value from the right list is larger then the pivot
            // element then get the next element from the right list
            while (numbers[j] > pivot) {
                j--;
            }

            // If we have found a values in the left list which is larger then
            // the pivot element and if we have found a value in the right list
            // which is smaller then the pivot elment then we exchange the
            // values.
            if (i <= j) {
                exchange(i, j);
                i++;
                j--;
            }
        }
        // Recursion
        if (low < j)
            quicksort(low, j);
        if (i < high)
            quicksort(i, high);
    }

    private void exchange(int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }
}

2.2. Mergesort

Mergesort is a fast, recursive, stable sort algorithm which works by the divide and conquer principle. The algorithm has a complexity of O(n log (n)). Similar to Quicksort the list of elements which should be sorted is divided into two lists. These lists are sorted independently and then combined. During the combination of the lists the elements are inserted (or merged) on the correct place in the list. Merge can be implemented in several ways.

The simplest way of merge is the following :

Assume the size of the left array is k, the size of the right array is m and the size of the total array is n (=k+m).
Create a helper array with the size n
Copy the elements of the left array into the left part of the helper array. This is position 0 until k-1.
Copy the elements of the right array into the right part of the helper array. This is position k until m-1.
Create an index variable i=0; and j=k+1
Loop over the left and the right part of the array and copy always the smallest value back into the original array. Once i=k all values have been copied back the original array. The values of the right array are already in place.

Compared to quicksort the mergesort algorithm puts less effort in dividing the list but more into the merging of the solution.

Standard mergesort does require a copy of the array although there are (complex) implementations of mergesort which allow to avoid this copying.

2.3. Standard Java Array sorting

Java offers a standard way of sorting Arrays with Arrays.sort(). This sort algorithm is a modified quicksort which shows more frequently a complexity of O(n log(n)). See the Javadoc for details.

2.4. Testing the sort algorithm

Here is a small unit test which you can use to test the sort algorithms.

package de.vogella.algorithm.quicksort;

import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import java.util.Random;

import org.junit.Before;
import org.junit.Test;

public class QuicksortTest {

    private int[] numbers;
    private final static int SIZE = 100000000;
    private final static int MAX = 1000000;

    @Before
    public void setUp() throws Exception {
        numbers = new int[SIZE];
        Random generator = new Random(MAX);
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = generator.nextInt(MAX);
        }
    }

    @Test
    public void testSort() {
        long startTime = System.currentTimeMillis();

        Quicksort sorter = new Quicksort();
        sorter.sort(numbers);

        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] > numbers[i + 1]) {
                fail("Should not happen");
            }
        }
        assertTrue(true);
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println(elapsedTime);

    }
}

3. Graph

3.1. Graph

A graph is made out of nodes and directed edges which define a connection from one node to another node. A node (or vertex) is a discrete position in a graph. Edges can be directed or undirected. Edges have an associated distance (also called costs or weight). The distance between two nodes a and b is labeled as [a,b]. The mathematical description for graphs is G= {V,E}, meaning that a graph is defined by a set of vertexes (V) and a collection of edges. The "order" of a graph is the number of nodes. The "size" of a graph is the number of edges.

3.2. Typical Graph Problems

Typical graph problems are:

finding the shortest path from a specific node to another node
finding the maximum possible flow through a network where each edge has a pre-defined maximum capacity (maximum-flow minimum-cut problem)