ヒープソートの実装

やったことなかったので、ヒープソートを実装してみた。
ヒープソートというのは、ツリー構造を作って、ツリー方向にバブルソートを行うアルゴリズム。

参考

アルゴリズムクイックリファレンス

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}));
    }
}