MergeSort

コメントをかけって言われそうな気もするけど気にしない。

merge関数でwhileを乱用してるのが気になる。
もう少しスマートな記述にしたい

後半の条件分岐が美しくない。45点

DoubleStackQueue

実装自体はすぐに完了。
Stackのほうが間違ってたのでそっちの修正に手間取った。
（配列の0番地を使ってない＆toStringの表示がおかしい）

Stack＆Queue

コードの類は以下に今後載せることにしました。
秋刀魚のCode録

閑話休題

StackとQueueの実装だけ済ましてみました。
テストは簡単にしかしていないので境界付近でも正しく動くかは不明。
Stackのほうは実装が簡単なのでおいておくとして

Queueのほうは少し課題が残ってる感じ。

■課題
1．
Full状態でも配列が1個あまる実装なのでスタックのサイズと配列のサイズのメンバ名に違和感がある。

2．
　int data = this.queue[this.head];
　this.head = nextIndex(this.head)
　return data;

のような書き方がCoolじゃない。できれば以下のように書きたい

　return this.queue[next(this.head)];

ここでnext(int val)は現在のthis.headを返した後this.headをインクリメント。感じとしては↓のような意味。

　return this.queue[this.head++]

基本型が値渡しでしか渡せないのが悔やまれます。
演算子のオーバーロードで何とかなるか、と思ったらJavaは演算子のオーバーロードを実装してないとのことorz

thisを渡してその中をいじるようなメソッドを作ってもいいかなと一瞬思ったけど、それだとheadとtailで別々に関数を作らないといけないからスマートじゃない。

結局基本型の変数のアドレスを渡せないと解決できないような気がします。

#新キーボードの打鍵感が楽しすぎる(｀・ω・)

Priority Queue

前回のコードに追加した部分

    /**
     * 要素をヒープに追加する
     * @param element　挿入する要素
     */
    public void insert(int element){
        int i= ++this.heapSize;
        this.arrayList.add(element);
       
        //iが根でない　かつ　親要素よりelementが大きい
        while(i>0 && this.arrayList.get(getParent(i))<element){
            changeElem(getParent(i), i);
            i=getParent(i);
        }
    }
   
    /**
     * knot番目の要素がelementより小さければknot番目の要素をelementに変更する
     * @param knot
     * @param element
     */
    public void heapIncreaseKey(int knot, int element) {
        if(this.arrayList.get(knot) < element){
            this.arrayList.set(knot, element);
            this.heapify();
        }
    }
   
    /**
     * i番目の要素を削除する
     * @param int i: index of deleted element
     */
    public void heapDelete(int i) {
        //i番目の要素と最後の要素を入れ替えて削除
        this.changeElem(i, this.heapSize);
        this.arrayList.remove(this.heapSize);

        //ヒープサイズの減少
        this.heapSize--;

        //ヒープ条件の再構築
        this.heapify(i);
    }
   
    /**
     * 最大の要素を返す
     * @return　最大要素の値
     */
    public int getMaximum(){
        return this.arrayList.get(0);
    }
   
    /**
     * 最大の要素を持つ要素を削除してその値を返す
     * @return　最大の要素の値（return後削除）
     */
    public int extractMax() throws IndexOutOfBoundsException{
        //例外処理
        if(this.heapSize<0){
            throw new IndexOutOfBoundsException("ヒープアンダーフロー");
        }
       
        int max = getMaximum();
       
        this.changeElem(0, this.heapSize);
        this.arrayList.remove(this.heapSize);
       
        this.heapSize--;
        this.heapify();
       
        return max;
    }

    /**
     * 親要素のindexを返す
     * @param knot
     * @return int: index of parent element
     */
    private int getParent(int knot){
        //XXX 切り捨てが正しくない気がする
        return (int) ((double)knot/(double)2 -0.5);
    }

HeapSort

Javaでヒープソートを実装してみました。
保持配列をArrayListで持ってるのは後々の要素追加削除をにらんで。
プライオリティーキューはまた今度(´･ω･｀)

入力配列
0　48　27　76　99　54　15　80　30

実行結果
0　15　27　30　48　54　76　80　99
--
import java.util.*;

/**
 *
 * @author sanma
 *
 */
public class HeapSort {
    /**
     * ソート対象arrayList
     */
    private ArrayList<Integer> arrayList;
   
    /**
     * heap-size
     */
    private int heapSize;
   
    /**
     * 入力配列をarrayListに格納
     * @param array
     */
    public HeapSort(int[] array) {
        this.arrayList = new ArrayList<Integer>();
       
        //配列内容をarrayListにコピー
        for(int i=0;i<array.length;i++){
            arrayList.add(array[i]);
        }
        buildHeap();
    }
   
    /**
     * arrayListによる生成
     * @param arrayList
     */
    public HeapSort(ArrayList<Integer> arrayList) {
        //HeapSort(int[] array)からのキャストなら何もしない
        if(this.arrayList != arrayList){
            this.arrayList = new ArrayList<Integer>(arrayList);
        }
        buildHeap();
    }
   
    /**
     *
     */
    private void buildHeap(){
        this.heapSize = arrayList.size()-1;

        //XXX 小数点の切り捨て処理
        for(int i=this.heapSize/2;i>=0;i--){
            heapify(i);
        }
    }
   
    /**
     * knot以下要素のヒープ条件を保持
     * @param knot
     */
    private void heapify(int knot) {
        int left = this.getLeft(knot);
        int right = this.getRight(knot);
       
        int largest;
       
        //親子の3要素のうち最大の要素を判定
        if(left<= this.heapSize && this.arrayList.get(left)>this.arrayList.get(knot)){
            largest = left;
        } else largest = knot;
        if(right<= this.heapSize && this.arrayList.get(right)>this.arrayList.get(largest)){
            largest = right;
        }
       
        if(largest != knot){
            //値の交換
            changeElem(knot, largest);
           
            //再帰
            this.heapify(largest);
        }
       

    }
   
    public Integer[] getlist(){
        return this.arrayList.toArray(new Integer[]{});
    }
   
    public void doSort() {
        for(int i=this.arrayList.size()-1;i>0;i-=1){
            changeElem(0, i);
           
            heapSize--;
           
            this.heapify(0);
        }
    }
   
    private void changeElem(int index1, int index2){
        int tmp = this.arrayList.get(index1);
       
        this.arrayList.set(index1, this.arrayList.get(index2));
        this.arrayList.set(index2, tmp);
    }
   
    private int getLeft(int knot){
        int left = 2*knot+1;
       
        return left;
    }
   
    private int getRight(int knot){
        int right = 2*knot+2;
       
        return right;
    }

    public static void main(String[] args) {
        int[] data = {0,48,27,76,99,54,15,80,30};
        HeapSort heap = new HeapSort(data);
      
        heap.doSort();
        Integer[] sortedList = heap.getlist();

         for(int i=0;i<sortedList.length;i++){
            System.out.printf(sortedList[i].toString()+" ");
        }
    }

}