Нужна помощь в понимании сортировки вставок - PullRequest
Новая
       22

Нужна помощь в понимании сортировки вставок

0 голосов
/ 29 января 2010

В этом коде, как это работает (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);
    }
  }
}

Я получил это из класса Беркли 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.

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

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

Спасибо.

1024 * SE *

Ответы [ 2 ]

1 голос
/ 29 января 2010

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

Требуется помощь в понимании вставка сортировка

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

Итак, используя ваши примеры чисел (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]
0 голосов
/ 29 января 2010

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

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

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

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

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

...