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

Курсы

Программирование
iOS Developer. Basic
-23%
Python Developer. Professional
-13%
Разработчик на Spring Framework
-23%
Golang Developer. Professional
-17%
Python Developer. Basic
-16%
iOS Developer. Professional
-13%
Node.js Developer
-15%
Unity Game Developer. Professional
-11%
React.js Developer
-12%
Android Developer. Professional
-7%
Software Architect
-12%
C++ Developer. Professional
-8%
Разработчик C#
-8%
Backend-разработчик на PHP Архитектура и шаблоны проектирования
-12%
Программист С Базы данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Agile Project Manager Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер-практикум по использованию и настройке GIT IoT-разработчик Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-17%
DevOps практики и инструменты
-18%
Архитектор сетей
-21%
Инфраструктурная платформа на основе Kubernetes
-22%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив по управлению миграциями (DBVC)
-16%
Administrator Linux.Basic
-10%
Супер-интенсив «ELK»
-10%
Administrator Linux. Professional MS SQL Server Developer Безопасность Linux PostgreSQL Reverse-Engineering. Professional CI/CD VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

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

Как и в случае с сортировкой выборкой, алгоритм сортировки вставками выполняет сегментацию списка на 2 части: сортированную и несортированную. Далее алгоритм перебирает 2-й сегмент, вставляя текущий элемент в правильную позицию 1-го сегмента.

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

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

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

Реализация алгоритма

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

def insertion_sort(nums):  
    # Сортировка начинается со 2-го элемента, так как по умолчанию считается, что 1-й элемент уже отсортирован
    for i in range(1, len(nums)):
        item_to_insert = nums[i]
        # Сохраняется ссылка на индекс предыдущего элемента
        j = i - 1
        # Элементы сортированного сегмента перемещаются вперёд, если они больше, чем элемент для вставки
        while j >= 0 and nums[j] > item_to_insert:
            nums[j + 1] = nums[j]
            j -= 1
        # Вставляется элемент
        nums[j + 1] = item_to_insert

# Происходит проверка работоспособности
random_list_of_nums = [9, 1, 15, 28, 6]  
insertion_sort(random_list_of_nums)  
print(random_list_of_nums)

Время сортировки вставками

Время сортировки с использованием этого алгоритма, как правило, равняется O(n2), где n — число элементов списка.

Источник — «Sorting Algorithms in Python».

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться