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

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

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

Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировка методом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: «метод пузырька»?

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

Алгоритм и особенности этой сортировки таковы:

1. При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и так далее. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
2. Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
3. При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
4. На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
5. В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
6. После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно M-1 , где M – это количество элементов массива.
7. Количество сравнений в каждом проходе равно m-i , где i – это номер прохода по массиву (первый, второй, третий и так далее).
8. При обмене элементов массива обычно используется «буферная» (третья) переменная, куда временно помещается значение одного из элементов.

Программа на языке Паскаль:

const M = 10; var arr: array[1..M] of integer; i, j, k: integer; begin randomize; write('Исходный массив: '); for i := 1 to M do begin arr[i] := random(100); write(arr[i]:3); end; writeln; for i := 1 to M-1 do for j := 1 to M-i do if arr[j] > arr[j+1] then begin k := arr[j]; arr[j] := arr[j+1]; arr[j+1] := k end; write('Отсортированный: '); for i := 1 to M do write (arr[i]:3); writeln; end.

Пример выполнения программы:

Исходный массив: 42 32 52 82 15 3 19 62 76 41 Отсортированный: 3 15 19 32 41 42 52 62 76 82

Уроки 58 — 61
Сортировка массива
(§ 21. Сортировка массива)
Составление программы на Паскале сортировки массива
Тест по теме «Программное управление работой компьютера»

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

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

Вывод результатов на экран организован так, чтобы на экране номера мест, занятых командами, названия команд и набранные очки выводились в три ровных столбца. Названия разных команд имеют разную длину. Самое длинное название у команды ТОРПЕДО-МЕТАЛЛУРГ состоит из 17 символов. Для выравнивания длин строк каждое название дополняется пробелами до 18 символов. Число добавляемых пробелов вычисляется так:

Здесь length ( ) — это стандартная функция, вычисляющая длину строки (число символов), указанной в скобках. Например, для ЦСКА длина строки равна 4, а для ТОРПЕДО-МЕТАЛЛУРГ длина равна 17. Значит, к ЦСКА добавится 14 пробелов, а к ТОРПЕДО-МЕТАЛЛУРГ — 1 пробел.

В операторе Team [I] : = Team [I] + ‘ ‘; используется операция «+» присоединения символов. В данном случае присоединяется пробел. К строке Team [l] добавится столько пробелов, сколько раз повторится присоединение. После этого по команде

Writeln(1:2,’ ‘,Team[I]:18, B[I]:2)

в ровные колонки выведутся места, названия команд и очки. Результаты будут иметь на экране следующий вид:

Демонстрации к уроку

Коротко о главном

Метод пузырька — алгоритм сортировки числового массива.

Структура алгоритма метода пузырька — два вложенных цикла с переменной длиной внутреннего цикла.

length() — функция определения длины строковой переменной.

В Паскале существует операция присоединения строк. Ее знак — «+».

Вопросы и задания

1. Как пояснить название метода сортировки массива — «метод пузырька»?

2. Сколько проходов с перестановками элементов потребуется при сортировке массива из 100 чисел?

3. Введите в компьютер программу Premier_liga_2.

а) Выполните ее, получите результаты. Сравните с результатами, приведенными в параграфе.

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

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

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

5. Условие то же, что и в предыдущем задании. Но в качестве исходных данных вводится еще два массива: с числом забитых и пропущенных мячей каждой командой.

Следующая страница Компьютерный практикум ЦОР. Сортировка массива (Задание 1 — 4)

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

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

Итак, представим, что у нас есть целочисленный массив из 10 элементов и нам его необходимо отсортировать по возрастанию.

Вот код программы на Паскале:

 const n = 10; var a:array[1..n] of integer; i,j,buf:integer; begin for i:=1 to n do begin a[i]:=random(10); write(a[i],' '); end;  for i:=1 to n-1 do for j:=i+1 to n do В этой строке начинающие программисты чаcто допускают ошибку> if a[i]>a[j] then begin buf:=a[i]; a[i]:=a[j]; a[j]:=buf; end; writeln; writeln('Массив после сортировки пузырьковым методом: '); for i:=1 to n do write(a[i],' '); end. 

Пояснения. Как видно из текста программы на Паскале, при сортировке массива методом пузырька, сравниваются два соседних элемента массива. В том случае, если элемент массива с номером i оказывается больше элемента массива с номером i+1 , происходит обмен значениями при помощи вспомогательной переменной buf (переменной я дал название со смысловой нагрузкой, от слова «буфер»).

Возможные ошибки. Как показывают мои личные наблюдения, начинающие программисты постоянно наступают на одни и те же грабли. Вместо строки «for j:=i+1 to n do» они зачастую пишут «for j:=2 to n do«, что хоть и приводит к обмену значениями некоторых переменных, но не дает необходимого результата.

При копировании материалов обратная ссылка обязательна

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

Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — один из квадратичных алгоритмов сортировки.

Алгоритм

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более [math] n — 1 [/math] проходов, где [math] n [/math] размер массива, чтобы отсортировать массив.

Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив [math] a[0..n — 1] [/math] .

function bubbleSort(a): for i = 0 to n - 2 for j = 0 to n - 2 if a[j] > a[j + 1] swap(a[j], a[j + 1])

Оптимизация

• Можно заметить, что после [math] i [/math] -ой итерации внешнего цикла [math] i [/math] последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до [math] n — 2 [/math] , а до [math] n — i — 2 [/math] .
• Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не [math] n — 1 [/math] раз, а до тех пор, пока во внутреннем цикле происходят обмены.

При использовании первой оптимизации сортировка принимает следующий вид:

function bubbleSort(a): for i = 0 to n - 2 for j = 0 to n - i - 2 if a[j] > a[j + 1] swap(a[j], a[j + 1])

При использовании же обеих оптимизаций сортировка пузырьком выглядит так:

function bubbleSort(a): i = 0 t = true while t t = false for j = 0 to n - i - 2 if a[j] > a[j + 1] swap(a[j], a[j + 1]) t = true i = i + 1

Сложность

В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма [math] T = T_1 + T_2 [/math] , где [math] T_1 [/math] — время, затрачиваемое на сравнение элементов, а [math] T_2 [/math] — время, за которое мы производим все необходимые обмены элементов.

Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество инверсий на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве [math] \frac [/math] . Получаем, что [math] T_2 = O(n^2) [/math] .

В неоптимизированной реализации на каждой итерации внутреннего цикла производятся [math] n — 1 [/math] сравнений, а так как внутренний цикл запускается также [math] n — 1 [/math] раз, то за весь алгоритм сортировки производятся [math] (n — 1)^2 [/math] сравнений.

В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен [math] \frac [/math] , а лучший — [math] n-1 [/math] . Следовательно, [math] T_1 = O(n^2) [/math] .

В итоге получаем [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] . Псевдокод указан ниже:

function oddEvenSort(a): for i = 0 to n - 1 if i mod 2 == 0 for j = 2 to n - 1 step 2 if a[j] < a[j - 1] swap(a[j - 1], a[j]) else for j = 1 to n - 1 step 2 if a[j] < a[j - 1] swap(a[j - 1], a[j])

Преимущество этой сортировки — на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.

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

Сортировка расческой (англ. comb sort) — модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность — [math] O(n^2) [/math] , но стремится к [math] O(n \log n) [/math] . Является самой быстрой квадратичной сортировкой. Недостаток — она неустойчива. Псевдокод указан ниже:

function combSort(a): k = 1.3 jump = n bool swapped = true while jump > 1 and swapped if jump > 1 jump /= k swapped = false for i = 0 to size - jump - 1 if a[i + jump] < a[i] swap(a[i], a[i + jump]) swapped = true 

Пояснения: Изначально расстояние между сравниваемыми элементами равно [math] \frac [/math] , где [math] k = 1<.>3 [/math] — оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.

Сортировка перемешиванием

Сортировка перемешиванием (англ. cocktail sort), также известная как Шейкерная сортировка — разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность — [math] O(n^2) [/math] , но стремится она к [math] O(k \cdot n) [/math] , где [math] k [/math] — максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:

function shakerSort(a): begin = -1 end = n - 2 while swapped swapped = false begin++ for i = begin to end if a[i] > a[i + 1] swap(a[i], a[i + 1]) swapped = true if !swapped break swapped = false end-- for i = end downto begin if a[i] > a[i + 1] swap(a[i], a[i + 1]) swapped = true 

См. также

• Сортировка выбором
• Сортировка вставками
• Сортировка кучей
• Сортировка слиянием
• Быстрая сортировка
• Сортировка подсчетом

Источники информации

• Сортировка пузырьком — Википедия
• Визуализатор
• Сортировка чет-нечет — Википедия
• Сортировка расческой — Википедия
• Сортировка перемешиванием — Википедия