Дерево решений с алгоритмом рекурсивной сортировки

Question

Мне было интересно, может ли кто-нибудь помочь мне понять, как создать дерево решений для рекурсивной сортировки. Я понимаю, как это сделать, скажем, с помощью пузырьковой сортировки или вставки. Когда дело доходит до рекурсивного вида, я просто не могу представить это. Если псевдокод является чем-то вроде:

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

Первоначально я думал, что дерево решений будет выглядеть следующим образом:

                               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

Я явно где-то ошибаюсь, просто я не совсем уверен, где. Я на правильном пути здесь?

Спасибо за любые указатели, которые вы можете дать мне.

Answer 1

Следуя вашему представлению, результат будет примерно таким:

                            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**

На последнем шаге вы решаете, нужен ли обмен или два на левой стороне отсортированы.Если это так, нет необходимости продолжать сортировку, так как сортировка с правой стороны выполняется, если это не так, вы сначала меняете местами самые левые элементы и сортируете два справа.

например, B: A,C --swap-> A: B, C --sort-> A, B, C или A, C, B.

Надеюсь, это поможет вам.

Answer 2

(это домашняя работа?)

Посмотри на свой код еще раз! В настоящее время вы разветвляетесь в обе стороны внутри конструкции if-then-else. Исправьте это, и вы получите один правильный результат.

Кроме того, вы там раскручиваете стек вызовов, поэтому возвращение назад будет «более правильным». Википедия может дать вам представление о том, как это работает.

Удачи!