Пузырьковая сортировка (Bubble-sort). Сортировка пузырьком Сортировка пузырьком по возрастанию c

Метод пузырька

Сортировка простыми обменами , сортиро́вка пузырько́м (англ. bubble sort ) - простой алгоритм сортировки . Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n ²).

Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками .

Алгоритм

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

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

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

Примеры реализации

Python

Def swap(arr, i, j) : arr[ i] , arr[ j] = arr[ j] , arr[ i] def bubble_sort(arr) : i = len (arr) while i > 1 : for j in xrange (i - 1 ) : if arr[ j] > arr[ j + 1 ] : swap(arr, j, j + 1 ) i -= 1

VBA

Sub Sort(Mus() As Long ) Dim n As Long , i As Long , tmp As Long i = 1 Do While (i < UBound (Mus) ) If Mus(i) > Mus(i + 1 ) Then tmp = Mus(i) Mus(i) = Mus(i + 1 ) Mus(i + 1 ) = tmp If i > 1 Then i = i - 1 Else i = i + 1 End If Else i = i + 1 End If Loop End Sub

Усовершенствованный алгоритм сортировки пузырьком в Pascal

P:=True ; {Перестановка есть} K:=1 ; {Номер просмотра} While P Do Begin P:=false ; For i:=1 To n-k Do If X[ i] > X[ i+1 ] Then Begin A:=X[ i] ; X[ i] :=X[ i+1 ] ; X[ i+1 ] :=A; P:=true ; End ; k:=k+1 ; End ;

PHP

$size = count ($arr ) -1 ; for ($i = $size ; $i >=0 ; $i --) { for ($j = 0 ; $j <=($i -1 ) ; $j ++) if ($arr [ $j ] >$arr [ $j +1 ] ) { $k = $arr [ $j ] ; $arr [ $j ] = $arr [ $j +1 ] ; $arr [ $j +1 ] = $k ; } }

Всем привет!

Сегодня мы разберем сортировку методом "пузырька". Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык Pascal. И, так, что такое сортировка? Сортировка - это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.

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

• Простота реализации алгоритма
• Красивое название

• Один из самых медленных методов сортировки (Время выполнения квадратично зависит от длины массива n 2)
• Почти не применяется в реальной жизни (используется в основном в учебных целях)

Алгоритм: Берем элемент массива, сравниваем со следующим, если наш элемент, больше следующего элемента, то мы их меняем местами. После прохождения всего массива, мы можем быть уверены, что максимальный элемент будет "вытолкнут" - и стоять самым последним. Таким образом, один элемент у нас уже точно стоит на своём месте. Т.к. нам надо их все расположить на свои места, следовательно, мы должны повторить данную операцию, столько раз, сколько у нас элементов массива минус 1. Последний элемент встанет автоматически, если остальные стоят на своих местах.

Вернемся к нашему массиву:3 1 4 2
Берем первый элемент "3" сравниваем со следующим "1". Т.к. "3" > "1", то меняем местами:
1 3 4 2
Теперь сравниваем "3" и "4", тройка не больше четвёрки, значит ничего не делаем. Далее, сравниваем "4" и "2". Четыре больше, чем два - значит меняем местами: 1 3 2 4 . Цикл закончился. Значит самый большой элемент уже должен стоять на своём месте!! Видим, что у нас так и произошло. Где бы "4" (наш самый большой элемент) не находился - он всё равно, после прохождения циклом всего массива, будет последним. Аналогия - как пузырёк воздуха всплывает в воде - так и наш элемент, всплывает в массиве. Поэтому и алгоритм, называется "Пузырьковая сортировка". Чтобы расположить следующий элемент, необходимо, начать цикл сначала, но последний элемент можно уже не рассматривать, потому что он стоит на своём месте.

Теперь осталось запрограммировать данный алгоритм на языке Pascal. const n = 4; {Заводим константу, это будет длина массива} var i, j, k:integer; {Две переменные для вложенного цикла, одна для того чтобы элементы менять местами } m:array of integer; {Заводим массив} begin {Будем запрашивать массив с клавиатуры:} Writeln("Введите массив:"); for i:=1 to n do begin Writeln(i, " элемент:"); Readln(m[i]); end; {Внешний цикл отвечает за то, что мы должны повторить внутренний цикл столько раз, сколько у нас элементов массива минус 1.} for i:=1 to n-1 do begin {Внутренний цикл уже перебирает элементы и сравнивает между собой.} for j:=1 to n-i do begin {Если элемент, больше следующего, то меняем местами.} if m[j]>m then begin k:=m[j]; m[j]:=m; m:=k; end; end; end; {Выводи результат:} for i:=1 to n do Write(m[i], " "); end.
Вот результат:

А вот видеоурок

Расположим массив сверху вниз, от нулевого элемента - к последнему.

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

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

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

Template void bubbleSort(T a, long size) { long i, j; T x; for(i=0; i < size; i++) { // i - номер прохода for(j = size-1; j > i; j--) { // внутренний цикл прохода if (a > a[j]) { x=a; a=a[j]; a[j]=x; } } } }

Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta(n 2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся.

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

Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла(особенно, если массив был отсортирован с самого начала!).

Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.

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

Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.

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

Template void shakerSort(T a, long size) { long j, k = size-1; long lb=1, ub = size-1; // границы неотсортированной части массива T x; do { // проход снизу вверх for(j=ub; j>0; j--) { if (a > a[j]) { x=a; a=a[j]; a[j]=x; k=j; } } lb = k+1; // проход сверху вниз for (j=1; j<=ub; j++) { if (a > a[j]) { x=a; a=a[j]; a[j]=x; k=j; } } ub = k-1; } while (lb < ub); }

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

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

На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется.

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

Введение

Сортировка глазами машины и глазами человека

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

Done!

• Сравнить два элемента;
• Поменять местами или скопировать один из них;
• Перейти к следующему элементу;

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

• Вы перемещаетесь к нулевому элементу нашего массива (Черная Вдова);
• Сравниваете нулевой элемент (Черную Вдову) с первым (Халком);
• Если элемент на нулевой позиции оказался выше, вы меняете их местами;
• Иначе, если элемент на нулевой позиции меньше, вы оставляете их на своих местах;
• Производите переход на позицию правее и повторяете сравнение (сравниваете Халка с Капитаном)

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

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

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

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

Реализация пузырьковой сортировки на языке Java

• создает массив на 5 элементов;
• загружает в него рост мстителей;
• выводит на экран содержимое массива;
• реализует пузырьковую сортировку;
• осуществляет повторный вывод на экран отсортированного массива.