Как сделать сортировку пузырьком python
Сортировка методом пузырька заключается в том, что по массиву осуществляются множественные проходы. На каждом проходе очередной элемент сравнивается со следующим за ним. И если он больше (при сортировке по возрастанию), то элементы массива меняются местами.
Таким образом при первом проходе по массиву при сортировке по возрастанию последним в массиве оказывается самое большое значение. При следующем проходе на предпоследнем месте окажется максимальное из оставшихся чисел. Сравнивать последнее и предпоследнее числа нет смысла. Поэтому количество просматриваемых элементов массива на каждом проходе сокращается на 1. Количество проходов равно количеству элементов массива за вычетом единицы, т.к. происходит попарное сравнение.
Pascal
сортировка пузырьком паскаль
Язык Си
Python
сортировка пузырьком Python (питон)
В Питоне при обмене значений переменных можно обойтись без буферной переменной. Это делается с помощью присваивания в одном выражении. Такая возможность существует, т.к. в Python перед присваиванием в подобных выражениях сначала формируются кортежи.
КуМир
Basic-256
сортировка пузырьком паскаль
const
N = 10;
var
arr: array[1..N] of integer;
i, j, k: integer;
begin
randomize;
for i:=1 to N do begin
arr[i] := random(256);
write (arr[i]:4);
end;
writeln;
for i:=1 to N-1 do
for j:=1 to N-i do
if arr[j] > arr[j+1] then begin
k := arr[j];
arr[j] := arr[j+1];
arr[j+1] := k
end;
for i:=1 to N do
write (arr[i]:4);
writeln;
end.
97 8 156 88 3 99 217 170 135 133
3 8 88 97 99 133 135 156 170 217
сортировка пузырьком Python (питон)
from random import random
a = [0]*10
for i in range(10):
a[i] = int(random()*100)
print(a)
for i in range(9):
for j in range(9-i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
print(a)
[42, 9, 95, 78, 59, 14, 50, 79, 54, 84]
[9, 14, 42, 50, 54, 59, 78, 79, 84, 95]
В Питоне при обмене значений переменных можно обойтись без буферной переменной. Это делается с помощью присваивания в одном выражении. Такая возможность существует, т.к. в Python перед присваиванием в подобных выражениях сначала формируются кортежи.
алг сортировка пузырьком
нач
цел N = 10
цел таб arr[1:N]
цел i,j,k
нц для i от 1 до N
arr[i] := int(rand(0,100))
вывод arr[i], " "
кц
вывод нс
нц для i от 1 до N-1
нц для j от 1 до N-i
если arr[j] > arr[j+1] то
k := arr[j]
arr[j] := arr[j+1]
arr[j+1] := k
все
кц
кц
нц для i от 1 до N
вывод arr[i], " "
кц
кон
41 38 95 61 71 1 20 14 83 61
1 14 20 38 41 61 61 71 83 95
dim a(10)
for i =0 to 9
a[i] = int(rand()*100)
print a[i] + " ";
next i
print
Пузырьковая сортировка делает по списку несколько проходов. Она сравнивает стоящие рядом элементы и меняет местами те из них, что находятся в неправильном порядке. Каждый проход по списку помещает следующее наибольшее значение на его правильную позицию. В сущности, каждый элемент “пузырьком” всплывает на своё место.
Рисунок 1 показывает первый проход пузырьковой сортировки. Затенёные элементы будут сравниваться для определения в правильном ли порядке они стоят. Если в списке \(n\) элементов, то за первый проход потребуется сравнить \(n-1\) пару. Важно отметить, что поскольку наибольшее значение - часть пары, то оно будет перемещаться вдоль списка до завершения прохода.
Рисунок 1: bubbleSort : первый проход
К началу второго прохода наибольшее значение стоит на своём месте. Остаётся \(n-1\) число для сортировки, или \(n-2\) пары. Поскольку каждый проход помещает следующее наибольшее значение на положенное место, то общее количество проходов равняется \(n-1\) . После завершения \(n-1\) прохода наименьший элемент будет на верной позиции без дополнительных вычислений. ActiveCode 1 демонстрирует функцию bubbleSort целиком. Она принимает список в качестве параметра и при необходимости изменяет его с помощью перестановок элементов.
Операция перестановки, иногда называемая “обменом”, в Python несколько проще, чем в большинстве других языков программирования. Обычно перестановка местами двух элементов списка требует временного сохранения их местоположения (дополнительный объём памяти). Следующий фрагмент кода
меняет местами i-й и j-й элементы списка. Одно из значений будет переписано безо всякого временного хранилища.
В Python возможно одновременное присваивание. Оператор a,b = b,a даст тот же результат, что и два присваивания, сделанных в одно и то же время (см. рисунок 2). С использованием одновременного присваивания операция обмена займёт всего в одну строку.
Строки 5-7 в ActiveCode 1 производят обмен \(i\) -го и \((i+1)\) -го элементов, используя трёхступенчатую операцию, описанную выше. Заметьте, что для перестановки элементов мы также можем использовать одновременное присваивание.
Рисунок 2: Перестановка местами двух значений в Python
Следующий пример ActiveCode демонстрирует законченную функцию bubbleSort , работающую со списком, показанным выше.
Пузырьковая сортировка (lst_bubble)
Эта анимация показывает bubbleSort в действии.
Для большей детализации CodeLens позволит вам пройти по алгоритму шаг за шагом.
Трассировка пузырьковой сортировки (bubbletrace)
При анализе пузырьковой сортировки стоит отметить, что, вне зависимости от первоначального порядка элементов, для списка из \(n\) элементов будет сделан \(n-1\) проход. Таблица 1 показывает число сравнений при каждом проходе. Общее их количество - сумма первых \(n-1\) чисел. Напомним, что сумма первых \(n\) целых равна \(\fracn^ + \fracn\) . Сумма первых \(n-1\) чисел равна \(\fracn^ + \fracn - n\) , или после сокращения \(\fracn^ - \fracn\) . Т.е. это по-прежнему \(O(n^)\) сравнений. В лучшем случае, когда список уже отсортирован, не будет сделано ни одной перестановки. Однако, для наихудшего случая каждое сравнение повлечёт за собой обмен. В среднем же обмен займёт половину времени.
| Проход | Количество сравнений |
|---|---|
| 1 | \(n-1\) |
| 2 | \(n-2\) |
| 3 | \(n-3\) |
| . | . |
| \(n-1\) | \(1\) |
Пузырьковая сортировка часто рассматривается как наиболее неэффективный сортировочный метод, поскольку она должна переставлять элементы до того, как станет известна их окончательная позиция. Эти “пустые” операции обмена весьма затратны. Однако, поскольку пузырьковая сортировка делает проход по всей несортированной части списка, она умеет то, что не могут большинство сортировочных алгоритмов. В частности, если во время прохода не было сделано ни одной перестановки, то мы знаем, что список уже отсортирован. Таким образом, алгоритм может быть модифицирован, чтобы останавливаться раньше, если обнаруживает, что задача выполнена. Т.е. для списков, которым нужно всего несколько проходов, пузырьковая сортировка имеет преимущество, поскольку умеет распознать сортированный список и остановиться. ActiveCode 2 демонстрирует эту модификацию, которую часто называют коротким пузырьком.
Иногда данные, которые мы храним или извлекаем в приложении, могут находится в беспорядочном состояние. И иногда возникает необходимость упорядочивания данные прежде чем их можно будет эффективно использовать. За все эти годы учеными было создано множество алгоритмов сортировки для организации данных.
В этой статье мы рассмотрим наиболее популярные алгоритмы сортировки, разберем, как они работают, и напишем их на Python. Мы также сравним, как быстро они сортируют элементы в списке.
Для простоты реализации алгоритмов сортировать числа будем в порядке их возрастания.
Пузырьковая сортировка (Bubble Sort)
Объяснение
Начнем со сравнения первых двух элементов списка. Если первый элемент больше второго, мы меняем их местами. Если они уже в нужном порядке, мы оставляем их как есть. Затем мы переходим к следующей паре элементов, сравниваем их значения и меняем местами при необходимости. Этот процесс продолжается до последней пары элементов в списке.
Достигнув конца списка, повторяем этот процесс для каждого элемента снова. Хотя это крайне неэффективно. Что если в массиве нужно сделать только одну замену? Почему мы все еще повторяем, даже если список уже отсортирован? Получается нам нужно пройти список n^2 раза.
Очевидно, что для оптимизации алгоритма нам нужно остановить его, когда он закончит сортировку.
Откуда нам знать, что мы закончили сортировку? Если бы элементы были отсортированы, то нам не пришлось бы их менять местами. Таким образом, всякий раз, когда мы меняем элементы, мы устанавливаем флаг в True, чтобы повторить процесс сортировки. Если перестановок не произошло, флаг останется False, и алгоритм остановится.
Реализация
Мы можем реализовать пузырьковую сортировку в Python следующим образом:
Алгоритм работает в цикле while, прерываясь только тогда, когда никакие элементы не меняются местами. Вначале мы установили для swapped значение True, чтобы алгоритм прошел по списку хотя бы один раз.
Сложность
Сложность пузырьковой сортировки в худшем случае (когда список отсортирован в обратном порядке) равна O(n^2).
Сортировка выбором (Selection Sort)
Этот алгоритм сегментирует список на две части: отсортированные и несортированные. Он постоянно удаляет наименьший элемент из несортированного сегмента списка и добавляет его в отсортированный сегмент.
Объяснение
На практике нам не нужно создавать новый список для отсортированных элементов, мы будет обрабатывать крайнюю левую часть списка как отсортированный сегмент. Затем мы ищем во всем списке наименьший элемент и меняем его на первый элемент.
Теперь мы знаем, что первый элемент списка отсортирован, мы получаем наименьший элемент из оставшихся элементов и заменяем его вторым элементом. Это повторяется до тех пор, пока последний элемент списка не станет оставшимся элементом для изучения.
Реализация
Мы видим, что по мере того как i увеличивается, нам нужно проверять все меньше элементов.
Сложность
Сложность сортировки выбором в среднем составляет O(n^2).
Сортировка вставками (Insertion Sort)
Как и Сортировка выбором, этот алгоритм сегментирует список на отсортированные и несортированные части. Он перебирает несортированный сегмент и вставляет просматриваемый элемент в правильную позицию отсортированного списка.
Объяснение
Предполагается, что первый элемент списка отсортирован. Затем мы переходим к следующему элементу, назовем его х. Если x больше первого элемента, мы оставляем его как есть. Если x меньше, мы копируем значение первого элемента во вторую позицию и затем устанавливаем первый элемент в x.
Когда мы переходим к другим элементам несортированного сегмента, мы непрерывно перемещаем более крупные элементы в отсортированном сегменте вверх по списку, пока не встретим элемент меньше x, или не достигнем конца отсортированного сегмента, а затем поместим x в его правильное положение.
Реализация
Сложность
Сложность сортировки вставками в среднем равна O(n^2).
Этот популярный алгоритм сортировки, как сортировки вставками и выбором, сегментирует список на отсортированные и несортированные части. Он преобразует несортированный сегмент списка в структуру данных типа куча (heap), чтобы мы могли эффективно определить самый большой элемент.
Объяснение
Мы начинаем с преобразования списка в Max Heap — бинарное дерево, где самым большим элементом является корневой узел. Затем мы помещаем этот элемент в конец списка. Затем мы восстанавливаем нашу Max Heap, которая теперь имеет на одно меньшее значение, помещая новое наибольшее значение перед последним элементом списка.
Мы повторяем этот процесс построения кучи, пока все узлы не будут удалены.
Реализация
Мы создаем вспомогательную функцию heapify для реализации этого алгоритма:
Сложность
В среднем сложность сортировки кучи составляет O(nlog (n)), что уже значительно быстрее, чем в предыдущих алгоритмах.
Сортировка слиянием (Merge Sort)
Соседние элементы становятся отсортированными парами, затем отсортированные пары объединяются и сортируются с другими парами. Этот процесс продолжается до тех пор, пока мы не получим отсортированный список со всеми элементами несортированного списка.
Объяснение
Мы рекурсивно разделяем список пополам, пока не получим списки с одиночным размером. Затем мы объединяем каждую половину, которая была разделена, и при этом сортируя их.
Сортировка осуществляется путем сравнения наименьших элементов каждой половины. Первый элемент каждого списка сравнивается с первым. Если первая половина начинается с меньшего значения, то мы добавляем ее в отсортированный список. Затем мы сравниваем второе наименьшее значение первой половины с первым наименьшим значением второй половины.
Каждый раз, когда мы выбираем меньшее значение в начале половины, мы перемещаем индекс, элемент которого нужно сравнить на единицу.
Реализация
Обратите внимание, что функция merge_sort(), в отличие от предыдущих алгоритмов сортировки, возвращает новый отсортированный список, а не сортирует существующий список.
Поэтому для сортировки слиянием требуется пространство в памяти для создания нового списка того же размера, что и входной список.
Сложность
В среднем сложность сортировки слиянием составляет O(nlog (n)).
Быстрая сортировка (Quick Sort)
Объяснение
Быстрая сортировка начинается с разбиения списка — выбора одного значения списка, которое будет в его отсортированном месте. Это значение называется опорным. Все элементы, меньшие, чем этот элемент, перемещаются влево. Все более крупные элементы перемещены вправо.
Зная, что опорный элемент находится на своем правильном месте, мы рекурсивно сортируем значения вокруг этого элемента, пока не будет отсортирован весь список.
Реализация
Сложность
В среднем сложность быстрой сортировки составляет O(nlog (n)).
Примечание. Алгоритм быстрой сортировки будет работать медленно, если опорный элемент будет наименьшим или наибольшим элементом списка. Быстрая сортировка обычно работает быстрее с более сбалансированными значениями. В отличие от сортировки кучи и сортировки слиянием, обе из которых имеют худшие времена O(nlog (n)), быстрая сортировка имеет худшее время O(n^2).
Встроенные функции сортировки Python
Хотя полезно знать и понимать эти алгоритмы сортировки, в большинстве проектов Python вы, вероятно, будете использовать встроенную функцию сортировки.
Создадим новый список, чтобы отсортировать его содержимое с помощью метода sort():
Или мы можем использовать функцию sorted() для создания нового отсортированного списка:
Они оба сортируются в порядке возрастания, но вы можете легко отсортировать в порядке убывания, установив для флага реверса в значение True:
В отличие от созданных нами функций алгоритма сортировки, обе эти функции могут сортировать списки кортежей и классов. Функция sorted() может сортировать любой итеративный объект, который включает в себя — списки, строки, кортежи, словари, наборы (set) и пользовательские итераторы.
Встроенная функция сортировки реализуют алгоритм сортировки Тима. Этот алгоритм, основан на сортировке слиянием и сортировке вставкой.
Сравнение скорости
Чтобы понять, как быстро работают рассмотренные алгоритмы, мы сгенерируем список из 5000 чисел от 0 до 1000. Затем мы определим время, необходимое для завершения каждого алгоритма. Повторим это 10 раз, чтобы мы могли более надежно установить производительность сортировки.
Вот какие результаты мы получили, время в секундах:
| Run | Bubble Пузырьковая | Selection Выбором | Insertion Вставкой | Heap Пирамидальная | Merge Слиянием | Quick Быстрая |
|---|---|---|---|---|---|---|
| 1 | 5.531886100769043 | 1.2315289974212646 | 1.6035542488098145 | 0.04006671905517578 | 0.0261991024017334 | 0.016391992568969727 |
| 2 | 4.921762228012085 | 1.2472858428955078 | 1.5910329818725586 | 0.03999590873718262 | 0.025842905044555664 | 0.01661396026611328 |
| 3 | 4.916421890258789 | 1.2244019508361816 | 1.5936298370361328 | 0.044072866439819336 | 0.028622865676879883 | 0.01646280288696289 |
| 4 | 5.154704332351685 | 1.2505383491516113 | 1.6346361637115479 | 0.04128289222717285 | 0.028828144073486328 | 0.01860785484313965 |
| 5 | 4.955228805541992 | 1.2898740768432617 | 1.61759614944458 | 0.04515719413757324 | 0.033148765563964844 | 0.01885080337524414 |
| 6 | 5.049072980880737 | 1.2546651363372803 | 1.625154972076416 | 0.042572975158691406 | 0.02595210075378418 | 0.01628708839416504 |
| 7 | 5.05591893196106 | 1.2491188049316406 | 1.6198101043701172 | 0.040289878845214844 | 0.027335166931152344 | 0.017602920532226562 |
| 8 | 5.087991952896118 | 1.2580881118774414 | 1.6260371208190918 | 0.04264688491821289 | 0.02633810043334961 | 0.017055988311767578 |
| 9 | 5.032891750335693 | 1.2491509914398193 | 1.6144649982452393 | 0.04302191734313965 | 0.032937049865722656 | 0.0176239013671875 |
| 10 | 5.142928838729858 | 1.2202110290527344 | 1.5727391242980957 | 0.03966116905212402 | 0.0257260799407959 | 0.016061067581176758 |
| Avg | 5.084880781173706 | 1.2474863290786744 | 1.6098655700683593 | 0.04187684059143067 | 0.02809302806854248 | 0.017155838012695313 |
Вы можете получить другие значения, если попробуете повторить тест самостоятельно, но общее соотношение должно быть одинаковым или похожим. Пузырьковая сортировка (Bubble Sort) — самая медленная и наихудшая из всех алгоритмов. Хотя она очень полезно в качестве введения в изучения алгоритмов сортировки, оно не подходит для практического использования.
Мы также заметили, что быстрая сортировка выполняется очень быстро, почти в два раза быстрее, чем сортировка слиянием, и для ее работы не требуется много памяти. Напомним, что наш опорный элемент был основан на среднем элементе списка, разные опорные элементы могут дать разные результаты.
Поскольку сортировка вставкой выполняет намного меньше сравнений, чем сортировка выбором, то обычно она выполняются быстрее, но в нашем тесте сортировка выбором выполнилась немного быстрее.
При выборе алгоритма сортировки следует помнить о самих данных и среде запуска алгоритмов, так как это тоже влияет на производительность.
Заключение
Алгоритмы сортировки дают нам много способов упорядочить наши данные. Мы рассмотрели 6 различных алгоритмов — Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort, Quick Sort — и их реализации в Python.
Количество сравнений и перестановок, которые выполняет алгоритм вместе со средой, в которой выполняется код, являются ключевыми определяющими факторами производительности. В реальных приложениях Python рекомендуется придерживаться встроенных функций сортировки Python из-за их гибкости и скорости.
Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.
Пример работы алгоритма
(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами. (1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как (1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как (1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (), алгоритм не меняет их местами.
(1 4 2 5 8) (1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)
Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.
(1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)
Теперь массив отсортирован и алгоритм может быть завершён.
Реализация алгоритма на различных языках программирования:
Синтаксис Intel
Синтаксис AT&T (GNU)
С использованием Template
Без использования Template
Delphi
Сортировка одномерного динамического целочисленного массива:
Fortran
Pascal
Усовершенствованный алгоритм сортировки пузырьком:
Python
JavaScript
JavaFX
Nemerle
TurboBasic 1.1
CLS RANDOMIZE TIMER DEFINT X, Y, N, I, J, D N = 10 ' 32 766 - 62.7 SEC DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] 'FRE(-1)=21440-21456 PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI" FOR X = 1 TO N Y[X] = X PRINT Y[X]; NEXT X:PRINT PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA" PRINT " SLUCHAINYE CHISLA" FOR X = 1 TO N YD=Y[X] XS=INT(RND*N)+1 PRINT XS; Y[X]=Y[XS] Y[XS]=YD NEXT X:PRINT PRINT " PEREMESHANNYJ MASSIV" FOR X=1 TO N PRINT Y[X]; NEXT X:PRINT 'ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2) MTIMER FOR J=1 TO N-1 STEP 1 F=0 FOR I=1 TO N-J STEP 1 'IF Y[I] > Y[I+1] THEN D=Y[I]:Y[I]=Y[I+1]:Y[I+1]=D:F=1 IF Y[I] > Y[I+1] THEN SWAP Y[I],Y[I+1]:F=1 LOCATE 8,1 REM PRINT " ANYMACIJA SORTIROVKI" REM FOR X1=1 TO N REM ANIMATION BLOCK PRINT Y[X1]; REM NEXT X1:PRINT REM DELAY .5 REM NEXT I IF F=0 THEN EXIT FOR NEXT J T1=MTIMER PRINT " OTSORTIROVANNYJ MASSIV" FOR X=1 TO N PRINT Y[X]; NEXT X:PRINT PRINT "ELAPSED TIME font-family: comic sans ms,sans-serif; font-size: 14pt;">Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность. В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).
Читайте также: