Heapsort.java

/**
 * Heapsort (method) is a comparison-based sorting algorithm,
 * and is part of the selection sort family. Although somewhat
 * slower in practice on most machines than a good implementation of
 * quicksort, it has the advantage of a worst-case Θ(n log n) runtime.
 * Heapsort is an in-place algorithm, but is not a stable sort.
 * 
 * @author ishikawa
 *
 */
public class Heapsort {
	private static void swap(int[] elements, int i, int j) {
		int tmp = elements[j];
		elements[j] = elements[i];
		elements[i] = tmp;
	}

	private static void shiftup(int[] elements, int n) {
		int i = n;
		while (i > 0) {
			final int p = (i+1)/2-1;
			if (elements[i] < elements[p]) break;
			swap(elements, i, p);
			i = p;
		}
	}
	
	private static void shiftdown(int[] elements, int n) {
		int i = 0;
		while(i <= n) {
			int c = (i+1)*2-1; // left child
			if (c > n) break;
			if ((c+1) <= n && elements[c+1] > elements[c]) c++;
			if (elements[i] >= elements[c]) break;
			swap(elements, i, c);
			i = c;
		}
	}

	public static void sort(int[] a) {
		for (int i = 1; i < a.length; i++) shiftup(a, i);
		for (int i = a.length - 1; i > 0; i--) {
			swap(a, 0, i);
			shiftdown(a, i-1);
		}
	}


}

HeapsortTest.java

import java.util.Arrays;

import junit.framework.TestCase;


public class HeapsortTest extends TestCase {

	public void test_empty() {
		int[] elements = {};
		Heapsort.sort(elements);
		assertEquals(0, elements.length);
	}

	public void test_single_element() {
		int[] elements = {123};
		Heapsort.sort(elements);
		assertEquals(1, elements.length);
		assertEquals(123, elements[0]);
	}

	public void test_sorted_array() {
		int[] elements = {1, 2, 3};
		Heapsort.sort(elements);
		assertEquals(3, elements.length);
		assertTrue(Arrays.equals(elements, new int[]{1, 2, 3}));
	}

	public void test_simple() {
		int[] elements = {123, 20, 55, 40, 0};
		Heapsort.sort(elements);
		assertEquals(5, elements.length);
		assertTrue(Arrays.equals(elements, new int[]{0, 20, 40, 55, 123}));
	}

	public void test_same_elements() {
		int[] elements = {0,0,0,0,0};
		Heapsort.sort(elements);
		assertEquals(5, elements.length);
		assertTrue(Arrays.equals(elements, new int[]{0,0,0,0,0}));
	}

}