[java] クイックソート 効率はよくない

クイックソート。

	package jp.dip.sys1.yagi.sort;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Comparator;
	import java.util.List;
	import java.util.Random;
	public class QuickSort {
	/**
	* クイックソートやで
	* @param list ソート対象のリスト
	* @param comp 比較関数
	* @return ソート済みのリスト
	*/
	public static <T> List<T> sort(List<T> list, Comparator<T> comp) {
	if(list.isEmpty()){
	return list;
	}
	//ピボットより値の小さいリスト
	List<T> smaller = new ArrayList<T>();
	//ピボットより値の大きいリスト
	List<T> greater = new ArrayList<T>();
	Random p = new Random(System.currentTimeMillis());
	//ピボット
	int index = p.nextInt(list.size());
	T pv = list.get(index);
	//ピボットより小さい値、大きい値で各リストに振り分ける
	for (int i = 0; i < list.size(); i++) {
	if (i != index) {
	T l = list.get(i);
	if (comp.compare(pv, l) >= 0) {
	smaller.add(l);
	} else {
	greater.add(l);
	}
	}
	}
	//ピボットより値の小さいリスト、ピボットより値の大きいリストをそれぞれクイックソートにかける
	//ピボットを真ん中にして連結して返す
	List<T> result = new ArrayList<T>();
	result.addAll(QuickSort.sort(smaller, comp));
	result.add(pv);
	result.addAll(QuickSort.sort(greater, comp));
	return result;
	}
	//sample
	public static void main(String[] args) {
	Integer[] l = new Integer[] { 1, 20, 4205, 539, 5, 2, 104, 100, 6, 1, 7, 239, 2, 55 };
	List<Integer> list = Arrays.asList(l);
	list = QuickSort.sort(list, new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
	return o1 - o2;
	}
	});
	for (Integer r : list) {
	System.out.println(r);
	}
	}
	}

view raw QuickSort.java hosted with ❤ by GitHub