Метод пузырьков в информатике

Метод пузырьков в информатике

  1. Алгоритм глупой сортировки
  2. Алгоритм пузырьковой сортировки
  3. Сортировка пузырьковым методом в Паскале
  4. Шейкерная сортировка

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

  • Слиянием;
  • Вставками;
  • Выбором;
  • С помощью распределения;
  • Гибридная;
  • Параллельная.

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

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

Алгоритм глупой сортировки

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

Алгоритм пузырьковой сортировки

Похожим на предыдущий способ является обменная или пузырьковая сортировка. Оперируя массивов данных с помощью рассматриваемой техники, мы немного меняем алгоритм глупого упорядочивания. Ранее вы находили пару «неправильных» чисел и поменяли их местами. В данном случае, нужно не возвращаться к началу ряда, а продолжать просмотр. Поэтапно следуя алгоритму, у вас получиться массив данных с наибольшим числом в конце ряда. Это достаточно простая техника, которая заключается в обмене соседних элементов. При следующем пересмотре массива, предпоследним числом окажется второе по значению. Сам метод обработки чисел остается прежним. Каждым таким этапом число, передвигающееся в конец ряда, оказывается самым большим. Чтобы правильно выполнить сортировку, во второй и следующие разы, вам стоит просматривать не весь массив, а лишь числа, с которыми вы работаете. Это все, кроме наибольшего последнего числа. Третья проверка происходит без последних двух. И так продолжается до тех пор, пока вы не распределите все данные. Максимальные элементы в результате перестроек постепенно перемещаются в конец ряда. На самом деле, пузырьковая техника проста и позволяет обработать массив быстрее и легче.

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

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

Рассматривая алгоритм сортировки данных, в нем выделяют такие ключевые моменты:

  • Сортировка происходит в два цикла. Первый из них используют при формировании шагов, а второй – под-шагов. Циклы представлены так, что один вложен в другой;
  • Алгоритм работает по принципу сравнения. Попеременно сопоставляя числа, происходит их перестановка по значению от меньшего к большему. Элементы меняются местами, если один из них на порядок или несколько выше;
  • Сама сортировка по пузырьковому методу распределена на шаги. Сравнение соседних пар чисел происходит таким образом, что каждый элемент учитывается дважды: 1 и 2, 2 и 3, 3 и 4 и т.д. В результате, самое большое число передвигается в правую сторону массива. Постепенное сравнение элементов формирует ряд, в котором слева располагаются числа с наименьшим значением, а по другую сторону – с наибольшим. Каждый раз в массив включается на одно число меньше, чем ранее. Все потому, что с одной проверкой ряда в конец перемещается по числу, которое больше остальных. В последующие алгоритмы оно не включается. 

Продемонстрируем, как происходит перегруппировка данных в массиве чисел. Предположим, у нас есть ряд с неотсортированными значениями 2, 5, 11, 1, 7, 8, 3. С процессом преобразования чисел можно ознакомиться на рисунке.

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

Замечание 1

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

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

Разновидность данной сортировки позволяет также быстро и качественно обработать массив данных. Ее также называют сортировкой по типу коктейль или перемешивание. Она также основана на технике пузырькового метода, но имеет некоторые отличия. Сходство в том, что числа проверяются последовательно. Следуя от меньшего к большему, происходит распределение и перестановка. Наибольшее значение оказывается в конце ряда. Далее алгоритм немного меняется, что отличает его от рассмотренных выше двух способов. Так называемый «разворот на 180 градусов» запускает проверку в направлении от большего к меньшему.

Источник