Пример сортировки пузырьком python

Пузырьковая сортировка в Python

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

Концепция пузырьковой сортировки

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

Мы создаем список элементов, в котором хранятся целые числа

Так алгоритм сортирует элементы:

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

Он сравнивает первые два элемента, и здесь 5> 3, а затем меняет их местами. Теперь у нас есть новый список –

В третьем сравнении 8> 6, элементы меняются местами –

В четвертом сравнении 8> 7, элементы меняются местами –

В пятом сравнении 8> 2, также нужно их поменять местами –

На этом первая итерация завершена, и в конце мы получаем самый большой элемент. Теперь нам нужно len (list1) – 1

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

[3, 5, 6, 7, 2, 8] -> [3, 5, 6, 2, 7, 8] здесь 7> 2, происходит их перемена местами. Теперь

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

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

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

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

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

Реализация в коде Python

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

# Creating a bubble sort function def bubble_sort(list1): # Outer loop for traverse the entire list for i in range(0,len(list1)-1): for j in range(len(list1)-1): if(list1[j]>list1[j+1]): temp = list1[j] list1[j] = list1[j+1] list1[j+1] = temp return list1 list1 = [5, 3, 8, 6, 7, 2] print("The unsorted list is: ", list1) # Calling the bubble sort function print("The sorted list is: ", bubble_sort(list1))

The unsorted list is: [5, 3, 8, 6, 7, 2] The sorted list is: [2, 3, 5, 6, 7, 8]

В приведенном выше коде мы определили функцию bubble_sort(), которая принимает list1 в качестве аргумента.

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

Без использования временной переменной

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

def bubble_sort(list1): # Outer loop for traverse the entire list for i in range(0,len(list1)-1): for j in range(len(list1)-1): if(list1[j]>list1[j+1]): # here we are not using temp variable list1[j],list1[j+1] = list1[j+1], list1[j] return list1 list1 = [5, 3, 8, 6, 7, 2] print("The unsorted list is: ", list1) # Calling the bubble sort function print("The sorted list is: ", bubble_sort(list1))

The unsorted list is: [5, 3, 8, 6, 7, 2] The sorted list is: [2, 3, 5, 6, 7, 8]

Оптимизация реализации кода Python

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

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

def bubble_sort(list1): # We can stop the iteration once the swap has done has_swapped = True while(has_swapped): has_swapped = False for i in range(len(list1) - 1): if list1[i] > list1[i+1]: # Swap list1[i], list1[i+1] = list1[i+1], list1[i] has_swapped = True return list1 list1 = [5, 3, 8, 6, 7, 2] print("The unsorted list is: ", list1) # Calling the bubble sort function print("The sorted list is: ", bubble_sort(list1))

The unsorted list is: [5, 3, 8, 6, 7, 2] The sorted list is: [2, 3, 5, 6, 7, 8]

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

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

На каждой последующей итерации мы можем сравнивать на один элемент меньше, чем раньше. Точнее, на k-й итерации нужно сравнить только первые n – k + 1 элементов:

def bubble_sort(list1): has_swapped = True total_iteration = 0 while(has_swapped): has_swapped = False for i in range(len(list1) - total_iteration - 1): if list1[i] > list1[i+1]: # Swap list1[i], list1[i+1] = list1[i+1], list1[i] has_swapped = True total_iteration += 1 print("The number of iteraton: ",total_iteration) return list1 list1 = [5, 3, 8, 6, 7, 2] print("The unsorted list is: ", list1) # Calling the bubble sort funtion print("The sorted list is: ", bubble_sort(list1))

The unsorted list is: [5, 3, 8, 6, 7, 2] The number of iteraton: 6 The sorted list is: [2, 3, 5, 6, 7, 8]

Сравнение времени

Давайте посмотрим на сравнение времени между приведенными выше фрагментами кода.

Unoptimized Bubble Sort Takes: 0.0106407 Optimize Bubble Sort Takes: 0.0078251 Bubble Sort with a Boolean flag and shortened list Takes: 0.0075207

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

Источник

Сортировка пузырьком

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

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

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

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

Пусть имеется список из пяти элементов [6, 12, 4, 3, 8].

За первую итерацию внешнего цикла число 12 переместится в конец. Для этого потребуется 4 сравнения во внутреннем цикле:

• 6 > 12? Нет
• 12 > 4? Да. Меняем местами
• 12 > 3? Да. Меняем местами
• 12 > 8? Да. Меняем местами

За вторую итерацию внешнего цикла число 8 переместиться на предпоследнее место. Для этого потребуется 3 сравнения:

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

На четвертой итерации внешнего цикла осталось сравнить только первые два элемента, поэтому количество итераций внутреннего равно единице:

Реализация сортировки пузырьком на языке программирования Python с помощью циклов for

from random import randint N = 10 a = [] for i in range(N): a.append(randint(1, 99)) print(a) for i in range(N-1): for j in range(N-i-1): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] print(a)

[63, 80, 62, 69, 71, 37, 12, 90, 19, 67] [12, 19, 37, 62, 63, 67, 69, 71, 80, 90]

С помощью циклов while :

from random import randint N = 10 a = [] for i in range(N): a.append(randint(1, 99)) print(a) i = 0 while i  N - 1: j = 0 while j  N - 1 - i: if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] j += 1 i += 1 print(a)

Функция сортировки пузырьком на Python:

from random import randint def bubble(array): for i in range(N-1): for j in range(N-i-1): if array[j] > array[j+1]: buff = array[j] array[j] = array[j+1] array[j+1] = buff N = 10 a = [] for i in range(N): a.append(randint(1, 99)) print(a) bubble(a) print(a)

Источник