Способ сортировки пузырьком c

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

Реализация сортировки методом «пузырька» на Си

Анализ алгоритма

Число сравнений в алгоритме прямого обмена

С = (n 2 — n)/2,

а минимальное, среднее и максимальное число перемещений элементов равно соответственно

Mmin = 0,

Mср = 3(n2 — n)/2,

Mmax = 3(n2 — n)/4.

Резюме : «обменная сортировка» представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора; фактически в пузырьковой сортировке нет ничего ценного, кроме привлекательного названия.

Источник

Сортировка пузырьком C: все про bubble sort простыми словами

Сортировка пузырьком может осуществляться во многих языках программирования, в том числе и в С. Это достаточно простой способ сортировки, который очень легко реализуется. Его изучают в числе первых в теме «теория алгоритмов», но применяется он крайне редко.

Сегодня мы простыми словами разберем, что такое сортировка пузырьком в Си.

Сортировка пузырьком

Под такой сортировкой понимают многократное прохождение алгоритма по массиву, который нужно отсортировать. При каждом таком «погружении»-прохождении по массиву его элементы будут попарно сравниваться. Если сравниваемые элементы неверно расположены, то они «меняются местами». Подобные «погружения» в массив будут осуществляться такое количество раз, какое потребуется для того, чтобы все элементы массива были правильно отсортированы.

При такой сортировк е элементы с «наибольшим» значением «погружаются» в глубь массива, а элементы с «наименьшим» значением «всплывают» в начало массива.

Сортировка пузырьком на простом примере

Представим, что у нас есть некий числовой массив со значениями «6, 2, 5, 3, 9». Нам нужно отсортировать элементы данного массива по возрастанию, для этого будет применяться сортировка пузырьком.

Написав алгоритм сортировки , мы получим отсортированный массив через несколько проходов алгоритма.

Первое «погружение» в массив

( 6, 2, 5, 3, 9) — ( 2, 6, 5, 3, 9) — наш алгоритм сравнил первые элементы и переместил «2», так как 2

(2, 6, 5, 3, 9) — (2, 5, 6, 3, 9) — наш алгоритм сравнил следующие элементы и переместил «5» чуть выше, так как 5

(2, 5, 6, 3, 9) — (2, 5, 3, 6, 9) — наш алгоритм сравнил следующие элементы и переместил «3» выше, так как 3

(2, 5, 3, 6, 9 ) — (2, 5, 3, 6, 9 ) — наш алгоритм сравнивает последнюю пару элементов и оставляет их на своих местах, так как требования соблюдаются.

Так как за одно прохождение по массиву сам массив не был отсортирован до конца, у нас будет еще одно прохождение.

Второе «погружение» в массив

( 2, 5, 3, 6, 9) — ( 2, 5, 3, 6, 9) — алгоритм сравнивает первую пару элементов и ничего не меняет, та к как все соответствует требованиям;

(2, 5, 3, 6, 9) — (1, 3, 5, 6, 9) — алгоритм сравнивает следующую пару элементов и поднимает «3» выше, так как 3

(1, 3, 5, 6, 9) — (1, 3, 5, 6, 9) — алгоритм сравнивает следующую пару элементов и оставляет все как есть;

(1, 3, 5, 6, 9 ) — (1, 3, 5, 6, 9 ) — алгоритм сравнивает следующую пару элементов и тоже оставляет все как есть.

Готово! Наш массив отсортирован, но это на примере видим мы , а не сам алгоритм. Поэтому будет еще одно прохождение по массиву с попарным сравнением элементов, чтобы алгоритм сам удостоверился, что все элементы расположены согласно требованиям. Только после финального прохождения, когда алгоритм убеди тся, что все в порядке, сам алгоритм завершит свою работу.

Как реализуется сортировка пузырьком в С (Си)

Сортировка пузырьком в С реализуется по следующему шаблону:

Источник

Пузырьковая сортировка в C++: главные моменты

Всем привет! Наверно всем прогерам в какой-то момент нужно было отсортировать массив. Сегодня мы разберем алгоритм сортировки с помощью которого вы сможете отсортировать ваш массив или вектор. Вы наверное догадались с названия сегодня пойдет речь о пузырьковой сортировке.

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

Что такое пузырьковая сортировка

Пузырьковая сортировка — наверно самая простая сортировка, которую я встречал. Обычно она встречается в книгах по программированию и не выходит за ее пределы. Так как она работает намного медленнее, чем другие алгоритмы сортировки.

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

Как работает алгоритм пузырьковой сортировки

Принцип работы пузырьковой сортировки можно описать в три пункта:

1. Прохождение по всему массиву;
2. Сравнивание между собой пар соседних ячеек;
3. Если при сравнении оказывается, что значение ячейки i больше, чем значение ячейки i + 1 , то мы меняем значения этих ячеек местами;

Ниже вы можете увидеть, как работает пузырьковая сортировка в действии.

Как создать пузырьковую сортировку

Вот что нам придется делать для создания пузырьковой сортировки:

• Создать два цикла for , чтобы проходить по всем элементам массива N раз ( N это размер массива).
• Сравнивать ячейки массива, с помощью оператора ветвления if .
• Менять местами значения ячеек.

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

Давайте поподробнее разберем строки 16 — 24 (здесь находится пузырьковая сортировка):

1. В строке 16: мы создали первый цикл for .
2. В строке 17: аналогично был создан второй, но уже вложенный цикл.
3. В строке 18: происходит сравнивание двух элементов.
   • Если результат этого условия положительный , то мы меняем значение элементов.
   • Если же результат отрицателен , то мы пропускаем этап смены значений.
4. В строке 19: создали переменную b , чтобы менять значения ячеек digitals[i] и digitals[i + 1] местами.

Давайте посмотрим, что выведет программа выше при запуске:

Как улучшить пузырьковую сортировку

Ниже вы можете видеть оптимизированную версию пузырьковой сортировки.

Давайте посмотрим, что мы сделали для ее оптимизации:

В строке 17: изменили условие внутреннего цикла на i .

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

Для этого в строке 5: чтобы пузырьковая сортировка останавливалась (когда массив уже стал отсортирован), мы объявили булеву переменную flag (ее обычно называют флаг или флажок). Еще при ее инициализации мы поместили значение true , но она меняется на:

• false , если результат условия в строке 4: положительный .

Вы также можете объявить переменную flag типа int и вместо true или false хранить в переменной значение 1 и 0.

А в строке 9: чтобы мы могли выйти из алгоритма мы проверяем:

• Если булева переменная равна true , значит массив уже полностью отсортирован и можно выйти. Для этого используем оператор break .
• Если же значение flag равно false , то продолжаем сортировать массив.

В строке 6: вы (возможно) увидели незнакомую функцию swap . Если коротко описать что она делает, то она принимает два аргумента (через запятую) и меняет их значения местами. В нашем случаи она принимает ячейки digitals[j] и digitals[j + 1] . Мы использовали эту функцию чтобы не писать вот эти 3 строчки:

Источник

Пузырьковая сортировка и все-все-все

Все отлично знают, что из класса обменных сортировок самый быстрый метод – это так называемая быстрая сортировка. О ней пишут диссертации, её посвящено немало статей на Хабре, на её основе придумывают сложные гибридные алгоритмы. Но сегодня речь пойдёт не про quick sort, а про другой обменный способ – старую добрую пузырьковую сортировку и её улучшения, модификации, мутации и разновидности.

Практический выхлоп от данных методов не ахти какой и многие хабрапользователи всё это проходили ещё в первом классе. Поэтому статья адресована тем, кто только-только заинтересовался теорией алгоритмов и делает в этом направлении первые шаги.

Сегодня поговорим о простейших сортировках обменами.

Если кому интересно, скажу, что есть и другие классы – сортировки выбором, сортировки вставками, сортировки слиянием, сортировки распределением, гибридные сортировки и параллельные сортировки. Есть, кстати, ещё эзотерические сортировки. Это различные фейковые, принципиально нереализуемые, шуточные и прочие псевдо-алгоритмы, про которые я в хабе «IT-юмор» как-нибудь напишу пару статей.

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

Заранее предупрежу, что почти все приведённые способы весьма медленные и глубокого анализа их временной сложности не будет. Какие-то побыстрее, какие-то помедленнее, но, грубо говоря, можно сказать, что в среднем O(n 2 ). Также я не вижу резона загромождать статью реализациями на каких-либо языках программирования. Заинтересовавшиеся без малейшего труда смогут найти примеры кода на Розетте, в Википедии или где-нибудь ещё.

Но вернёмся к сортировкам обменами. Упорядочивание происходит в результате многократного последовательного перебора массива и сравнения пар элементов между собой. Если сравниваемые элементы не отсортированы друг относительно друга – то меняем их местами. Вопрос только в том, каким именно макаром массив обходить и по какому принципу выбирать пары для сравнения.

Начнём не с эталонной пузырьковой сортировки, а с алгоритма, который называется…

Глупая сортировка

Сортировка и впрямь глупейшая. Просматриваем массив слева-направо и по пути сравниваем соседей. Если мы встретим пару взаимно неотсортированных элементов, то меняем их местами и возвращаемся на круги своя, то бишь в самое начало. Снова проходим-проверяем массив, если встретили снова «неправильную» пару соседних элементов, то меняем местами и опять начинаем всё сызнова. Продолжаем до тех пор пока массив потихоньку-полегоньку не отсортируется.

«Так любой дурак сортировать умеет» — скажете Вы и будете абсолютно правы. Именно поэтому сортировку и прозвали «глупой». На этой лекции мы будем последовательно совершенствовать и видоизменять данный способ. Сейчас у него временная сложность O(n 3 ), произведя одну коррекцию, мы уже доведём до O(n 2 ), потом ускорим ещё немного, потом ещё, а в конце концов мы получим O(n log n) – и это будет вовсе не «Быстрая сортировка»!

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

В этом случае перед нами не что иное как всем известная…

Пузырьковая сортировка

Или сортировка простыми обменами. Бессмертная классика жанра. Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.

Если не только в конец задвигать максимумы, а ещё и в начало перебрасывать минимумы то у нас получается…

Шейкерная сортировка

Она же сортировка перемешиванием, она же коктейльная сортировка. Начинается процесс как в «пузырьке»: выдавливаем максимум на самые задворки. После этого разворачиваемся на 180 0 и идём в обратную сторону, при этом уже перекатывая в начало не максимум, а минимум. Отсортировав в массиве первый и последний элементы, снова делаем кульбит. Обойдя туда-обратно несколько раз, в итоге заканчиваем процесс, оказавшись в середине списка.

Шейкерная сортировка работает немного быстрее чем пузырьковая, поскольку по массиву в нужных направлениях попеременно мигрируют и максимумы и минимумы. Улучшения, как говорится, налицо.

Как видите, если к процессу перебора подойти творчески, то выталкивание тяжёлых (лёгких) элементов к концам массива происходит быстрее. Поэтому умельцы предложили для обхода списка ещё одну нестандартную «дорожную карту».

Чётно-нечётная сортировка

На сей раз мы не будем сновать по массиву взад-вперёд, а снова вернёмся к идее планомерного обхода слева-направо, но только сделаем шире шаг. На первом проходе элементы с нечётным ключом сравниваем с соседями, зиждущимися на чётных местах (1-й сравниваем со 2-м, затем 3-й с 4-м, 5-й с 6-м и так далее). Затем наоборот – «чётные по счёту» элементы сравниваем/меняем с «нечётными». Затем снова «нечёт-чёт», потом опять «чёт-нечет». Процесс останавливается тогда, когда после подряд двух проходов по массиву («нечётно-чётному» и «чётно-нечётному») не произошло ни одного обмена. Стало быть, отсортировали.

В обычном «пузырьке» во время каждого прохода мы планомерно выдавливаем в конец массива текущий максимум. Если же передвигаться вприпрыжку по чётным и нечётным индексам, то сразу все более-менее крупные элементы массива одновременно за один пробег проталкиваются вправо на одну позицию. Так получается быстрее.

Разберём последнее покращення* для Сортування бульбашкою** — Сортування гребінцем***. Этот способ упорядочивает весьма шустро, O(n 2 ) – его наихудшая сложность. В среднем по времени имеем O(n log n), а лучшая даже, не поверите, O(n). То есть, весьма достойный конкурент всяким «быстрым сортировкам» и это, заметьте, без использования рекурсии. Впрочем, я обещал, что в крейсерские скорости мы сегодня углубляться не станем, засим умолкаю и перехожу непосредственно к алгоритму.

Во всём виноваты черепашки

Небольшая предыстория. В 1980 году Влодзимеж Добосиевич пояснил почему пузырьковая и производные от неё сортировки работают так медленно. Это всё из-за черепашек. «Черепахи» — небольшие по значению элементы, которые находятся в конце списка. Как Вы, возможно, заметили пузырьковые сортировки ориентированы на «кроликов» (не путать с «кроликами» Бабушкина) – больших по значению элементов в начале списка. Они весьма резво перемещаются к финишу. А вот медлительные пресмыкающиеся на старт ползут неохотно. Подгонять «тортилл» можно с помощью расчёски.

image: виноватая черепашка

Сортировка расчёской

В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние элементы. Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди.

Первоначальный разрыв между сравниваемыми элементами лучше брать не абы какой, а с учётом специальной величины называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247. Сначала расстояние между элементами равно размеру массива разделённого на фактор уменьшения (результат, естественно, округляется до ближайшего целого). Затем, пройдя массив с этим шагом, мы снова делим шаг на фактор уменьшения и проходим по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае массив досортировывается обычным пузырьком.

Опытным и теоретическим путём установлено оптимальное значение фактора уменьшения:

Когда был изобретён этот метод, на него на стыке 70-х и 80-х мало кто обратил внимание. Десятилетие спустя, когда программирование перестало быть уделом учёных и инженеров IBM, а уже лавинообразно набирало массовый характер, способ переоткрыли, исследовали и популяризировали в 1991 году Стивен Лейси и Ричард Бокс.

Вот собственно и всё что я хотел Вам рассказать про пузырьковую сортировку и иже с ней.

* покращення (укр.) – улучшение
** Сортування бульбашкою (укр.) – Сортировка пузырьком
*** Сортування гребінцем (укр.) – Сортировка расчёской

Источник