Может кто-нибудь объяснить мне логику этого утверждения о пузырьковой сортировке?

Question

Предположим, у нас есть массив с именем A.

пусть Π будет набором (x, y) пар, где x, y являются значениями, которые существуют в массиве A, и index (x) y.

так, например, если бы у нас был этот массив

      3 2 9 8 3 0

тогда (3,2) будет в Π. (3,0) также будет в Π.

все пары в Π будут следующими

   { (3,2), (3,0), (8,0), (9,0),(9,3),(2,0),(8,3),(9,8) }

Надеюсь, я ничего не забыл

Я понимаю, что если мы исправим все эти пары, то мы отсортируем массив. Когда я говорю «исправить», я имею в виду, например, (3,2) сделать его (2,3) и для других

что я не понимаю, так это сколько пар на каждом шаге исправляет пузырьковая сортировка? мой учитель сказал мне 1, и я не понимаю этого

Запустим пузырьковую сортировку

 3 2 9 8 3 0
 2 3 9 8 3 0
 2 3 9 8 3 0
 2 3 8 9 3 0
 2 3 8 3 9 0
 2 3 8 3 0 9

 2 3 8 3 0 9
 2 3 8 3 0 9
 2 3 3 8 0 9
 2 3 3 0 8 9

 2 3 3 0 8 9
 2 3 3 0 8 9
 2 3 0 3 8 9

 2 3 0 3 8 9
 2 0 3 3 8 9

 0 2 3 3 8 9

Есть ли какие-то шаги, когда пузырьковая сортировка ничего не исправляет? Итак, верный ли ответ, что пузырьковая сортировка будет фиксировать не более 1 балла за каждый шаг?

Answer 1

Bubble sort включает циклическое повторение массива. Во время каждого прохода по массиву он неоднократно меняет соседние элементы, которые вышли из строя при попадании в них.

Каждый шаг от одной записи к другой заменяется, только если элементы не в порядке.

Каждый проход через массив будет фиксировать по крайней мере одну пару из неупорядоченного порядка, если ее нет (т. Е. Массив уже отсортирован, а прохождение без изменений является сигналом завершения).

Я подозреваю, что вы думаете о шагах, а ваш профессор думает о проходах, но в любом случае он не совсем прав, так как некоторые проходы через весь массив могут исправить более одной неупорядоченной пары, а последний проход ничего не исправляет (поскольку в этой точке ничего не нужно исправлять).

Answer 2

Мне кажется, что в вашем примере набора данных пузырьковая сортировка всегда будет "фиксировать" ровно один элемент, потому что каждый элемент не в порядке. Однако, если бы вы переместили 0 ближе к началу исходного списка, вы бы сгенерировали несколько пар, которые уже находятся в отсортированном порядке. Эти пары не будут «фиксированы» с помощью пузырьковой сортировки, и в этом случае вы бы правильно сказали, что пузырьковая сортировка может «фиксировать» до 1 элемента на каждом шаге.

Так что в общем случае вы правы. В случае , который вы использовали в своем примере, учитель прав.

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