開発メモ

開発用のメモです。

シェイカーソート

ソース

package jp.mirageworld.algorithm.sort;

import java.util.ArrayList;
import java.util.List;

public class ShakerSort {

    public static <T extends Comparable<T>> List<T> sort(List<T> list) {
        List<T> retList = new ArrayList<T>(list);

        boolean next = true;
        int top = 0;
        int bot = retList.size() - 1;
        int tmp;
        while (next) {
            next = false;

            tmp = top;
            for (int i = top; i < bot; i++) {
                T a = retList.get(i + 0);
                T b = retList.get(i + 1);

                if (a.compareTo(b) > 0) {
                    retList.set(i + 0, b);
                    retList.set(i + 1, a);
                    tmp = i;
                    next = true;
                }
            }
            if (!next) {
                break;
            }
            bot = tmp;
            for (int i = bot; i > top; i--) {
                T a = retList.get(i - 0);
                T b = retList.get(i - 1);

                if (a.compareTo(b) < 0) {
                    retList.set(i - 0, b);
                    retList.set(i - 1, a);
                    next = true;
                    tmp = i;
                }
            }
            top = tmp;
        }
        return retList;
    }
}

テストケース

package jp.mirageworld.algorithm.sort;

import static org.junit.Assert.*;

import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import org.junit.Test;

public class ShakerSortTest {

    @Test
    public void testSort() {
        Set<Long> set = new HashSet<>();
        Long target = Math.round(Math.random() * 50);
        while (set.size() < 50) {
            set.add(Math.round(Math.random() * 50 + set.size() * 50));
        }
        List<Long> list = new LinkedList<>(set);
        target = list.get(target.intValue());

        List<Long> retList = ShakerSort.sort(list);

        System.out.println(list);
        System.out.println(retList);

        Collections.sort(list);
        assertEquals(list.toString(), retList.toString());
        System.out.println(list);
    }

}
Twitter: @asahina_alice