こちらでバブルソートをしたので、今回はクイックソートしてみます。
クイックソートのサンプル
１０個の整数をシャッフル。
シャッフルしたリストをクイックソートでソートします。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.stream.Collectors; import java.util.stream.IntStream; public class QuickSort { public static void main(String[] args) { //データ準備 List<Integer> sortList = IntStream.rangeClosed(1, 10) .boxed() .collect(Collectors.toList()); Collections.shuffle(sortList); System.out.println("ソート前:" + sortList); //ソート sortList = sort(sortList); System.out.println("ソート後:" + sortList); } public static List<Integer> sort(List<Integer> list){ List<Integer> leftList = new ArrayList<>(); List<Integer> rightList = new ArrayList<>(); //リストの最後尾をピボットにする int eval = list.get(list.size() -1); for(int i=0 ; i<list.size()-1 ; i++) { //ピボットと大小比較して、左右のリストに分割 int v = list.get(i); if(v >= eval) { rightList.add(v); }else { leftList.add(v); } } //左右のリストで再帰 if(leftList.size() != 0) { leftList = sort(leftList); } if(rightList.size() != 0) { rightList = sort(rightList); } //再帰の結果を足す leftList.add(eval); leftList.addAll(rightList); return leftList; } } |
実行結果
ソート前とソート後のリストが出力されます。
1 2 | ソート前:[5, 10, 1, 3, 7, 9, 4, 6, 8, 2] ソート後:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] |
サンプルの解説
クイックソートは、一般的に早いアルゴリズムです。
また、いろんなやり方があります。
今回は、よくある基本的なやり方です。
１つピボットを決めて、大小を比較して左右に分割。
これを再帰的に繰り返しています。
