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

Содержание:

Anonim

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

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

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

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

  • Что такое пузырьковая сортировка?
  • Реализация алгоритма пузырьковой сортировки
  • Оптимизированный алгоритм пузырьковой сортировки
  • Визуальное представление
  • Примеры Python
  • Код Пояснение
  • Преимущества пузырьковой сортировки
  • Недостатки пузырьковой сортировки
  • Анализ сложности пузырьковой сортировки

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

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

Проблема

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

Рассмотрим следующий список:

[21,6,9,33,3]

Решение

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

Результат должен быть таким:

[3,6,9,21,33]

Алгоритм

Алгоритм пузырьковой сортировки работает следующим образом

Шаг 1) Получите общее количество элементов. Получить общее количество элементов в данном списке

Шаг 2) Определите количество выполняемых внешних проходов (n - 1). Его длина - список минус один

Шаг 3) Выполните внутренние проходы (n - 1) раз для внешнего прохода 1. Получите значение первого элемента и сравните его со вторым значением. Если второе значение меньше первого значения, то поменяйте местами позиции

Шаг 4) Повторяйте шаг 3 проходов, пока не дойдете до внешнего прохода (n - 1). Получите следующий элемент в списке, затем повторите процесс, который был выполнен на шаге 3, пока все значения не будут расположены в правильном порядке возрастания.

Шаг 5) Верните результат, когда все проходы будут выполнены. Вернуть результаты отсортированного списка

Шаг 6) Оптимизируйте алгоритм

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

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

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

Оптимизация пузырьковой сортировки помогает нам избежать ненужных итераций и сэкономить время и ресурсы.

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

Оптимизация выполняется с помощью следующих шагов

Шаг 1) Создайте переменную флага, которая отслеживает, произошла ли какая-либо подкачка во внутреннем цикле.

Шаг 2) Если значения поменялись местами, переходите к следующей итерации.

Шаг 3) Если преимущества не поменялись местами, завершите внутренний цикл и продолжите внешний цикл.

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

Визуальное представление

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

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

Первая итерация

Шаг 1)

Значения 21 и 6 сравниваются, чтобы проверить, какое из них больше другого.

21 больше 6, поэтому 21 занимает позицию, занимаемую 6, а 6 занимает позицию, которую занимали 21

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

Шаг 2)

Значения 21 и 9 сравниваются.

21 больше 9, поэтому мы меняем местами 21 и 9

Новый список теперь такой, как указано выше

Шаг 3)

Значения 21 и 33 сравниваются, чтобы найти большее.

Значение 33 больше 21, поэтому замена не выполняется.

Шаг 4)

Значения 33 и 3 сравниваются, чтобы найти большее.

Значение 33 больше 3, поэтому мы меняем их позиции.

Сортированный список в конце первой итерации аналогичен приведенному выше.

Вторая итерация

Новый список после второй итерации выглядит следующим образом

Третья итерация

Новый список после третьей итерации выглядит следующим образом

Четвертая итерация

Новый список после четвертой итерации выглядит следующим образом

Примеры Python

В следующем коде показано, как реализовать алгоритм пузырьковой сортировки в Python.

def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)

Выполнение указанной выше программы пузырьковой сортировки в Python дает следующие результаты

[6, 9, 21, 3, 33]

Код Пояснение

Объяснение программного кода Python Bubble Sort следующее

ЗДЕСЬ,

  1. Определяет функцию bubbleSort, которая принимает параметр theSeq. Код ничего не выводит.
  2. Получает длину массива и присваивает значение переменной n. Код ничего не выводит
  3. Запускает цикл for, который выполняет алгоритм пузырьковой сортировки (n - 1) раз. Это внешний цикл. Код ничего не выводит
  4. Определяет переменную флага, которая будет использоваться для определения того, произошла ли подкачка или нет. Это сделано для оптимизации. Код ничего не выводит
  5. Запускает внутренний цикл, сравнивающий все значения в списке от первого до последнего. Код ничего не выводит.
  6. Использует оператор if, чтобы проверить, больше ли значение в левой части, чем значение в правой части. Код ничего не выводит.
  7. Присваивает значение theSeq [j] временной переменной tmp, если условие истинно. Код ничего не выводит
  8. Значение Seq [j + 1] присваивается позиции Seq [j]. Код ничего не выводит
  9. Значение переменной tmp присваивается позиции theSeq [j + 1]. Код ничего не выводит
  10. Переменной flag присваивается значение 1, чтобы указать, что произошел обмен. Код ничего не выводит
  11. Использует оператор if, чтобы проверить, равно ли значение переменной flag 0. Код ничего не выводит.
  12. Если значение равно 0, мы вызываем оператор break, который выходит из внутреннего цикла.
  13. Возвращает значение Seq после сортировки. Код выводит отсортированный список.
  14. Определяет переменную el, содержащую список случайных чисел. Код ничего не выводит.
  15. Присваивает значение функции bubbleSort переменному результату.
  16. Печатает значение переменной result.

Преимущества пузырьковой сортировки

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

  • Это легко понять
  • Очень хорошо работает, когда список уже или почти отсортирован.
  • Не требует большой памяти.
  • Код алгоритма легко написать
  • Требования к пространству минимальны по сравнению с другими алгоритмами сортировки.

Недостатки пузырьковой сортировки

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

  • Он не работает при сортировке больших списков. На это уходит слишком много времени и ресурсов.
  • Он в основном используется в академических целях, а не в реальных приложениях.
  • Количество шагов, необходимых для сортировки списка, имеет порядок n 2.

Анализ сложности пузырьковой сортировки

Есть три типа сложности:

1) Сложность сортировки

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

2) Временная сложность

Временная сложность пузырьковой сортировки O (n 2 )

Временные сложности можно разделить на следующие категории:

  • В худшем случае - это список в порядке убывания. Алгоритм выполняет максимальное количество выполнений, которое выражается как [Big-O] O (n 2 ).
  • В лучшем случае - это происходит, когда предоставленный список уже отсортирован. Алгоритм выполняет минимальное количество выполнений, которое выражается как [Big-Omega] Ω (n).
  • Средний случай - это происходит, когда список находится в случайном порядке. Средняя сложность представлена ​​как [Big-theta] ⊝ (n 2 )

3) Космическая сложность

Сложность пространства измеряет количество дополнительного места, которое необходимо для сортировки списка. Для пузырьковой сортировки требуется только одно (1) дополнительное пространство для временной переменной, используемой для обмена значениями. Следовательно, его пространственная сложность O (1).

Резюме

  • Алгоритм пузырьковой сортировки работает, сравнивая два соседних значения и меняя их местами, если значение слева меньше значения справа.
  • Реализация алгоритма пузырьковой сортировки в Python относительно проста. Все, что вам нужно использовать, - это циклы for и операторы if.
  • Проблема, которую решает алгоритм пузырьковой сортировки, состоит в том, чтобы взять случайный список элементов и превратить его в упорядоченный список.
  • Алгоритм пузырьковой сортировки в структуре данных лучше всего работает, когда список уже отсортирован, поскольку он выполняет минимальное количество итераций.
  • Алгоритм пузырьковой сортировки не работает, когда список находится в обратном порядке.
  • Сортировка с помощью барботера имеет временную сложность O (n 2 ) и пространственную сложность O (1).
  • Алгоритм барботажной сортировки лучше всего подходит для академических целей, а не для реальных приложений.
  • Оптимизированная пузырьковая сортировка делает алгоритм более эффективным, пропуская ненужные итерации при проверке значений, которые уже были отсортированы.