algorithm - 挿入ソートはポストオーダーできますか?

Question

public class insSort {
int i,j,key; //j=1

public void rec(int a[],int pos){

    if(pos>a.length-1){
        return;
    }
    key= a[pos];
    i=pos-1;
    while((i>=0)&&(a[i]>key)){//swapping
            a[i+1]=a[i];
            i--;
            a[i+1]=key;
        }
        pos++;
        rec(a,pos);//post order
    }

挿入ソートと見なすことはできますか？それとも順番にすべきですか？再帰アルゴリズムにインオーダーを使用することは普遍的な慣行ですか?もしそうなら、なぜそうなのですか?

Answer 1

問題のコード例は末尾再帰バージョンであり、コンパイラがループに最適化する可能性があります (再帰なし)。サンプル コードを C++ に変換し、マイナーなクリーンアップを行いました。最初の呼び出しは rec(1) (pos == 1 の初期値) である必要があります。

class insSort
{
public:
    int a[8];

    void rec(int pos){
    int i,value;
        if(pos >= (sizeof(a)/sizeof(a[0])))
            return;
        value = a[pos];                       // get value
        i = pos-1;
        while((i >= 0) && (a[i] > value)){    // shift up
            a[i+1] = a[i];
            i--;
        }
        a[i+1] = value;                       // insert value
        pos++;
        rec(pos);
    }
};