Пузырьковая сортировка питон код

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Алгоритмы сортировки и их реализация на Python

ViktorSalimonov/sorting-algorithms

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Алгоритмы сортировки на Python

Сортировка пузырьком (Bubble Sort)

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

def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr

Сортировка выбором (Selection Sort)

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

def selection_sort(arr): n = len(arr) for i in range(n-1): min_index = i for j in range(i+1, n): if arr[j]  arr[min_index]: min_index = j if min_index != i: arr[i], arr[min_index] = arr[min_index], arr[i] return arr

Сортировка вставками (Insertion Sort)

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

def insertion_sort(arr): n = len(arr) for i in range(1, n): current_value = arr[i] j = i - 1 while j >= 0: if current_value  arr[j]: arr[j+1] = arr[j] arr[j] = current_value j = j - 1 else: break return arr

Быстрая сортировка (Quick Sort)

Рекурсивный алгоритм, который работает по следующему принципу:

1. Выбрать опорный элемент из массива. Это можно сделать разными способами, в данной реализации этой будет случайный элемент.
2. Сравнить все элементы с опорным и распределить их в подмассивы. Первый подмассив будет состоять из элементов, которые меньше опорного; второй — больше опорного или равные.
3. Рекурсивно выполнить шаги 1 и 2, пока в подмассиве есть хотя бы 2 элемента.

import random def quick_sort(arr): n = len(arr) if n  1: return arr else: pivot = random.choice(arr) less = [x for x in arr if x  pivot] greater_or_equal = [x for x in arr if x >= pivot] return quick_sort(less) + quick_sort(greater_or_equal)

• В худшем случае O(n²)
• В среднем случае O(n * log n)
• В лучшем случае O(n * log n)

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

Рекурсивный алгоритм, который работает по следующему принципу:

1. Разделить массив на две равные части
2. Отсортировать каждую половину
3. Из двух отсортированных массивов получить один (операция слияния)

def merge_sort(arr): n = len(arr) if n  1: return arr else: middle = int(len(arr) / 2) left = merge_sort(arr[:middle]) right = merge_sort(arr[middle:]) return merge(left, right) def merge(left, right): result = [] while len(left) > 0 and len(right) > 0: if left[0]  right[0]: result.append(left[0]) left = left[1:] else: result.append(right[0]) right = right[1:] if len(left) > 0: result += left if len(right) > 0: result += right return result

• В худшем случае O(n * log n)
• В среднем случае O(n * log n)
• В лучшем случае O(n * log n)

Источник

Пузырьковая сортировка в 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

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

Источник