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

1. СОРТИРОВКА ВСТАВКАМИ

Группа: 21ВА1
САМИЕВ КОБИЛДЖОН

2.

Сортировка вставками (insertion sort) – простой алгоритм
сортировки,
преимущественно
использующийся
в
учебном
программировании. К положительной стороне метода относится простота
реализации, а также его эффективность на частично упорядоченных
последовательностях, и/или состоящих из небольшого числа элементов.
Тем не менее, высокая вычислительная сложность не позволяет
рекомендовать алгоритм в повсеместном использовании.
Сортировка вставкой— алгоритм со сложностью порядка O(N^2).
Особенности алгоритма
прост в реализации;
эффективен на небольших наборах данных, на наборах данных до
десятков элементов может оказаться лучшим;
эффективен на наборах данных, которые уже частично
отсортированы;
устойчивый алгоритм сортировки (не меняет порядок элементов,
которые уже отсортированы);
может сортировать список по мере его получения;
не требует временной памяти, даже под стек.

3.

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

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

При сортировке вставками массив разбивается на две области: упорядоченную и и
неупорядоченную. Изначально весь массив является неупорядоченной областью. При первом
проходе первый элемент из неупорядоченной области изымается и помещается в правильном
положении в упорядоченной области.
На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной
области сокращается на 1.
Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в
правильное положение в упорядоченной области. Это сделано путем сдвига всех элементов
упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i] вставляется в
интервал между теми элементами, которые меньше [i], и теми, которые больше [i].
Операции:
Начало алгоритма
•Шаг 1: Повторить шаги с 2 по 5 для k = 1 до n-1
•Шаг 2: установить temp = A[ k ]
•Шаг 3: установить j = k – 1
•Шаг 4: Повторить, пока temp <=A[ j ] установить A[ j + 1] = A[ j ]
установить j = j – 1
[конец внутреннего цикла]
•Шаг 5: установить A[ j + 1 ] = temp [конец цикла]
•Шаг 6: вывод данных
Конец алгоритма

5.

6. Основные операции

Для сортировки массива
размером N в порядке возрастания:
Выполняет итерацию от arr[1]
до arr [N] по массиву.
Сравнивает текущий элемент
(ключ) с его предшественником.
Если ключевой элемент меньше
своего предшественника,
сравнивает его с предыдущими
элементами. Перемещает
элементы большого размера на
одну позицию вверх, чтобы
освободить место для
заменяемого элемента.

7. Исследование

В исследование будут два алгоритма(сортировки):
1.
Сортировка простыми вставками
2.
Сортировка Шелла,
Их часто сравнивают. Сортировка простыми вставками очень эффективна
для последовательности, которая почти упорядочена.
Сортировка Шелла является видом сортировки вставкой с изменяющимся
расстоянием между сравниваемыми ключами. Эффективности сортировки
Шелла математически достаточно сложен. Можно показать, что порядок
сложности сортировки Шелла может быть аппроксимирован величиной
0(n(log n)2), если используется подходящая последовательность шагов (т.е.
количества шагов на разных итерациях должны быть взаимно простыми
числами).
Сравнение между ними, во времени:
Среднее
время
Требования
к памяти
Примечания
Простые вставки
О(n2)
нет
Хорош для списков частично упорядоченных и
массивов n<20
Сортировка
Шелла
О(n1,25)
нет
Хорош для общего образования и для n<50

8. Заключение

В данном курсовом проекте при разработке программы были
закреплены навыки объектно-ориентированного программирования на
языке С++.
Освоены алгоритмы двух сортировок:
Сортировка вставки(простая)
Сортировка Шелла
При разработке пользовательского интерфейса, были освоены основные
объекты и их свойства.