Может ли кто-нибудь предоставить мне лучшее доказательство и сценарий для пузырьковой сортировки по сравнению с тем, что я доказал?

Question

Дайте список несортированных элементов. Начальное условие: A= список несортированных элементов, p=1, N= общий размер массива.

Bubble(A,p,N)
 if p>=N return
 for i=p to N-1
  if A[i]>A[i+1]
   swap(A[i],A[i+1])
 Bubble(A,p,N-1)

Вопрос 1: Докажите правильность алгоритма по индукции на N. Моя проблема: Как я могу использовать k+1 на Bubble(A,p,N-1)? Мне нужен кто-то, чтобы объяснить и доказать для меня.

Вопрос 2: Докажите, что если элемент однажды переместится в направлении n, он никогда не будет перемещаться в направлении p для текущих и всех последующих рекурсивных вызовов.(Не решено)

Моя проблема: я знаю, что после завершения первого n-1 для цикла сортировки, наибольшее целочисленное значение в массиве будет сортироваться в последней позиции. когда рекурсия Bubble (A, p, N-1) вызывается, размер массива будет n-1,n-2,...nn, а наибольшее целое число в последнем больше не будет сравниваться для следующего и предстоящего вызова рекурсии (Это хорошее доказательство? Если нет, может кто-нибудь предоставить мне лучшее доказательство?)

Вопрос 3: Приведите сценарий того, что после того, как элемент переместится в сторону p, он может переместиться в сторону n

Моя проблема: я знаю, что для тока для цикла от 1 до n-1, если A[i]>A[i+1], то он поменяется местами, где A [i + 1] будет наибольшим, а A [i] будет самым маленьким. Затем, когда вызывается Bubble (A, p, N-1), целое значение размера массива n-1 будет снова сравниваться. Если A[i]>A[i+1], то поменяйте местами. Элементы будут сравниваться и заменяться на n-1,n-2,...,nn.(Это хороший сценарий? Если нет, то может ли кто-нибудь предоставить мне лучший сценарий?)

Answer 1

Вопрос 1: Докажите правильность алгоритма по индукции на N. Моя проблема: Как я могу использовать k+1 на Bubble(A,p,N-1)? Мне нужен кто-то, чтобы объяснить и доказать для меня.

Доказательство проводится индукцией по N.

Базовый случай: когда N = 1, массив уже отсортирован, и Bubble правильно ничего не делает и немедленно завершает if p >= N return,

Индукционная гипотеза: предположим Bubble правильно сортирует списки по размеру вплоть до k (сильная индукция).

Индуктивный шаг: мы должны показать Bubble правильно сортирует списки по размеру k+1, На начальном вызове Bubble, p меньше чем N = k+1 и поэтому мы пропускаем первую строку алгоритма. Далее for цикл может быть показан (также с использованием индукции), чтобы обладать следующим инвариантом цикла: на итерации i = m, A[m+1] будет больше или равно A[1] через A[m], Цикл, следовательно, заканчивается наибольшим элементом в A[1], A[2], ..., A[k+1] в положении k+1, Затем он делает рекурсивный вызов проблемы, если размер k который, по предположению индукции, Bubble гарантированно правильно отсортировать. поскольку A[k+1] является самым большим элементом и находится в конце, и так как все более ранние элементы отсортированы правильно рекурсивным вызовом Bubbleсортировка оказалась правильной.

(Индуктивное доказательство другого оставлено в качестве упражнения. Выберите в качестве базового случая N=2 и p=1. Затем предположите, что инвариант верен до k, Покажите это для k+1 рассуждая о том, что swap делает. Затем на основе последнего значения, принятого p, скажи, каким должно быть конечное состояние массива.)

Вопрос 2: Докажите, что если элемент однажды переместится в направлении n, он никогда не будет перемещаться в направлении p для текущих и всех последующих рекурсивных вызовов.(Не решено)

Доказательство от противного. Рассмотрим элемент в положении i в начале некоторого вызова Bubble тронут swapв for цикл в положение j > i, Предположим, что дальше swapс тем же вызовом, или swapс в другом вызове Bubbleвызвать положение этого элемента, чтобы k с k < j, Нам нужно только рассмотреть первое такое движение, поскольку, если оно есть, есть первое. Первое такое движение связано либо с swap в том же вызове или swap в другом вызове. Рассмотрим эти случаи отдельно.

1. swaps в текущем вызове могут только перемещать элементы вперед, а не назад. Поскольку элемент, который был заменен во время этого вызова, никогда не может быть "следующим" элементом для любого обмена, он не может двигаться назад.

2. swapс другими вызовами Bubble потенциально может переместить элемент, так как элемент будет "следующим" элементом для одного из потенциальных swaps; однако этого никогда не произойдет, поскольку это будет означать, что в массиве ранее имеется более крупный элемент, который был бы "пузырился" за рассматриваемым элементом при предыдущем вызове "пузыря". Мы предполагали, что наш элемент сместился вправо, а это означает, что он был самым крупным из всех, что мы когда-либо видели.

Поскольку это единственные два пути, по которым элемент может двигаться p и ни один из них не возможен, у нас есть противоречие, означающее наше предположение, что элемент может двигаться в направлении p ложно

Изменить: для вопроса 3 рассмотрим случай массива [3, 2, 1]. Первый обмен меняет 3 и 2, двигаясь 2 в направлении р. Второй обмен обменивает 3 и 1, двигаясь 1 к р. Первый обмен рекурсивного вызова Bubble обменивает 1 и 2, двигая 2 назад к n. Как правило, вы получите описанное поведение, которое многие из вас начнут с массива в обратном порядке.