Необходимая помощь вставки понимание рода

Question

В этом коде, как это работает (Java):

/** Move A[A.length-1] to the first position, k, in A such that there 
* are no smaller elements after it, moving all elements 
* A[k .. A.length-2] over to A[k+1 .. A.length-1]. */ 

static void moveOver (int A[]) { 
    moveOver (A, A.length-1); 
} 

/** Move A[U] to the first position, k<=U, in A such that there 
* are no smaller elements after it, moving all elements 
* A[k .. U-1] over to A[k+1 .. U]. */ 

static void moveOver (int A[], int U) { 
    if (U > 0) { 
    if (A[U-1] > A[U]) { 
     /* Swap A[U], A[U-1] */ 
    moveOver (A, U-1); 
    } 
    } 
} 

Я получил это от Berkeley CS класса я иду через интернет, обучение себя. это не домашнее задание (я бы хотел, но не так повезло). я не понимаю следующее:

Предположим, что числа в A [] равны 8, 2, 10, 5, 4, 12. Когда я использую их выше, я получаю это в своих итерациях, отслеживая его.

1. самый верхний индекс является U, или в этот случай 12, U-1 = 4, не подкачки не сделано
2. U теперь 4 (рекурсивный U-1), а число выше, это 5 (другой U-1). они меняются местами.
3. U теперь 4, потому что четыре просто поднялись и 10 U-1, они поменялись местами.

Моя последовательность в настоящее время 8,2,4,10,5,12.

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

Я не думаю, что правильно отслеживаю программу, и меня путают с рекурсией. Для этого, пожалуйста, предположите, что обмен сделан правильно.

спасибо.

себе

Answer 1

Что касается вашего следа: вы собираетесь неправильно в точке 2, так как условие if не выполняется, так что не рекурсивный вызов не будет когда-либо сделал.

Если рекурсия вас смущает, это может помочь переписать в итерационной форме:

static void moveOver (int A[], int U) { 
    while (U > 0 && A[U-1] > A[U]) { 
    /* Swap A[U], A[U-1] */ 
    --U; 
    } 
} 

Теперь легко видеть, что цикл остановится, как только встречается меньший элемент. Для того чтобы это был полный алгоритм сортировки, требуется больше работы. В любом случае, это не сортировка вставки; он больше похож на частичный вид пузыря для меня.

Теперь, откуда вы сказали, что у вас есть этот код?

Answer 2

Я думаю, что ключ к неправильному пониманию проблемы на самом деле скрытый в названии вашего вопроса

нидинга помощи в понимании вставки рода

алгоритм действительно только сортирует текущий элемент, но идея состоит в том, что его запуск выполняется каждый раз, когда элемент добавляется в массив. Таким образом, каждый раз его называемый остальной массив уже в порядке. Другими словами, вы только пытаетесь отсортировать позицию последнего элемента.

Таким образом, используя номера ваших примеров (8, 2, 10, 5, 4, 12) и добавляя/сортируя их по массиву по очереди, последовательность будет следующей: сортировка на каждом шаге происходит как вы уже описали):

To be added   | old array  | after push  | Result (after moveOver()) 
(8, 2, 10, 5, 4, 12)| []    | [8]   | [8] 
(2, 10, 5, 4, 12) | [8]   | [8,2]   | [2,8] 
(10, 5, 4, 12)  | [2,8]   | [2,8,10]  | [2,8,10] 
(5, 4, 12)   | [2,8,10]  | [2,8,10,5]  | [2,5,8,10] 
(4, 12)    | [2,5,8,10]  | [2,5,8,10,4] | [2,4,5,8,10] 
(12)    | [2,4,5,8,10] | [2,4,5,8,10,12]| [2,4,5,8,10,12]