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

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

Сортировка вставками (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

Сортировка вставкой в Python – это простой и более эффективный алгоритм, чем алгоритм пузырьковой сортировки. Концепция основана на принципе колоды карт, в которой мы сортируем игральные карты в соответствии с конкретной картой. У этого метода есть много преимуществ, но есть много эффективных алгоритмов, доступных в структуре данных.

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

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

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

Давайте разберемся в следующих терминах.

Что означает “на месте” и “стабильно”?

• На месте: алгоритм на месте требует дополнительного пространства, не обращая внимания на размер ввода коллекции. После выполнения сортировки он перезаписывает исходные ячейки памяти элементов в коллекции.
• Стабильный: это термин, который управляет относительным порядком равных объектов в исходном массиве.

Что более важно, сортировка вставкой в Python не требует заранее знать размер массива, и она получает по одному элементу за раз.

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

Это более эффективно для массива небольшого (менее 10) размера. Теперь давайте разберемся с концепцией сортировки вставкой.

Концепция сортировки вставкой

Массив разделился практически на две части при сортировке вставками – несортированная часть и отсортированная часть.

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

Он фокусируется на вставке элементов путем перемещения всех элементов, если правое значение меньше левого.

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

Ниже приведен алгоритм сортировки массива с помощью вставки.

• Разбить список на две части – отсортированный и несортированный.
• Итерировать от arr [1] к arr [n] по заданному массиву.
• Сравнить текущий элемент со следующим элементом.
• Если текущий элемент меньше, чем следующий элемент, сравнить с предыдущим элементом. Переместиться к большим элементам на одну позицию вверх, чтобы освободить место для замененного элемента.

Разберемся в следующем примере.

Рассмотрим первый элемент отсортированного массива.

Первый шаг к добавлению 10 в отсортированный подмассив.

Теперь берем первый элемент из несортированного массива – 4. Это значение сохраняем в новой переменной temp. Теперь мы видим, что 10> 4, перемещаем 10 вправо, и это перезаписывает 4, которые были ранее сохранены.

Здесь 4 меньше, чем все элементы в отсортированном подмассиве, поэтому мы вставляем его в первую позицию индекса.

У нас есть два элемента в отсортированном подмассиве.

Теперь проверьте число 25. Мы сохранили его во временной переменной. 25> 10, а также 25> 4, затем мы помещаем его в третью позицию и добавляем в отсортированный подмассив.

Снова проверяем цифру 1. Сохраняем в темп. 1 меньше 25. Он перезаписывает 25.

[4, 10, 25, 25, 5] 10> 1, затем перезаписывается снова [25, 4, 10, 25, 5] 4> 1 теперь ставим значение temp = 1 [1, 4, 10, 25, 25] положите temp = 5

Теперь мы получаем отсортированный массив, просто помещая временное значение.

Данный массив отсортирован.

Реализация

Реализация вставки относительно проста. Мы будем реализовывать, используя массив целых чисел Python. Рассмотрим следующий пример –

# creating a function for insertion def insertion_sort(list1): # Outer loop to traverse through 1 to len(list1) for i in range(1, len(list1)): value = list1[i] # Move elements of list1[0..i-1], that are # greater than value, to one position ahead # of their current position j = i - 1 while j >= 0 and value < list1[j]: list1[j + 1] = list1[j] j -= 1 list1[j + 1] = value return list1 # Driver code to test above list1 = [10, 5, 13, 8, 2] print("The unsorted list is:", list1) print("The sorted list1 is:", insertion_sort(list1))

The unsorted list is: [10, 5, 13, 8, 2] The sorted list1 is: [2, 5, 8, 10, 13]

В приведенном выше коде мы создали функцию с именем insert_sort (list1). Внутри функции –

• Мы определили цикл for для обхода списка от 1 до len (list1).
• В цикле for присвоено значение list1 в значении. Каждый раз, когда цикл будет повторяться, новое значение будет присвоено переменной value.
• Затем мы переместили элементы list1 [0… i-1], которые больше значения, на одну позицию впереди их текущей позиции.
• Теперь мы использовали while, чтобы проверить, больше ли j или равно 0, а значение меньше первого элемента списка.
• Если оба условия верны, перемещаем первый элемент в 0-й индекс, уменьшаем значение j и так далее.
• После этого мы вызвали функцию, передали список и распечатали результат.

Сортировка настраиваемых объектов

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

Нам потребуется перегрузить операторы, чтобы по-другому отсортировать объекты. Но мы можем передать другой аргумент функции insert_sort(), используя лямбда-функцию. Лямбда-функция удобна при вызове метода сортировки.

Давайте разберемся в следующем примере сортировки пользовательских объектов.

Сначала мы определяем класс Point.

# Creating Point class class Point: def __init__(self, a, b): self.a = a self.b = b def __str__(self): return str.format("(<>,<>)", self.a, self.b) def insertion_sort(list1, compare_function): for i in range(1, len(list1)): Value = list1[i] Position = i while Position > 0 and compare_function(list1[Position - 1], Value): list1[Position] = list1[Position - 1] Position = Position - 1 list1[Position] = Value U = Point(2,3) V = Point(4,4) X = Point(3,1) Y = Point(8,0) Z = Point(5,2) list1 = [U,V,X,Y,Z] # We sort by the x coordinate, ascending insertion_sort(list1, lambda x, y: x.a > y.a) for point in list1: print(point)

The points are in the sorted order (2,3) (3,1) (4,4) (5,2) (8,0)

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

Сложность времени при сортировке вставкой

Сортировка вставкой – медленный алгоритм; иногда это кажется слишком медленным для обширного набора данных. Однако он эффективен для небольших списков или массивов.

Временная сложность сортировки вставкой – O (n2). Для итерации используются два цикла.

Еще одно важное преимущество сортировки вставкой: он используется популярным алгоритмом сортировки под названием Shell sort. Вспомогательное пространство в сортировке вставками: O (1)

Источник