やったことなかったので、ヒープソートを実装してみた。
ヒープソートというのは、ツリー構造を作って、ツリー方向にバブルソートを行うアルゴリズム。
参考
- 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/04/26
- メディア: 単行本(ソフトカバー)
- 購入: 11人 クリック: 656回
- この商品を含むブログ (72件) を見る
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; public class HeapSort { static int[] sort(int[] data){ //初回のヒープ構築 for(int i = data.length / 2 - 1; i >= 0; --i){ heapify(data, i, data.length); } //ソート実行 for(int i = data.length - 1; i >= 1; --i){ int tmp = data[0]; data[0] = data[i]; data[i] = tmp; heapify(data, 0, i); } return data; } private static void heapify(int[] data, int idx, int max){ int left = idx * 2 + 1; int right = idx * 2 + 2; //一番大きい要素を得る int maxid = idx; if(left < max && data[maxid] < data[left]){ maxid = left; } if(right < max && data[maxid] < data[right]){ maxid = right; } //交換 if(maxid != idx){ int tmp = data[idx]; data[idx] = data[maxid]; data[maxid] = tmp; heapify(data, maxid, max); } } }
テストコード。ランダムにデータ作ってるので、もしテスト通らなかったときにどんなデータでダメだったかわからないけど。
import java.util.ArrayList; import java.util.Collections; import java.util.List; import org.junit.AfterClass; import org.junit.BeforeClass; import org.junit.Test; import static org.junit.Assert.*; public class HeapSortTest { public HeapSortTest() { } @BeforeClass public static void setUpClass() throws Exception { } @AfterClass public static void tearDownClass() throws Exception { } @Test public void testSortランダム() { for(int i = 3; i <= 20; ++i){ List<Integer> data = new ArrayList<>(); for(int j = 1; j < i; ++j){ data.add(j); } for(int j = 0; j < 10; ++j){ Collections.shuffle(data); assertTrue(isSorted(HeapSort.sort(toIntArray(data)))); } } } @Test public void testSort0要素(){ assertArrayEquals(new int[]{}, HeapSort.sort(new int[]{})); } @Test public void testSort1要素(){ assertArrayEquals(new int[]{3}, HeapSort.sort(new int[]{3})); } @Test public void testSort昇順() { for(int i = 2; i <= 20; ++i){ List<Integer> data = new ArrayList<>(); for(int j = 1; j <= i; ++j){ data.add(j); } assertTrue(isSorted(HeapSort.sort(toIntArray(data)))); } } @Test public void testSort降順() { for(int i = 2; i <= 20; ++i){ List<Integer> data = new ArrayList<>(); for(int j = i; j >= 1; --j){ data.add(j); } assertTrue(isSorted(HeapSort.sort(toIntArray(data)))); } } /** IntegerのListをintの配列へ */ private int[] toIntArray(List<Integer> data){ int[] result = new int[data.size()]; for(int i = 0; i < data.size(); ++i){ result[i] = data.get(i); } return result; } /** ソートされているか判定 */ private boolean isSorted(int[] data){ for(int i = 1; i < data.length; ++i){ if(data[i - 1] > data[i]) return false; } return true; } @Test public void testIsSorted(){ assertTrue(isSorted(new int[]{1, 3, 7})); assertTrue(isSorted(new int[]{1, 3, 3, 7})); assertFalse(isSorted(new int[]{1, 8, 7})); assertFalse(isSorted(new int[]{9, 8, 7})); assertFalse(isSorted(new int[]{1, 8, 10, 7})); assertFalse(isSorted(new int[]{1, 8, 8, 7})); } }