Алгоритм сортировки пузырьком 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

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

Источник

5 Простых Методов Сортировки С Использованием Python

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

“Методы сортировки С Использованием href=”https://www.python.org/”>Python”- Алгоритм сортировки используется для перестановки заданного массива или списка элементов в соответствии с оператором сравнения элементов. Оператор сравнения определяет новый порядок элементов в соответствующей структуре данных. href=”https://www.python.org/”>Python”- Алгоритм сортировки используется для перестановки заданного массива или списка элементов в соответствии с оператором сравнения элементов. Оператор сравнения определяет новый порядок элементов в соответствующей структуре данных.

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

Методы сортировки и сложность

Некоторые из методов сортировки:

1 – Методы Сортировки Выбора С Использованием Python

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

1) Подмассив, который уже отсортирован. 2) Оставшийся подмассив, который не отсортирован.

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

Блок-схема

Блок-схема сортировки выбора

Код/Реализация Python:

def insertion_sort(nums): for i in range(1, len(nums)): [i] - 1 while j and nums[j] > item_to_insert: nums[j +[j] j nums[j + # Verify if it works random_list_of_nums = [9, 1, 15, 28, 6] insertion_sort(random_list_of_nums) print(random_list_of_nums)

2 – Сортировка Пузырьков

Алгоритм сортировки пузырьков перебирает список, сравнивая элементы попарно и меняя их местами до тех пор, пока более крупные элементы не “всплывут” в конец списка, а более мелкие элементы не останутся “внизу”.

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

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

Откуда нам знать, что мы закончили сортировку? Если бы предметы были в порядке, то нам не пришлось бы менять их местами. Поэтому всякий раз, когда мы меняем значения местами, мы устанавливаем флаг True, чтобы повторить процесс сортировки. Если свопы не происходят, флаг остается False и алгоритм останавливается.

Код/Реализация Python:

def bubble_sort(nums): while swapped: for i in range(len(nums) - 1): if nums[i] > nums[i + 1]: nums[i], nums[i +[i + 1], nums[i] # Verify if it works random_list_of_nums = [5, 2, 1, 8, 4] bubble_sort(random_list_of_nums) print(random_list_of_nums)

3 – Методы Сортировки Вставки С Использованием Python

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

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

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

Код/Реализация Python:

def insertion_sort(nums): for i in range(1, len(nums)): [i] - 1 while j and nums[j] > item_to_insert: nums[j +[j] j nums[j + # Verify if it works random_list_of_nums = [9, 1, 15, 28, 6] insertion_sort(random_list_of_nums) print(random_list_of_nums)

4 – Быстрая сортировка

Быстрая сортировка начинается с разбиения списка – выбора одного значения списка, которое будет находиться в отсортированном месте. Это значение называется pivot. Все элементы, меньшие, чем ось, перемещаются влево. Все более крупные элементы перемещаются вправо.

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

Код/Реализация Python:

def partition(arr,low,high): i = ( low-1 ) # index of smaller element [high] # pivot for j in range(low , high): if arr[j] < pivot: +1 [j],arr[i] [high],arr[i+1] return ( i+1 ) def quickSort(arr,low,high): if low < high: (arr,low,high) quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) # Verify if it works random_list_of_nums = [22, 5, 1, 18, 99] quick_sort(random_list_of_nums) print(random_list_of_nums)

5 – Методы Сортировки Слиянием С Использованием Python

Сортировка слиянием-это алгоритм “Разделяй и властвуй”. Он делит входной массив на две половины, вызывает себя для этих двух половин, а затем объединяет две отсортированные половины. Функция merge () используется для слияния двух половин. Слияние(arr, l, m, r) – это ключевой процесс, который предполагает, что arr[l..m] и arr[m+1..r] отсортированы и объединяют два отсортированных суб-массива в один. Подробнее см. Следующую реализацию C

Мы рекурсивно делим список пополам, пока не получим списки с размером один. Затем мы объединяем каждую половину, которая была разделена, сортируя их в процессе.

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

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

Код/Реализация Python:

def mergeSort(arr): if len(arr) >1: (arr)//2 #Finding the mid of the array [:mid] [mid:] mergeSort(L) mergeSort(R) while i < len(L) and j < len(R): if L[i] < R[j]: [i] else: [j] while i < len(L): [i] while j < len(R): [j] def printList(arr): for i in range(len(arr)): ) print() if __name__: arr = [12, 11, 13, 5, 6, 7] print ("Given array is",) printList(arr) mergeSort(arr) print("Sorted array is: ",) printList(arr) # Verify it works random_list_of_nums = [120, 45, 68, 250, 176](random_list_of_nums) print(random_list_of_nums)

Итак, выше приведены некоторые из популярных методов сортировки в Python. Сортировка и листинг делают take объектно-ориентированным и помогают легко реализовывать и запускать коды. Следовательно, техника сортировки очень важна.

Читайте ещё по теме:

Источник