Зачем пузырьковой сортировке нужны вложенные циклы?
Я собираюсь начать новый вопрос. Вчера я задал вопрос и хотел узнать, в чем проблема в моей программе. Программа приведена ниже, и вы, люди, указали, что эта следующая программа выполняет только один проход сортировки и также требует внешнего цикла. В то время я был в порядке. Но снова, когда я посмотрел программу, я запутался и должен спросить, зачем нам нужен внешний цикл для сортировки, поскольку только один цикл может выполнять сортировку (на мой взгляд). Сначала см. Программу ниже, а затем я представляю свою логику в конце программы.
Я думаю, что ЕДИНСТВЕННЫЙ цикл с условием пузырька должен выполнять сортировку. Посмотрите на следующий цикл программы:
Теперь я объясняю, о чем я думаю, что этот цикл «должен» делать. Сначала он сравнивает число [0] с числом [1]. Если условие выполнено, он будет делать то, что находится в теле оператора IF. Тогда i будет увеличен на 1 (i ++). Тогда на следующей итерации сравниваемые значения будут иметь номер [1] с номером [2]. Тогда почему этого не происходит и цикл завершается только после прохода? Другими словами, может быть, я пытаюсь спросить, что оператор IF не повторяется в цикле for? На мой взгляд, да. Я очень благодарен за помощь и мнения, мой вопрос может быть незначительным, но так я буду прогрессировать.
4 ответа
Позвольте мне привести пример, давайте возьмем только 3 числа. Итак, вы вводите
Теперь вы начинаете разбираться, как вы это сделали. так что сравнивает 13 и 3 13 > 3 поменяйте местами их обоих. теперь у нас есть.
Теперь будет сравнивать, как вы сказали, следующая пара = 13 и 1. 13 > 1 , чтобы новый заказ был
Теперь ваш цикл завершен, и вы пропустили сравнение 3 и 1. На самом деле первый цикл сортирует только наибольшее число!
Это неверно, потому что
Алгоритм получил свое название от того, как более мелкие элементы «всплывают» вверху списка. (пузырьковая сортировка)
Итак, в конце первого цикла мы получаем наименьший элемент . Итак, для полной сортировки нам нужно оставить всего n циклов . (где n = общий размер чисел)
Для пузырьковой сортировки проход просто перемещает самый большой элемент в конец массива. Итак, вам нужно n-1 проходов, чтобы получить отсортированный массив, поэтому вам нужен другой цикл. Теперь для вашего кода 1 проход означает
Так что, как вы можете видеть, оператор IF повторяется, просто после всех 9 IF самый большой элемент перемещается в конец массива
так как только один цикл может выполнять сортировку (на мой взгляд)
Это не так. Не вдаваясь в подробности, постоянного количества циклов недостаточно для сортировки , поскольку сортировка является проблемой Omega(nlogn) . То есть O(1) (постоянного, включая 1) количества циклов для этого недостаточно — для любого алгоритма 1,2 .
Достаточно одного цикла пузырьковой сортировки:
Таким образом, алгоритм получит массив: [ 4, 3, 2, 1, 5] , который НЕ сортируется.
После одного цикла пузырьковой сортировки гарантированно останется только последний элемент (что действительно происходит в примере). Вторая итерация гарантирует, что два последних элемента находятся на своих местах, а n -я итерация гарантирует, что массив действительно отсортирован, что приводит к циклам n , что достигается с помощью вложенного цикла.
(1) Внешний цикл иногда скрывается как рекурсивный вызов (пример быстрой сортировки) бывает) — но петля все равно остается.
(2), если быть точным, на основе сравнений.
Сортировка пузырьком
Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — один из квадратичных алгоритмов сортировки.
Содержание
Алгоритм [ править ]
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более [math] n — 1 [/math] проходов, где [math] n [/math] размер массива, чтобы отсортировать массив.
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив [math] a[0..n — 1] [/math] .
Оптимизация [ править ]
- Можно заметить, что после [math] i [/math] -ой итерации внешнего цикла [math] i [/math] последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до [math] n — 2 [/math] , а до [math] n — i — 2 [/math] .
- Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не [math] n — 1 [/math] раз, а до тех пор, пока во внутреннем цикле происходят обмены.
При использовании первой оптимизации сортировка принимает следующий вид:
При использовании же обеих оптимизаций сортировка пузырьком выглядит так:
Сложность [ править ]
В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма [math] T = T_1 + T_2 [/math] , где [math] T_1 [/math] — время, затрачиваемое на сравнение элементов, а [math] T_2 [/math] — время, за которое мы производим все необходимые обмены элементов.
Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество инверсий на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве [math] \frac
В неоптимизированной реализации на каждой итерации внутреннего цикла производятся [math] n — 1 [/math] сравнений, а так как внутренний цикл запускается также [math] n — 1 [/math] раз, то за весь алгоритм сортировки производятся [math] (n — 1)^2 [/math] сравнений.
В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен [math] \frac
В итоге получаем [math] T = T_1 + T_2 = O(n^2) + O(n^2) = O(n^2) [/math] .
Пример работы алгоритма [ править ]
Возьмём массив [math] [5, 1, 4, 2, 8] [/math] и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Первый проход:
| До | После | Описание шага |
|---|---|---|
| 5 1 4 2 8 | 1 5 4 2 8 | Здесь алгоритм сравнивает два первых элемента и меняет их местами. |
| 1 5 4 2 8 | 1 4 5 2 8 | Меняет местами, так как 5 > 4 |
| 1 4 5 2 8 | 1 4 2 5 8 | Меняет местами, так как 5 > 2 |
| 1 4 2 5 8 | 1 4 2 5 8 | Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами. |
Второй проход:
| До | После | Описание шага |
|---|---|---|
| 1 4 2 5 8 | 1 4 2 5 8 | |
| 1 4 2 5 8 | 1 2 4 5 8 | Меняет местами, так как 4 > 2 |
| 1 2 4 5 8 | 1 2 4 5 8 | |
| 1 2 4 5 8 | 1 2 4 5 8 |
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена.
Модификации [ править ]
Сортировка чет-нечет [ править ]
Сортировка чет-нечет (англ. odd-even sort) — модификация пузырьковой сортировки, основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность — [math] O(n^2) [/math] . Псевдокод указан ниже:
Преимущество этой сортировки — на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.
Сортировка расческой [ править ]
Сортировка расческой (англ. comb sort) — модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность — [math] O(n^2) [/math] , но стремится к [math] O(n \log n) [/math] . Является самой быстрой квадратичной сортировкой. Недостаток — она неустойчива. Псевдокод указан ниже:
Пояснения: Изначально расстояние между сравниваемыми элементами равно [math] \frac
Сортировка перемешиванием [ править ]
Сортировка перемешиванием (англ. cocktail sort), также известная как Шейкерная сортировка — разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность — [math] O(n^2) [/math] , но стремится она к [math] O(k \cdot n) [/math] , где [math] k [/math] — максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:
Вопрос по пузырьковой сортировке в Паскале. Зачем нужны два цикла и почему у второго ограничение сверху (arrayLength-i)?
Потому, что сортировка требует множества проходов по массиву — что и обеспечивается вложенностью циклов. В данном варианте сортировки после каждого прохода внутреннего цикла на своё место встаёт один элемент: сначала последний, потом предпоследний и т. д. — упорядочивание идёт справа налево.
Чтобы ускорить сортировку — не тратя время на анализ уже отсортированного «хвоста» массива.