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

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

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

Источник

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)

Источник