- Saved searches
- Use saved searches to filter your results more quickly
- ViktorSalimonov/sorting-algorithms
- Name already in use
- Sign In Required
- Launching GitHub Desktop
- Launching GitHub Desktop
- Launching Xcode
- Launching Visual Studio Code
- Latest commit
- Git stats
- Files
- README.md
- Сортировка пузырьком на Python
- Введение
- Алгоритм работы сортировки пузырьком
- Сортировка пузырьком на Python
- Заключение
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, пока в подмассиве есть хотя бы 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)
Рекурсивный алгоритм, который работает по следующему принципу:
- Разделить массив на две равные части
- Отсортировать каждую половину
- Из двух отсортированных массивов получить один (операция слияния)
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.
Сортировка пузырьком – простой метод сортировки массивов, который последовательно сравнивает и обменивает соседние элементы, если предыдущий оказался больше последующего.
Алгоритм работы сортировки пузырьком
Допустим у нас есть следующий массив: [1, 5, 10, 2, 6, 4]
- Значение первого элемента массива сравниваем со вторым. Если первый оказался больше второго, то они меняются местами, если нет – идём дальше:
1 > 5 – Единица меньше пяти, поэтому идём дальше. - Берём значение второго элемента массива и сравниваем с третьим. Если второй больше третьего, то меняем их местами, если нет – идём дальше
5 > 10 – Пять меньше десяти, поэтому идём дальше. - Повторяем всё те же действия, пока не кончится массив. В конце массива должен оказаться самый большой элемент.
10 > 2 – Десять больше двух, меняем их местами
10 > 6 – Десять больше шести, меняем их местами
10 > 4 – Десять больше четырёх, меняем их местами
Итог после первой итерации: [1, 5, 2, 6, 4, 10] - Переходим к следующей итерации, но в этот раз последний элемент затрагиваться не будет, т.к. в прошлой итерации было выявлено, что он самый большой.
Как менялся наш массив по итерациям:
1 итерация – [1, 5, 2, 6, 4, 10]2 итерация – [1, 2, 5, 4, 6, 10]3 итерация – [1, 2, 4, 5, 6, 10]4 итерация – [1, 2, 4, 5, 6, 10]5 итерация – [1, 2, 4, 5, 6, 10]6 итерация – [1, 2, 4, 5, 6, 10]7 итерация – [1, 2, 4, 5, 6, 10]
Сортировка пузырьком на Python
Для начала напишем генератор рандомного списка:
from random import randint # Заполняем список 10 рандомными элементами подбираемыми рандомно от 1, до 100 array = [randint(1, 100) for i in range(10)] print(array)
Определим количество элементов в списке:
from random import randint # Заполняем список 10 рандомными элементами подбираемыми рандомно от 1, до 100 array = [randint(1, 100) for i in range(10)] print(array) length = len(array)
Создадим цикл, количество итераций в котором будет length-1:
from random import randint # Заполняем список 10 рандомными элементами подбираемыми рандомно от 1, до 100 array = [randint(1, 100) for i in range(10)] print(array) length = len(array) for i in range(length-1):
Внутри создадим вложенный цикл, у которого будет length-i-1 итераций:
from random import randint # Заполняем список 10 рандомными элементами подбираемыми рандомно от 1, до 100 array = [randint(1, 100) for i in range(10)] print(array) length = len(array) for i in range(length-1): for j in range(length-i-1):
Дальше будет идти условие, сравнивающее элемент массива со следующим элементом. Если же он больше, то они меняются местами, если нет – идёт следующая итерация:
from random import randint # Заполняем список 10 рандомными элементами подбираемыми рандомно от 1, до 100 array = [randint(1, 100) for i in range(10)] print(array) length = len(array) for i in range(length-1): for j in range(length-i-1): if array[j] > array[j+1]: b = array[j] array[j] = array[j+1] array[j+1] = b print(array)
Начальный список – [71, 58, 30, 61, 95, 58, 100, 27, 46, 95]Отсортированный список – [27, 30, 46, 58, 58, 61, 71, 95, 95, 100]
Заключение
В ходе статьи мы с Вами разобрались с тем, как работает сортировка пузырьком, и смогли её реализовать на Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂