-1

再帰と、現在反復的な挿入ソートを再帰的なものに変える方法を理解しようとしています。

コードを再帰的にするには、コードに何をする必要がありますか?

  • 無限ループにならないようにベースケースが必要だと思います。
  • 再帰を完全に理解しているかどうかはわかりません。多分あなたは私のためにそれをより明確にすることができますか？
  • 私はたくさんの読書をしましたが、どこから始めればいいのかまだわかりません.

これが私のコードです：

public class InsertionSort
{

    public static void main(String a[])
    {

        int i;
        int array[] =
        { 8, 33, 12, 99, 0, 17 };

        System.out.println("Values of Array before the sort: ");

        for (i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + "  ");
        }

        insertion_srt(array, array.length);

        System.out.println("");
        System.out.println("Values of Array after the sort: ");

        for (i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + "  ");
        }

    }

    public static void insertion_srt(int array[], int n)
    {

        for (int i = 1; i < n; i++)
        {

            int j = i;
            int B = array[i];

            while ((j > 0) && (array[j - 1] > B))
            {
                array[j] = array[j - 1];
                j--;
            }

            array[j] = B;
        }
    }
}
4

4 に答える 4

1

これは私が個人的に好きな素晴らしいアプローチです。3 つの方法を使用しますが、理解するのは非常に簡単です。insertOut を外側の for ループと考え、insertionIn を内側のネストされた for ループと考えてください。

public static void insertionRecursive(int[] a){
    if(a.length > 0){ // base case
        insertionOut(a, 1, a.length);
    }
}   
private static void insertionOut(int[] a, int i, int length){ //outer loop
    if(i < length){ // iterates from 1 to the length
        int temp = a[i]; // temp value
        int k = i;
        insertionIn(a, k, temp);
        insertionOut(a, i + 1, length); // iterates through the loop
    }
}
private static void insertionIn(int[] a, int k, int temp){ // inner loop
    if(k > 0 && a[k - 1] > temp){
       //this does a basic swap
        a[k] = temp;
        a[k] = a[k - 1];
        a[k - 1] = temp;
        insertionIn(a, k - 1, temp);    // iterates through the loop
    }
}
于 2014-12-10T10:24:35.493 に答える
0

再帰がどのように機能するかを理解する良い方法は、分割統治アルゴリズムの概念を理解することです。この手法は、あらゆる種類の問題に対する効率的なアルゴリズムの基礎です。

その背後にある考え方は、問題をすべて同じ方法で解決できる小さなサブ問題に分割することです。

  • 2つ（またはそれ以上）のサブ問題に分割します。
  • 各サブ問題を再帰的に解決します。
  • 結果を組み合わせます。

挿入ソートは分割統治アルゴリズムの最良の例ではありませんが、それでもこの方法でアプローチできます。問題を2つのサブ問題に分けることができます。

  • 最後の要素
  • ほかのすべて

このようにして、いわゆる末尾再帰が得られます。すべてのループは、末尾再帰に変換するのが比較的簡単です。

public static void insertion_srt(int array[], int n, int j) {
    if (j < n) {
        int i;
        int temp = array[j];

        for (i=j; i > 0 && array[i-1] > temp; i--) array[i] = array[i-1];
        array[i] = temp;

        insertion_srt(array,n, j+1);
    }
}
于 2012-10-03T09:44:18.513 に答える
0

外側の for ループを変換するのは簡単です。while ループを克服するには、少し再帰的なヘルパー関数が必要です。メインの関数を次のように呼び出す必要がありますinsertion_srt(array, 0, array.length)。

public static void insertion_srt(int array[], int beg_index, int n) {
    if(beg_index >= n-1)
            return;
    int i = beg_index + 1;
    int j = i;
    int B = array[i];
    j=helper(array, j, B);
    array[j] = B;
    insertion_srt(array, beg_index + 1, n);
}

private static int helper(int[] array, int j, int B) {
    if(j <= 0 || array[j-1] <= B)
        return j;
    array[j] = array[j - 1];
    return helper(array, j-1, B);
}
于 2012-10-03T09:58:20.260 に答える
-1

この単純な再帰的アプローチを試してください。

public static void insertionSort(int[] array, int index) {
    if(array.length == index + 1) return;

    insertionSort(array, index + 1);

    // insert array[index] into the array

}
于 2012-10-03T09:49:25.880 に答える