再帰ソートアルゴリズムを使用した意思決定ツリー

Question

再帰的な並べ替えのために意思決定ツリーを作成する方法を理解できる人がいるかどうかは疑問でした。私は、バブルソートや挿入ソートなどでそれを行う方法を理解しています。再帰的なソートになると、私はそれを描くことができません。擬似コードのようなものである場合：私は明らかにどこか間違っているつもりです

       A, B, C 
          yes/ \ no is length <= 1? 
          /  \ 
             remove head 
             / \ 
             A B, C 
             yes/ \ no is length <= 1? 
             / \ 
               remove head 
               / \ 
                B C 
               yes/ \ no is length <= 1? 
                / \ 
               B:C 
               / \ 
               B,C C,B 
              |   | 
              A:B,C  A:C,B 
             / \  / \ 
            A,B,C B:A,C A,C,B C:A,B 
              /\  / \ 
             B,A,C A:B,C C,A,B A:C,B 

、私だけではない、かなりよ：

if length == 1 
    return; 
else 
    int elem = head of array; 
    array tail = tail of array; 
    recursive sort; 
    if (elem <= head of sorted list) 
     add elem to the beginning of sorted list 
    else 
     swap elem and first element of sorted list 
     sort smaller list again 
     add elem to the beginning of sorted list 
return 

私の最初に考えたのは、決定木は、以下のように見えるだろうということです確かにどこに。私は正しい道にここにいますか？

ありがとうございました。

Answer 1

（この宿題ですか？）

コードをもう一度見てください。あなたは現在、if-then-else構成内の両方の方法で分岐しています。それを修正すれば、正しい結果が得られるはずです。

また、コールスタックを解凍しているので、バックアップが「より正確」になります。 Wikipediaは、これがどのように機能するかを知っているかもしれません。

幸運を祈る！

Answer 2

あなたの表現に続いて、結果はこのようなものになるだろう：

      A, B, C 
         yes/ \ no is length <= 1? 
         /  \ 
            remove head 
            / \ 
            A B, C 
            yes/ \ no is length <= 1? 
            / \ 
              remove head 
              / \ 
               B C 
              yes/ \ no is length <= 1? 
               / \ 
              B:C 
              / \ 
              B,C C,B 
             |   | 
             A:B,C  A:C,B 
            / \  / \ 
           A,B,C B:A,C A,C,B C:A,B 
             /\  / \ 
            B,A,C **B,C,A** C,A,B **C,B,A** 

最後のステップでは、スワップが必要な場合は、あなたが決めるか、左側の2がソートされています。もしそうであれば、右側がソートされているので並べ替えを行う必要はありません。そうでない場合は、最初に左端の要素を入れ替え、右側の2つをソートします。 B：A、C - スワップ - > A：B、C - ソート - > A、B、CまたはA、C、Bである。

私はそれがあなたを助けてくれることを願っています。