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

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

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

Описание алгоритма сортировки вставками

Алгоритм работы сортировки вставками заключается в следующем:

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

Реализация сортировки вставками

def insertion_sort(array): length = len(array) for i in range(1, length): key = array[i] j = i while (j - 1 >= 0) and (array[j - 1] > key): array[j - 1], array[j] = array[j], array[j - 1] j = j - 1 array[j] = key print("Сортировка вставками") arr = [] length = int(input("Введите длину массива: ")) for i in range(0, length): element = int(input("arr[" + str(i + 1) + "] hljs-built_in">append(element) insertion_sort(arr) print("Отсортированный массив: ") print(arr) 

Результат работы программы:

Источник

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

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

Как работает сортировка вставками

1. Выполните итерацию слева направо по массиву.
2. Сравните каждый элемент с предыдущими и поместите его в правильное место в отсортированном подмассиве.
3. Он начинается с 1 и сравнивает элемент — 1.
4. Сортировка будет продолжаться до тех пор, пока не будут отсортированы все компоненты.

Графическое представление работ по сортировке вставок

где: Comparing — сравнение, Swap — обмен.

Сортировка по вставке

Шаги, которые необходимо предпринять

1. Во-первых, вам нужно найти длину массива.
2. Вы не должны забывать, что элементы массива сравниваются с предыдущими значениями, поэтому цикл for должен начинаться с 1 до длины списка, а затем вам нужно использовать цикл while else для сравнения элементов массива.
3. Вам нужно поменять местами, если массив x-1 больше текущего значения массива; в противном случае вам не нужно изменять положение массива.
4. Возвращаемое значение после сортировки.

def ins_sort(aray): len_list = len(aray) for i in range(1, len_list): ref_value = aray[i] x = i while x>0 and aray[x-1] > ref_value: aray[x] = aray[x-1] x -= 1 else: aray[x] = ref_value return aray aray=[6,5,3,1,2] print("before sort ",aray) hello=ins_sort(aray) print("result sorted is ",hello)

before sort [6, 5, 3, 1, 2] result sorted is [1, 2, 3, 5, 6]

Далее мы вам предлагаем ознакомиться дополнительными трюками Python для легкого управления списками в ваших проектах.

Источник

Виды алгоритмов сортировки в Python

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

Встроенные методы сортировки в Python

Стандартный метод сортировки списка по возрастанию – sort(). Пример использования:

nums = [54, 43, 3, 11, 0] nums.sort() print(nums) # Выведет [0, 3, 11, 43, 54]

Метод sorted() создает новый отсортированный список, не изменяя исходный. Пример использования:

nums = [54, 43, 3, 11, 0] nums2 = sorted(nums) print(nums, nums2) # Выведет [54, 43, 3, 11, 0] [0, 3, 11, 43, 54]

Если нам нужна сортировка от большего числа к меньшему, то установим флаг reverse=True. Примеры:

nums = [54, 43, 3, 11, 0] nums.sort(reverse=True) print(nums) # Выведет [54, 43, 11, 3, 0] nums = [54, 43, 3, 11, 0] nums2 = sorted(nums, reverse=True) print(nums, nums2) # Выведет [54, 43, 3, 11, 0] [54, 43, 11, 3, 0]

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

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

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

Сравниваются первые два элемента. Если первый элемент больше, то они меняются местами. Далее происходит все то же самое, но со следующими элементами до последней пары элементов в списке.

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

def bubble(list_nums): swap_bool = True while swap_bool: swap_bool = False for i in range(len(list_nums) - 1): if list_nums[i] > list_nums[i + 1]: list_nums[i], list_nums[i + 1] = list_nums[i + 1], list_nums[i] swap_bool = True nums = [54, 43, 3, 11, 0] bubble(nums) print(nums) # Выведет [0, 3, 11, 43, 54]

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

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

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

Пример сортировки вставками:

def insertion(list_nums): for i in range(1, len(list_nums)): item = list_nums[i] i2 = i - 1 while i2 >= 0 and list_nums[i2] > item: list_nums[i2 + 1] = list_nums[i2] i2 -= 1 list_nums[i2 + 1] = item nums = [54, 43, 3, 11, 0] insertion(nums) print(nums) # Выведет [0, 3, 11, 43, 54]

Сортировка выборкой

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

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

Пример сортировки выборкой:

def selection(sort_nums): for i in range(len(sort_nums)): index = i for j in range(i + 1, len(sort_nums)): if sort_nums[j] < sort_nums[index]: index = j sort_nums[i], sort_nums[index] = sort_nums[index], sort_nums[i] nums = [54, 43, 3, 11, 0] selection(nums) print(nums) # Выведет [0, 3, 11, 43, 54]

Пирамидальная сортировка

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

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

Хоть алгоритм и кажется сложным, он значительно быстрее остальных, что особенно заметно при обработке больших списков.

Пример пирамидальной сортировки:

def heapify(sort_nums, heap_size, root): l = root left = (2 * root) + 1 right = (2 * root) + 2 if left < heap_size and sort_nums[left] >sort_nums[l]: l = left if right < heap_size and sort_nums[right] >sort_nums[l]: l = right if l != root: sort_nums[root], sort_nums[l] = sort_nums[l], sort_nums[root] heapify(sort_nums, heap_size, l) def heap(sort_nums): size = len(sort_nums) for i in range(size, -1, -1): heapify(sort_nums, size, i) for i in range(size - 1, 0, -1): sort_nums[i], sort_nums[0] = sort_nums[0], sort_nums[i] heapify(sort_nums, i, 0) nums = [54, 43, 3, 11, 0] heap(nums) print(nums) # Выведет [0, 3, 11, 43, 54]

Сортировка слиянием

Алгоритм разделяет список на две части, каждую из них он разделяет еще на две и так далее, пока не останутся отдельные единичные элементы. Далее соседние элементы сортируются парами. Затем эти пары объединяются и сортируются с другими парами, пока не обработаются все элементы в списке.

Пример сортировки слиянием:

def mergeSort(sort_nums): if len(sort_nums)>1: mid = len(sort_nums)//2 lefthalf = sort_nums[:mid] righthalf = sort_nums[mid:] mergeSort(lefthalf) mergeSort(righthalf) i=0 j=0 k=0 while i
Быстрая сортировка в Python
Один из самых популярных алгоритмов при сортировке списков. При правильном использовании он не требует много памяти и выполняется очень быстро.
Алгоритм разделяет список на две равные части, принимая псевдослучайный элемент и используя его в качестве опоры, то есть центра деления. Элементы, меньшие, чем опора, перемещаются влево от опоры, а элементы, размер которых больше опоры – вправо. Этот процесс повторяется для списка слева от опоры, а также для массива элементов справа от опоры, пока весь массив не будет отсортирован. Алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементу списка.
Пример быстрой сортировки:
def partition(sort_nums, begin, end): part = begin for i in range(begin+1, end+1): if sort_nums[i] = end: return part = partition(sort_nums, begin, end) quick(sort_nums, begin, part-1) quick(sort_nums, part+1, end) return quick(sort_nums, begin, end) nums = [54, 43, 3, 11, 0] quick_sort(nums) print(nums) # Выведет [0, 3, 11, 43, 54]
 
Скорость работы алгоритмов
 
Сортировка слиянием почти в два раза медленнее, чем быстрая сортировка. Сортировка выборкой выполняет больше сравнений, чем сортировка вставками, но выполняется немного быстрее.
 
Пузырьковая сортировка не подойдет для практического применения, так как она является самой медленной из всех. Но знать данный алгоритм будет полезно тем, кто хочет полностью изучить тему алгоритмов сортировки списков в Python.
 
Итог
 
Мы изучили виды сортировки списков в Python и сравнили их эффективность, а также рассмотрели встроенные методы. Надеюсь, данная статья была полезна для вас!
 
Источник