クイックソートの考え方

始めに

ネット上で解説しているクイックソートの実装がいまいちぴんと来なかったので、自分なりにまとめた記事をアップすることにします。
アルゴリズムの方針は関数型言語の解説でよく取り上げられる、要素の分解と再集約を採用し、Javaで実装してみてクイックソートの実装が命令型言語でどのくらい面倒くさいか確認して見ることにします

クイックソートの考え方

例として、[6,1,8,5,9]という数字の集合のソートについて考えてみる
クイックソートを行う時、要素を分割する基準が必要になるが、ここではその基準に集合の1番目の要素を使うことにする

リストの分解イメージ

分解後のリストの集約のイメージ

実装コード

Qsort.java

package test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class QSort {

    public static void main(String args[]){
        System.out.println(qsort(Arrays.asList(1,5,6,2,11,9,4)));
    }

    public static List<Integer> qsort(List<Integer>list){
        if(list.size()==1){
            //配列の含まれる要素が一つならば、再帰処理を抜ける
            return new ArrayList<Integer>(list) ;
        }else{
            //リスト内の要素を分割する処理を呼び出す
            Divive div = splitList(list);
            //分割後の配列を格納するリストを生成する
            List<Integer>newList = new ArrayList<Integer>();
            //小さい数の集合を再度、切り分けるために再帰処理を行う
            newList.addAll(qsort(div.leftList));
            //大きい数の集合を再度、切り分けるために再帰処理を行う
            newList.addAll(qsort(div.rightList));
            return newList ;
        }
    }

    //リストを分割する関数
    public static Divive splitList(List<Integer>list){
        int size =list.size();
        Divive div = new Divive();
        //要素数が二つの場合は、要素間の大小を比較して要素分割を行う
        if(size==2){
            if(list.get(0)<=list.get(1)){
                div.leftList.add(list.get(0))  ;
                div.rightList.add(list.get(1))  ;
            }else{
                div.leftList.add(list.get(1))  ;
                div.rightList.add(list.get(0))  ;
            }
            return div;
        }

        int pivot = list.get(0);
        List<Integer>smallIntList =new ArrayList<Integer>();
        List<Integer>largeIntList =new ArrayList<Integer>();
        //引数で与えられたリストを所定の基準に従って、小さい集合と大きい集合に分ける
        for(int i=0;i<size;i++){
            //基準より小さい数の集合を生成する
            if(pivot>=list.get(i))smallIntList.add(list.get(i));
            //基準より大きい数の集合を生成する
            if(pivot<list.get(size - 1- i))largeIntList.add(list.get(size - 1- i));
        }

        //小さい集合と引数で与えられたリストの引数が一致しない場合、分割したリストの組み合わせを呼び出し元に戻す
        if(smallIntList.size()!=list.size()){
            div.leftList.addAll(smallIntList);
            div.rightList.addAll(largeIntList);
        }
        //小さい集合と引数で与えられたリストの引数が一致する場合は基準となる数字が一番小さいので、
        //リストの一番左とそれ以外でリストを分割する
        else{
            Deque<Integer> que  = new ArrayDeque<Integer>(smallIntList);
            div.leftList.add(que.pop()) ;
            div.rightList.addAll(new ArrayList<Integer>(que))  ;
        }
        return div;
    }

    //Javaは戻り値に2値を設定できないため、分割後の集合を表すデータ構造を定義しておく必要がある
    static public class Divive{
        List<Integer>leftList =new ArrayList<Integer>();
        List<Integer>rightList =new ArrayList<Integer>();
    }
}