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

Массив делится на две части - отсортированную и неотсортированную. В начале работы в отсортированную часть входит только один первый элемент. Алгоритм выполняетn-1 проход, на каждом из которых поочередно выбираются элементы из неотсортированной части и вставляются в отсортированную часть таким образом, чтобы не нарушить в ней упорядоченность элементов. На некотором i-м проходе элементы a1, a2, ..., ai составляют отсортированную часть, а элементы ai+1, ai+2, …, an - неотсортированную. Если f(ai) ≤ f(ai+1), то элемент ai+1включается в отсортированную часть. В противном случае значение ai+1 временно сохраняется в переменной s = ai+1, а элемент ai сдвигается на одну позицию вправо. Далее ключ f(s) поочередно сравнивается с ключами следующих элементов из отсортированной части справа налево, т.е. с ключами f(ak), k = i-1, i-2, ..., 1. Если f(S) < f(ak), то элемент ak сдвигается на одну позицию, вправо. В противном случае элемент S записывается в k+1-ю позицию. Скорость сортировки простыми вставками можно увеличить, если для поиска позиции элемента ai+1 в отсортированной части использовать метод бинарного поиска, так как элементы упорядочены. Это уменьшает общее число сравнений от O(n2) до O(n log2n), но количество перестановок элементов при этом не уменьшается и имеет порядок O(n2).

1.3 Сортировка подсчетом

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

Для описания данного и других методов сортировки введем некоторые определения. Пусть дано Nэлементов, которые необходимо упорядочить:

                     

 Назовем их записями. Также каждая запись   имеет свой ключ , который и управляет процессом сортировки. На множестве элементов a, b, c вводится соотношение “ < ”, таки образом, что выполняется:

1.  справедливо только одно из соотношений: a < b, a = b, b < a

2.  если a < b и b < c то a < c

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

                  

Теперь вернемся к нашему методу. Его смысл заключается в том, чтобы подсчитать количество ключей меньших каждого из ключей сортируемых элементов. То есть, если меньше ключа  имеется j ключей, то его положение в таблице ключей должно быть j+1. Очевидно, такой подсчет можно выполнить путем сравнений:

 

Но очевидно, что в этом алгоритме половина сравнений излишне, и его можно реализовать так:

 

Для реализации данного алгоритма целесообразно использовать дополнительную таблицу count[n]. В результате окончательное положение записи будет определено значением count[j] + 1. Итак, алгоритм (А) сортировки методом подсчета выглядит так:

    А_1. Установить count[1] .. count[N] равными 0

 А_2. [цикл по i] Выполнить шаг А_3 при i = N .. 2

 А_3. [цикл по j] Выполнить шаг А_4 при j = N .. 1

 А_4. если , то увеличить count[j] на 1; иначе увеличить count[i]

Отметим, что данный алгоритм не предусматривает перестановку самих записей. В чем то этот алгоритм похож на сортировку таблицы адресов, но в отличие от последней элемент  count[j] указывает куда нужно отправить элемент , а не элемент, который нужно отправить на место . Стоит отметить, что этот алгоритм дает верно упорядоченный файл записей независимо от числа одинаковых ключей.

Скорость работы такого алгоритма выражается формулой.

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

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

• Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в Ω(n log n) сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O(n log log n log log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О - обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O(log² n) операций. При этом число n должно быть заранее известно;

• Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O(log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляетO(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Свойства и классификация.

• Устойчивость (англ. stability) — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами^[3].

• Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

• Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

  • В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.

• Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), т. е. в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью.

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

  • Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

• потребности в дополнительной памяти или её отсутствию

• потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой

Список алгоритмов сортировки.