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

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

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

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

В этой пузырьковой сортировке Учебник по Python ты выучишь:

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

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

Проблема

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

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

[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 compares все элементы в списке независимо от того, отсортирован ли он уже или нет. Если данный список уже отсортирован, сравнение всех значений — пустая трата времени и ресурсов.

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

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

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

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

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

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

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

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

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

Фоллоwing на изображении показан несортированный список

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

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

Шаг 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

Фоллоwing код показывает, как реализовать алгоритм пузырьковой сортировки в Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

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

[6, 9, 21, 3, 33]

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

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

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

ВОТ,

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

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

Фоллоwing некоторые преимущества алгоритма пузырьковой сортировки

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

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

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

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

сplexИтичный анализ пузырьковой сортировки

Существует три типа Complexэто:

1) Сортировать комplexность

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

2) Время комplexность

время комplexСтепень пузырьковой сортировки O(n2)

время комplexпредприятия можно разделить на:

  • Худший случай – здесь представленный список расположен в порядке убывания. Алгоритм выполняет максимальное количество выполнений, которое выражается как [Big-O] O(n2)
  • Лучший случай – это происходит, когда предоставленный список уже отсортирован. Алгоритм выполняет минимальное количество выполнений, которое выражается как [Big-Omega] Ом(п)
  • Средний случай – это происходит, когда список находится в случайном порядке. Средний комplexity представляется как [Big-theta] ⊝(n2)

3) Космическая связьplexность

Космическая связьplexity измеряет объем дополнительного пространства, необходимого для сортировки списка. Пузырьковая сортировка требует только одно (1) дополнительное пространство для временной переменной, используемой для замены значений. Поэтому у него есть космическая связь.plexность О (1).

Итоги

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