問題1

class Sorter extends Thread{
private TextField[] obj; // reference to data

    Sorter(TextField[] l){ obj=l; }

    // support function: get integer value
    private int val(TextField l){
        return Integer.parseInt(l.getText());
    }

    // support function: set integer value
    private void set(TextField l, int v){
        //l.setBackground(Color.red);
        l.setText(v+"");
        //l.setBackground(Color.white);
    }

    // Bootstrap for Sort Engine
    public void run(){
        new QSorter(obj, 0, obj.length-1).run();
    }
}

class QSorter{
private TextField[] obj; // reference to data
private int left;
private int right;

    // obj[left]からobj[right]までをソートします
    QSorter(TextField[] tf, int left, int right){
        obj=tf; this.left=left; this.right=right;
    }

    // support function: get integer value
    // Sorterとかぶっててかっこ悪いですね，修正点の指示に失敗しました
    private int val(TextField l){
        return Integer.parseInt(l.getText());
    }

    // support function: set integer value
    // Sorterとかぶっててかっこ悪いですね，修正点の指示に失敗しました
    private void set(TextField l, int v){
        //l.setBackground(Color.red);
        l.setText(v+"");
        //l.setBackground(Color.white);
    }

    // 見ていて分かりやすいように，分割中の値はクリアすることにしました
    private void clear(TextField l){
        l.setText("");
    }

    // Algorithm body, currently bubble sort
    public void run(){
        // ソート左端と右端のindexの大小が逆転してたら，この部分はソートが終わっているはず
        if(left>=right) return;

        // 分割するため，今ある値を tmpa[]に一時退避します
        int[] tmpa=new int[right-left+1];
        for(int i=0; i<tmpa.length; i++){
            tmpa[i]=val(obj[left+i]);
            clear(obj[left+i]);
        }

        int tmpl=0;             // tmplの指す相対位置に小さい値を左からつめていきます
        int tmpr=tmpa.length-1; // tmprの指す相対位置に大きい値を右からつめていきます
        int tmpc=tmpa[0];       // 中間値
        for(int i=1; i<tmpa.length; i++){
            if(tmpa[i]<tmpc){
                set(obj[left+tmpl], tmpa[i]); tmpl++;
            }else{
                set(obj[left+tmpr], tmpa[i]); tmpr--;
            }
            try{ Thread.currentThread().sleep(800); } catch(Exception e){}; // 見やすくするため
        }
        set(obj[left+tmpl], tmpc); // 左右に振り分け終わった後に中間値を置く位置がわかる

        new QSorter(obj, left, left+tmpl-1).run();  // 中間値は含まれないことに注意
        new QSorter(obj, left+tmpr+1, right).run();
    }
}

問題2

上記と異なる部分のみ 赤字． 要は上記とほとんど同じ．

class Sorter extends Thread{
private TextField[] obj; // reference to data

    Sorter(TextField[] l){ obj=l; }

    // support function: get integer value
    private int val(TextField l){
        return Integer.parseInt(l.getText());
    }

    // support function: set integer value
    private void set(TextField l, int v){
        //l.setBackground(Color.red);
        l.setText(v+"");
        //l.setBackground(Color.white);
    }

    // Bootstrap for Sort Engine
    public void run(){
        new QSorter(obj, 0, obj.length-1).start();
    }
}

class QSorter extends Thread{
private TextField[] obj; // reference to data
private int left;
private int right;

    QSorter(TextField[] tf, int left, int right){
        obj=tf; this.left=left; this.right=right;
    }

    // support function: get integer value
    private int val(TextField l){
        return Integer.parseInt(l.getText());
    }

    // support function: set integer value
    private void set(TextField l, int v){
        //l.setBackground(Color.red);
        l.setText(v+"");
        //l.setBackground(Color.white);
    }

    private void clear(TextField l){
        l.setText("");
    }

    // Algorithm body, currently bubble sort
    public void run(){
        // this segment is already sorted. 
        if(left>=right) return;

        int[] tmpa=new int[right-left+1];
        // save original values in obj[left] to obj[right];
        for(int i=0; i<tmpa.length; i++){
            tmpa[i]=val(obj[left+i]);
            clear(obj[left+i]);
        }

        int tmpl=0;
        int tmpr=tmpa.length-1;
        int tmpc=tmpa[0]; // assume center value
        for(int i=1; i<tmpa.length; i++){
            if(tmpa[i]<tmpc){
                set(obj[left+tmpl], tmpa[i]); tmpl++;
            }else{
                set(obj[left+tmpr], tmpa[i]); tmpr--;
            }
            try{ Thread.currentThread().sleep(800); } catch(Exception e){};
        }
        set(obj[left+tmpl], tmpc);

        new QSorter(obj, left, left+tmpl-1).start();
        new QSorter(obj, left+tmpr+1, right).start();
    }
}

問題3

• 逐次の場合は，二つの部分列に分けた後でも， まず，左をやって，次に右をやるという，逐次的な処理をする．
• しかし，並行処理で記述すると，分割した後は，それぞれ勝手な順番で 処理が行うことができることがわかる．

• 1つのCPUにおいて，当該のプログラムに同じ時間だけ処理権限が 与えれている場合においては，逐次版も並行版も処理の速さは変わらない． スレッド処理のスケジューリングにもよるが， 異なるのは，処理順序のみである．
• むしろマルチスレッドの場合はスケジューリングをする分， 処理が増えるので，若干遅いのかもしれない．
• 実際に並列実行可能か否かはマシン次第である．
• 本解答例では， 左右の振り分けの際，sleepによって，処理を見やすいようにしている． 逐次の場合，処理が本当に一定時間とまってしまうが， 並行の場合，sleepしていないスレッドは処理を続けて行うことができる． よって，並行版の方が処理が速くなる． (概念図)

• 複数のCPUを同時に利用できるマシンの場合， これもスケジューリング等の負担にもよるが， 並行版のほうが速くなる可能性がある．
• ある値をもとに，それより大きいもの，小さいものの2つの部分列に 分割した後は，異なる部分列に含まれる値間は無関係となる． よって，分割された部分列を同時並行して処理する場合に， それぞれの処理の間の処理順序や同期を全く考慮しなくても， 干渉やデッドロックが起こることはありえない． これが，容易さの理由である．
• 逐次，並行処理の違いはほとんど無いようにソースコード記述することが， 比較的容易である．