開発メモ

開発用のメモです。

クイックソート

ソース

package jp.mirageworld.algorithm.sort;

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

public class QuickSort {

    public static <T extends Comparable<T>> List<T> sort(List<T> list) {
        List<T> retList = new ArrayList<>(list);
        return sort(retList, 0, retList.size() - 1);
    }

    public static <T extends Comparable<T>> List<T> sort(List<T> list, int left, int right) {

        if (left < right) {
            int i = left;
            int j = right;
            T pivot = med3(list.get(i), list.get(i + (j - i) / 2), list.get(j));
            while (true) {
                while (list.get(i).compareTo(pivot) < 0)
                    i++;
                while (pivot.compareTo(list.get(j)) < 0)
                    j--;
                if (i >= j)
                    break;
                T a = list.get(i);
                T b = list.get(j);

                list.set(i, b);
                list.set(j, a);

                i++;
                j--;
            }
            sort(list, left, i - 1);
            sort(list, j + 1, right);
        }

        return list;
    }

    private static <T extends Comparable<T>> T med3(T x, T y, T z) {
        if (x.compareTo(y) < 0)
            if (y.compareTo(z) < 0)
                return y;
            else if (z.compareTo(x) < 0)
                return x;
            else
                return z;
        else if (z.compareTo(y) < 0)
            return y;
        else if (x.compareTo(z) < 0)
            return x;
        else
            return z;
    }

}

テストケース

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 QuickSortTest {

    @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 = QuickSort.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