再帰的にバブルソート

Question

Googleを検索しましたが、何も見つかりませんでした。私は様々な種類のものを探していました（私の以前の質問で分かるように）、誰かが再帰的なバブルソートコードを知っているかどうか疑問に思っていました。私には、このアイデアはばかげて聞こえますが、私は物事の準備をしたいと思います。これができるかどうかについては私は興味があります。私の教授が過去に彼の生徒にこれを尋ねたので、それができると確信しています。私は彼が質問を繰り返すとは思わないが、私は好奇心が強くなり、バブルソートのコードが再帰的に存在するかどうかを知りたい。

Answer 1

これは確かに可能ですが、反復アルゴリズムは再帰アルゴリズムに変換でき、その逆も可能です。

ここでこれを行う方法があります。簡単にするために、私はC++を使用していて、入力はすべて整数であると仮定します。

void bubbleSort(std::vector<int>& list) { 
    /* Make one pass of swapping elements. If anything was swapped, 
    * repeat this process. 
    */ 
    if (swapPass(list)) { 
     bubbleSort(list); 
    } 
} 

/* Does a pass over the array, swapping adjacent elements if they're 
* out of place. Returns true if anything was swapped and false 
* otherwise. 
*/ 
bool swapPass(std::vector<int>& list) { 
    return recSwapPass(list, 0, false); 
} 

/* Does a swap pass starting from index given information about 
* whether a swap was made on the pass so far. Returns true if across 
* the entire pass a swap was made and false otherwise. 
*/ 
bool recSwapPass(std::vector<int>& list, unsigned index, 
       bool wasSwapped) { 
    /* Base case: If we're at the end of the array, then there's 
    * nothing to do and we didn't swap anything. 
    */ 
    if (index + 1 >= list.size()) return wasSwapped; 

    /* Compare the current element against the next one and see if 
    * they need to swap. 
    */ 
    if (list[index] > list[index + 1]) { 
     std::swap(list[index], list[index + 1]); 
     return recSwapPass(list, index + 1, true); 
    } else { 
     return recSwapPass(list, index + 1, wasSwapped); 
    } 
} 

興味深いことに、ここではすべての再帰関数は末尾再帰で、とても良い最適化コンパイラは、非再帰的なコードを生成することができるはずです。言い換えれば、良いコンパイラは、これを繰り返し書いたのと同じコードを生成するはずです。時間があれば、実際に起こっているかどうかチェックします。 :-)