Пузырьковая сортировка (сортировка “пузырьком”)

Методы списков

Давайте теперь
предположим, что у нас имеется список из чисел:

a = 1, -54, 3, 23, 43, -45, 

и мы хотим в
конец этого списка добавить значение. Это можно сделать с помощью метода:

a.append(100)

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

a = a.append(100)

категорически не
следует, так мы только потеряем весь наш список! И этим методы списков
отличаются от методов строк, когда мы записывали:

string="Hello"
string = string.upper()

Здесь метод upper возвращает
измененную строку, поэтому все работает как и ожидается. А метод append ничего не
возвращает, и присваивать значение None переменной a не имеет
смысла, тем более, что все работает и так:

a = 1, -54, 3, 23, 43, -45, 
a.append(100)

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

a.append("hello")

тогда в конец
списка будет добавлен этот элемент. Или, булевое  значение:

a.append(True)

Или еще один
список:

a.append(1,2,3)

И так далее. Главное,
чтобы было указано одно конкретное значение. Вот так работать не будет:

a.append(1,2)

Если нам нужно
вставить элемент в произвольную позицию, то используется метод

a.insert(3, -1000)

Здесь мы
указываем индекс вставляемого элемента и далее значение самого элемента.

Следующий метод remove удаляет элемент
по значению:

a.remove(True)
a.remove('hello')

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

a.remove('hello2')

то возникает
ошибка. Еще один метод для удаления

a.pop()

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

end = a.pop()

Также в этом
методе можно указывать индекс удаляемого элемента, например:

a.pop(3)

Если нам нужно
очистить весь список – удалить все элементы, то можно воспользоваться методом:

a.clear()

Получим пустой
список. Следующий метод

a = 1, -54, 3, 23, 43, -45, 
c = a.copy()

возвращает копию
списка. Это эквивалентно конструкции:

c = list(a)

В этом можно
убедиться так:

c1 = 1

и список c будет отличаться
от списка a.

Следующий метод count позволяет найти
число элементов с указанным значением:

c.count(1)
c.count(-45)

Если же нам
нужен индекс определенного значения, то для этого используется метод index:

c.index(-45)
c.index(1)

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

c.index(1, 1)

Здесь поиск
будет начинаться с индекса 1, то есть, со второго элемента. Или, так:

c.index(23, 1, 5)

Ищем число 23 с
1-го индекса и по 5-й не включая его. Если элемент не находится

c.index(23, 1, 3)

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

23 in c1:3

и при значении True далее уже
определять индекс этого элемента.

Следующий метод

c.reverse()

меняет порядок
следования элементов на обратный.

Последний метод,
который мы рассмотрим, это

c.sort()

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

c.sort(reverse=True)

Причем, этот
метод работает и со строками:

lst = "Москва", "Санкт-Петербург", "Тверь", "Казань"
lst.sort()

Здесь
используется лексикографическое сравнение, о котором мы говорили, когда
рассматривали строки.

Это все основные
методы списков и чтобы вам было проще ориентироваться, приведу следующую
таблицу:

Реализация

Сортировка массивов

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

При этом мы будем использовать две функции — partition() и quick_sort().

Давайте начнем с функции partition():

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array <= array:
            pivot += 1
            array, array = array, array
    array, array = array, array
    return pivot

И, наконец, давайте реализуем функцию quick_sort():

def quick_sort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

После того, как обе функции реализованы, мы можем запустить quick_sort():

array = 

quick_sort(array)
print(array)

Результат:

Поскольку алгоритм unstable (нестабилен), нет никакой гарантии, что два 19 будут всегда в этом порядке друг за другом. Хотя это ничего не значит для массива целых чисел.

Оптимизация быстрой сортировки

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

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

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

Сложность алгоритма

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

Точное время выполнения алгоритма не рассматривается, потому что оно зависит слишком от многих факторов: мощность процессора, тип данных массива, используемый язык программирования.

Алгоритм сортировки пузырьком имеет сложность , где – количество элементов массива. Из формулы видно, что сложность сортировки пузырьком квадратично зависит от количества сортируемых элементов. Это значит, что он неэффективен при работе с большими массивами данных.

Следует понимать, что с помощью асимптотической функции нельзя точно вычислить время работы алгоритма. Например, дана последовательность «6 5 4 3 2 1», для её сортировки придется сделать максимальное количество проходов. Такой случай называют наихудшим. Если дана последовательность «3 1 2 4 5», то количество проходов будет минимально, соответственно сортировка пройдет гораздо быстрее. Если же дан уже отсортированный массив, то алгоритму сортировки и вовсе не нужно совершать проходов. Это называется наилучшим случаем.

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

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

На самом деле, программисты просто гуглят необходимую реализацию. Конечно, они имеют представление о принципах их работы, потому что в своё время рассмотрели несколько алгоритмов, как, например, сортировка пузырьком.

Кроме того, в Python и других языках программирования существуют встроенные функции, которые производят сортировку быстро и эффективно.

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

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

Выполняет сортировку последовательности по возростанию/убыванию.

Параметры:

• — объект, поддерживающий итерирование
• — пользовательская функция, которая применяется к каждому элементу последовательности
• — порядок сортировки

Описание:

Функция вернет новый отсортированный t-list] из итерируемых элементов. Функция имеет два необязательных аргумента, которые должны быть указаны в качестве аргументов ключевых слов.

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

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

Используйте для преобразования функции, использующей cmp (старый стиль) в использующую key (новый стиль).

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

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

Сортировка слов в предложении без учета регистра:

line = 'This is a test string from Andrew'
x = sorted(line.split(), key=str.lower)
print(x)
# 

Сортировка сложных объектов с использованием индексов в качестве ключей :

student = 
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
    

# Сортируем по возрасту student
x = sorted(student, key=lambda student student2])
print(x)
# 

Тот же метод работает для объектов с именованными атрибутами.

class Student
    def __init__(self, name, grade, age):
        self.name = name
        self.grade = grade
        self.age = age
    def __repr__(self):
        return repr((self.name, self.grade, self.age))

student = 
    Student('john', 'A', 15),
    Student('jane', 'B', 12),
    Student('dave', 'B', 10),
    

x = sorted(student, key=lambda student student.age)
print(x)
# 

Сортировка по убыванию:

student = 
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
    

# Сортируем по убыванию возраста student
x = sorted(student, key=lambda i i2], reverse=True)
print(x)
# 

Стабильность сортировки и сложные сортировки:

data = 
x = sorted(data, key=lambda data data])
print(x)
# 

Обратите внимание, как две записи (‘blue’, 1), (‘blue’, 2) для синего цвета сохраняют свой первоначальный порядок. Это замечательное свойство позволяет создавать сложные сортировки за несколько проходов по нескольким ключам

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

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

student = 
    ('john', 15, 4.1),
    ('jane', 12, 4.9),
    ('dave', 10, 3.9),
    ('kate', 11, 4.1),
    

# По средней оценке
x = sorted(student, key=lambda num num2])
# По убыванию возраста
y = sorted(x, key=lambda age age1], reverse=True)
print(y)
# 

А еще, для сортировок по нескольким ключам, удобнее использовать модуль . Функции модуля допускают несколько уровней сортировки. Например, как в предыдущем примере успеваемость будет первым ключом, возраст вторым.Только сортировать будем все по возрастанию:

from operator import itemgetter

x = sorted(student, key=itemgetter(2,1))
print(x)
# 

Как работает Быстрая сортировка

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

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

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

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

Теперь, когда мы выбрали опорный элемент — что нам с ним делать? Опять же, есть несколько способов сделать само разбиение. У нас будет «указатель» на нашу опору, указатель на «меньшие» элементы и указатель на «более крупные» элементы.

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

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

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)

Выберем первый элемент как опору 29), а указатель на меньшие элементы (называемый «low») будет следующим элементом, указатель на более крупные элементы (называемый «high») станем последний элемент в списке.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

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

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

• Теперь, когда наш элемент high указывает на элемент 21, то есть на значение меньше чем опорное значение, мы хотим найти значение в начале массива, с которым мы можем поменять его местами. Нет смысла менять местами значение, которое меньше, чем опорное значение, поэтому, если low указывает на меньший элемент, мы пытаемся найти тот, который будет больше.
• Мы перемещаем переменную low вправо, пока не найдем элемент больше, чем опорное значение. К счастью, low уже имеет значение 89.
• Мы меняем местами low и high:

29 | 21 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (high),44

• Сразу после этого мы перемещает high влево и low вправо (поскольку 21 и 89 теперь на своих местах)
• Опять же, мы двигаемся high влево, пока не достигнем значения, меньшего, чем опорное значение, и мы сразу находим — 12
• Теперь мы ищем значение больше, чем опорное значение, двигая low вправо, и находим такое значение 41

Этот процесс продолжается до тех пор, пока указатели low и high наконец не встретятся в одном элементе:

29 | 21,27,12,19,28 (low/high),44,78,87,66,31,76,58,88,83,97,41,99,44

Мы больше не используем это опорное значение, поэтому остается только поменять опорную точку и high, и мы закончили с этим рекурсивным шагом:

28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44

Как видите, мы достигли того, что все значения, меньшие 29, теперь слева от 29, а все значения больше 29 справа.

Затем алгоритм делает то же самое для коллекции 28,21,27,12,19 (левая сторона) и 44,78,87,66,31,76,58,88,83,97,41,99,44 (правая сторона). И так далее.

Оптимизация[править]

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

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

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

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

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

Алгоритм

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N−1{\displaystyle N-1} раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде. Отсюда и название алгоритма).

Сортировка слиянием (Merge sort)

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

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

Description

We can imagine that sorted numbers are bubbles, the ones with lower value are lighter than the ones with higher value, hence they ascend to the surface faster.

Bubble sort advances similarly. In every step it compares two adjacent elements and if the lower value is on the left side of the higher, bubble sort swaps them (lighter value ascends to the end of the array) and with the same logic algorithm proceeds to the next item.

After one iteration the lowest value is located at the end of the array. Algorithm now repeats the procedure with reduced array (the last element is already sorted). After iterations is the array completely sorted, because the last bubble is sorted trivially.

How Bubble Sort Works?

We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we’re keeping it short and precise.

Bubble sort starts with very first two elements, comparing them to check which one is greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with 27.

We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this −

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After one iteration, the array should look like this −

To be precise, we are now showing how an array should look like after each iteration. After the second iteration, it should look like this −

Notice that after each iteration, at least one value moves at the end.

And when there’s no swap required, bubble sorts learns that an array is completely sorted.

Now we should look into some practical aspects of bubble sort.

Pseudocode

We observe in algorithm that Bubble Sort compares each pair of array element unless the whole array is completely sorted in an ascending order. This may cause a few complexity issues like what if the array needs no more swapping as all the elements are already ascending.

To ease-out the issue, we use one flag variable swapped which will help us see if any swap has happened or not. If no swap has occurred, i.e. the array requires no more processing to be sorted, it will come out of the loop.

Pseudocode of BubbleSort algorithm can be written as follows −

procedure bubbleSort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
		
      for j = 0 to loop-1 do:
      
         /* compare the adjacent elements */   
         if list > list then
            /* swap them */
            swap( list, list )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
      
   end for
   
end procedure return list

Скорость сортировки в Python

Python

# speed/main.py

import random

from boxx import timeit

def list_sort(arr):
return arr.sort()

def sorted_builtin(arr):
return sorted(arr)

def main():
arr =

with timeit(name=»sorted(list)»):
sorted_builtin(arr)

with timeit(name=»list.sort()»):
list_sort(arr)

if __name__ == «__main__»:
main()

Указанный выше код выводит следующий результат:

Shell

$ python main.py
«sorted(list)» spend time: 0.1104379
«list.sort()» spend time: 0.0956471

Как видите, метод немного быстрее, чем функция . Почему так получается? Разберем обе функции и посмотрим, сможет ли байтовый код дать ответ:

Python

>>> import dis
>>> dis.dis(list_sort)
12 0 LOAD_FAST 0 (arr)
2 LOAD_METHOD 0 (sort)
4 CALL_METHOD 0
6 RETURN_VALUE
>>> dis.dis(sorted_builtin)
16 0 LOAD_GLOBAL 0 (sorted)
2 LOAD_FAST 0 (arr)
4 CALL_FUNCTION 1
6 RETURN_VALUE

Байтовый код обеих функций практически идентичен. Единственное различие в том, что функция сначала загружает список, и за методом (sort) следует вызванный метод списка без аргументов. Если сравнить, функция сначала загружает встроенную функцию , а за ней следует список и вызов загруженной функции со списком в качестве аргумента.

Почему же временные результаты отличаются?

Можно предположить, что в то время как может работать с известным размером и менять элементы внутри данного размера, должен работать c неизвестным размером. Следовательно, если при добавлении нового элемента не хватает памяти, нужно изменить размер нового списка, созданного через . На это требуется время! Если просмотреть исходный код CPython, можно найти следующий комментарий об изменении размера списка объектов:

Помните, что сейчас мы работаем со списком из 1 000 000 элементов — изменений размера будет довольно много! К несчастью, пока что это лучший ответ на вопрос, почему на 13% быстрее, чем .

Python

new_array = arr.copy()
arr.sort()

Имплементация приводит к разнице во времени выполнения, поскольку создание копии списка занимает некоторое время.

Таблица 1: Сортировка пузырьком в однопоточном режиме

Поиск в массиве

• Используем цикл while:

1
2
3
4
5
6
7
8
9
10
11
12

import random # подключение библиотеки
from random import randint 
n=10; x=5
mas = randint(1,10) for i in range(n) # инициализируем массив
 
i = 
while i < n and masi != x: # если элемент не равен
      i += 1
if i < n:
      print ( "mas=", x, sep = "" )
else:
      print ( "Не нашли!" )

Используем цикл for:

1
2
3
4
5
6
7
8
9
10
11
12
13

import random
from random import randint 
n=10;x=5
mas = randint(1,10) for i in range(n)
 
for i in range (n):
     if masi == x:
             nomer = i
             break
if nomer >= :
     print ( "mas=", x, sep = "" )
else:
     print ( "Не нашли!" )

В данном случае в переменной nomer сохраняется номер элемента массива с найденным значением.

Поэтому рассмотрим второй способ поиска, более простой:

1
2
3
4
5
6
7
8
9
10
11
12
13

import random
from random import randint 
n=10;x=5
mas = randint(1,10) for i in range(n)
 
nomer = -1
for i in range (n):
     if masi == x:
             print ( "mas=", x, sep = "" )
             break
 
else:
     print ( "Не нашли!" )

Задание Python 7_1:
Дан массив. Необходимо подтвердить, что в массиве есть числа, кратные трем.

Задание Python 7_2:
Заполните массив случайными числами в диапазоне 0..4 и выведите на экран номера всех элементов, равных значению X (оно вводится с клавиатуры).

Working of Bubble Sort

Suppose we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)

1. Starting from the first index, compare the first and the second elements.
2. If the first element is greater than the second element, they are swapped.
3. Now, compare the second and the third elements. Swap them if they are not in order.
4. The above process goes on until the last element.
   Compare the Adjacent Elements

2. Remaining Iteration

The same process goes on for the remaining iterations.

After each iteration, the largest element among the unsorted elements is placed at the end.

Put the largest element at the end

In each iteration, the comparison takes place up to the last unsorted element.

Compare the adjacent elements

The array is sorted when all the unsorted elements are placed at their correct positions.

The array is sorted if all elements are kept in the right order

Code

     function bubbleSort(array a)
         for i in 1 -> a.length - 1 do
             for j in 1 -> a.length - i - 1 do 
                 if a < a 
                     swap(a, a);  
             

     /**
      * Bubble sort (descending order)
      * @param array array to besorted
      */
     public static void bubbleSort(int[] array){
         for (int i = 0; i < array.length - 1; i++) {
             for (int j = 0; j < array.length - i - 1; j++) {
                 if(array < array){
                     int tmp = array;
                     array = array;
                     array = tmp;
                 }
             }
         }
     }   
             

 /**
  * Bubble sort (ascending order)
  * @param array array to be sorted
  * @param size size of the array
  */
 void bubbleSort(int * array, int size){
     for(int i = 0; i 
         

         /**
          * Bubble sort (ascending order)
          * @param arr array to be sorted
          * @author Thomas (www.adamjak.net)
          */
         static void BubbleSort(int[] arr)
         {
             for (int i = 0; i 
         

 /**
  * Bubble sort (descending order)
  * @param array array to be sorted
  * @auhor Pavel Micka
  */
 function bubbleSort(array){
     for (var i = 0; i 
         

   procedure BubbleSort(var X : ArrayType; N : integer);
   var
     I,
     J : integer;
   begin
     for I := 2 to N do
       begin
         for J := N downto I do
           if (X > X) then
             Swap(X, X);
       end
   end;
 
   procedure Swap(var X, Y : integer);
   var
     Temp : integer;
   begin
     Temp := X;
     X := Y;
     Y := Temp
   end;
             

 /**
  * Bubble sort (ascending order)
  * @param arr array to be sorted
  * @auhor Thomas (www.adamjak.net)
  */ 
 function bubble_sort(&$arr) {
 
     $count = count($arr);
 
     for($i = 0; $i 
         

Bubble Sort Complexity

Complexity in Detail

Bubble Sort compares the adjacent elements.

Hence, the number of comparisons is

nearly equals to

Hence, Complexity: O(n2)

Also, if we observe the code, bubble sort requires two loops. Hence, the complexity is

1. Time Complexities

• Worst Case Complexity:
  If we want to sort in ascending order and the array is in descending order then the worst case occurs.
• Best Case Complexity:
  If the array is already sorted, then there is no need for sorting.
• Average Case Complexity:
  It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

2. Space Complexity

• Space complexity is because an extra variable is used for swapping.
• In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be .

Пример работы алгоритма

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Наглядная демонстрация алгоритма.

Первый проход:

(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5>4{\displaystyle 5>4}

(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5>2{\displaystyle 5>2}

(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (8>5{\displaystyle 8>5}), алгоритм не меняет их местами.

Второй проход:

(1 4 2 5 8) (1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4>2{\displaystyle 4>2}

(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)

Теперь массив отсортирован и алгоритм может быть завершён.

Заключение

В этом уроке мы изучали, что такое сортировка и где он используется, то мы узнали, как Bubble Sort работает, мы придумали алгоритм и реализовали пузырь в Python.

Bubble Sort – один из многих сортировковных алгоритмов, и он далеко от лучшего, но это очень легко реализовать. Причина, по которой она не используется слишком часто, так это то, что у него сложность O (n 2 ), что означает, что количество элементов в списке удвоилось, время, необходимое для сортировки их использования этого алгоритма, увеличится в четыре раза.

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