сортировка бинарными вставками c код
В мире алгоритмов: Сортировка Вставками
От автора
Данная статья рассматривает один из алгоритмов сортировки массивов. Она предназначена для новичков или же для тех кто по каким-то причинам не знаком с данным алгоритмом. Исправления и поправки только приветствуются:)
Теория
Сортировка вставками (Insertion Sort) — это простой алгоритм сортировки. Суть его заключается в том что, на каждом шаге алгоритма мы берем один из элементов массива, находим позицию для вставки и вставляем. Стоит отметить что массив из 1-го элемента считается отсортированным.
Словесное описание алгоритма звучит довольно сложно, но на деле это самая простая в реализации сортировка. Каждый из нас, не зависимо от рода деятельности, применял алгоритм сортировки, просто не осознавал это:) Например когда сортировали купюры в кошельке — берем 100 рублей и смотрим — идут 10, 50 и 500 рублёвые купюры. Вот как раз между 50 и 500 и вставляем нашу сотню:) Или приведу пример из всех книжек — игра в карточного «Дурака». Когда мы тянем карту из колоды, смотрим на наши разложенные по возрастанию карты и в зависимости от достоинства вытянутой карты помещаем карту в соответствующее место. Для большей наглядности приведу анимацию из википедии. 
Реализация
Прежде чем приступить к реализации определимся с форматом входных данных — для примера это будет массив целочисленных (int) значений. Нумерация элементов массива начинается с 0 и заканчивается n-1. Сам алгоритм реализуем на языке C++. Итак приступим…
Основной цикл алгоритма начинается не с 0-го элемента а с 1-го, потому что элемент до 1-го элемента будет нашей отсортированной последовательностью (помним что массив состоящий из одного элемента является отсортированным) и уже относительно этого элемента с номером 0 мы будем вставлять все остальные. Собственно код:
Реализация сортировки очень проста, всего 3 строчки. Функция swap меняет местами элементы x[j-1] и x[j]. Вложенный цикл ищет место для вставки. Рекомендую запомнить этот алгоритм, чтобы в случае необходимости написать сортировку не позориться сортировкой пузырьком:)
Эффективность
Сортировка вставками наиболее эффективна когда массив уже частично отсортирован и когда элементов массива не много. Если же элементов меньше 10 то данный алгоритм является лучшим. Не зря в быстрой сортировке (оптимизация Боба Седжвика) используется алгоритм сортировки вставками как вспомогательный, но об этом алгоритме мы поговорим позже…
Бинарная сортировка вставок
// C программа для реализации бинарной сортировки вставок
#include
// Функция на основе бинарного поиска для поиска позиции
// где элемент должен быть вставлен в [low..high]
int binarySearch( int a[], int item, int low, int high)
return (item > a[low])? (low + 1): low;
int mid = (low + high)/2;
return binarySearch(a, item, mid+1, high);
return binarySearch(a, item, low, mid-1);
// Функция для сортировки массива a [] размера ‘n’
void insertionSort( int a[], int n)
int i, loc, j, k, selected;
// найти место, где выбрано, может быть
loc = binarySearch(a, selected, 0, j);
// Переместить все элементы после расположения, чтобы создать пространство
// Программа драйвера для проверки вышеуказанной функции
int n = sizeof (a)/ sizeof (a[0]), i;
printf ( «Sorted array: \n» );
// Реализация Java-программы
// двоичная вставка
public static void main(String[] args)
public void sort( int array[])
// Найти место для вставки с помощью бинарного поиска
// Смещение массива в одну позицию вправо
// Размещение элемента в правильном месте
// Код предоставлен Mohit Gupta_OMG
# Реализация программы Python
# двоичного типа вставки
def binary_search(arr, val, start, end):
# мы должны различать, должны ли мы вставить
# до или после левой границы.
# это происходит, если мы выходим за левую границу
# означает, что левая граница является наименьшей позицией для
# найти число больше чем val
mid = (start + end) / 2
arr = arr[:j] + [val] + arr[j:i] + arr[i + 1 :]
print ( «Sorted array:» )
# Код предоставлен Mohit Gupta_OMG
// C # Реализация программы
// двоичная вставка
public static void Main()
public static void sort( int []array)
// Найти место для вставки используя
int j = Math.Abs(Array.BinarySearch(
// Смещение массива в одну позицию вправо
System.Array.Copy(array, j, array,
// Размещение элемента в правильном
// Этот код предоставлен нитин митталь.
// PHP программа для реализации
// двоичная вставка
// Функция поиска на основе бинарного поиска
// позиция, где должен быть элемент
// вставляем в [low..high]
// Функция для сортировки массива a размера ‘n’
// найти место где выбран
// элемент должен быть вставлен
// Переместить все элементы после расположения
$a = array (37, 23, 0, 17, 12, 72,
echo «Sorted array:\n» ;
// Этот код предоставлен
// Адеш Сингх
?>
Выход:
Сложность времени: алгоритм в целом все еще имеет время выполнения в наихудшем случае O (n 2 ) из-за серии перестановок, необходимых для каждой вставки.
Сортировки массивов
Задача сортировки
Эта лекция посвящена сугубо алгоритмической проблеме упорядочения данных.
Эту лекцию мы посвятим только внутренним сортировкам. Их важная особенность состоит в том, что эти алгоритмы не требуют дополнительной памяти: вся работа по упорядочению производится внутри одного и того же массива.
Простые сортировки
Как правило, сложность алгоритмов подсчитывают раздельно по количеству сравнений и по количеству перемещений данных в памяти (пересылок), поскольку выполнение этих операций занимает различное время. Однако точные значения удается найти редко, поэтому для оценки алгоритмов ограничиваются лишь понятием «пропорционально», которое не учитывает конкретные значения констант, входящих в итоговую формулу. Общую же эффективность алгоритма обычно оценивают «в среднем»: как среднее арифметическое от сложности алгоритма «в лучшем случае» и «в худшем случае», то есть (Eff_best + Eff_worst)/2.
Сортировка простыми вставками
— начав с конца уже существующей упорядоченной последовательности, все ее элементы, которые больше, чем вновь вводимый элемент, сдвинуть на 1 шаг назад;
— записать новый элемент на освободившееся место.
При этом, разумеется, можно прочитать все вводимые элементы одновременно, записать их в массив, а потом «воображать», что каждый очередной элемент был введен только что. На суть и структуру алгоритма это не повлияет.
Реализация алгоритма ПрВст
Метод прямых вставок с барьером (ПрВстБар)
Для того чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний var) и будем записывать в нее поочередно каждый вставляемый элемент (сравните строки <*>и <**>в приведенных вариантах программы). В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как «барьер», не дающий индексу j выйти за нижнюю границу массива. Кроме того, компонента a[0] может заменить собою и дополнительную переменную х:
Эффективность алгоритма ПрВстБар
Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм ПрВстБар совершит N-1 сравнение и 0 пересылок данных.
N 2 (читается «порядка эн квадрат») по обоим параметрам.
Предположим, что нужно отсортировать следующий набор чисел:
Выполняя алгоритм ПрВстБар, мы получим такие результаты (подчеркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):
Сортировка бинарными вставками
Сортировку простыми вставками можно немного улучшить: поиск «подходящего места» в упорядоченной последовательности можно вести более экономичным способом, который называется Двоичный поиск в упорядоченной последовательности. Он напоминает детскую игру «больше-меньше»: после каждого сравнения обрабатываемая последовательность сокращается в два раза.
Пусть, к примеру, нужно найти место для элемента 7 в таком массиве:
Найдем средний элемент этой последовательности (10) и сравним с ним семерку. После этого все, что больше 10 (да и саму десятку тоже), можно смело исключить из дальнейшего рассмотрения:
Снова возьмем середину в отмеченном куске последовательности, чтобы сравнить ее с семеркой. Однако здесь нас поджидает небольшая проблема: точной середины у новой последовательности нет, поэтому нужно решить, который из двух центральных элементов станет этой «серединой». От того, к какому краю будет смещаться выбор в таких «симметричных» случаях, зависит окончательная реализация нашего алгоритма. Давайте договоримся, что новой «серединой» последовательности всегда будет становиться левый центральный элемент. Это соответствует вычислению номера «середины» по формуле
Итак, отсечем половину последовательности:
Таким образом, мы нашли в исходной последовательности место, «подходящее» для нового элемента. Если бы в той же самой последовательности нужно было найти позицию не для семерки, а для девятки, то последовательность границ рассматриваемых промежутков была бы такой:
Из приведенных примеров уже видно, что поиск ведется до тех пор, пока левая граница не окажется правее(!) правой границы. Кроме того, по завершении этого поиска последней левой границей окажется как раз тот элемент, на котором необходимо закончить сдвиг «хвоста» последовательности.
Будет ли такой алгоритм универсальным? Давайте проверим, что же произойдет, если мы станем искать позицию не для семерки или девятки, а для единицы:
Кажется, будто все плохо: левая граница вышла за пределы массива; непонятно, что нужно сдвигать.
Вспомним, однако, что в реальности на (N+1)-й позиции как раз и находится вставляемый элемент (21). Таким образом, если левая граница вышла за рассматриваемый диапазон, получается, что ничего сдвигать не нужно. Вообще же такие действия выглядят явно лишними, поэтому от них стоит застраховаться, введя одну дополнительную проверку в текст алгоритма.
Реализация алгоритма БинВст
Эффективность алгоритма БинВст
Сортировка простым выбором
Попробуем теперь сократить количество пересылок элементов.
На каждом шаге (всего их будет ровно N-1) будем производить такие действия:
Эффективность алгоритма ПрВыб
В лучшем случае (если исходная последовательность уже упорядочена), алгоритм ПрВыб произведет (N-1)*(N+2)/2 сравнений и 0 пересылок данных. В остальных же случаях количество сравнений останется прежним, а вот количество пересылок элементов массива будет равным 3*(N-1).
Таким образом, алгоритм ПрВыб имеет квадратичную сложность (
N 2 ) по сравнениям и линейную (
Предположим, что нужно отсортировать тот же набор чисел, при помощи которого мы иллюстрировали метод сортировки простыми вставками:
Теперь мы будем придерживаться алгоритма ПрВыб (подчеркнута несортированная часть массива, а квадратиком выделен ее минимальный элемент):
Сортировка простыми обменами
Рассмотренными сортировками, конечно же, не исчерпываются все возможные методы упорядочения массивов.
Сортировка вставками
Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса «Алгоритмы и структуры данных» от OTUS.
Введение
Постановка задачи
Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.
Сортировка вставками
В прошлый раз мы поговорили об одной из простейших сортировок — сортировке выбором. Сегодня речь пойдет о несколько более сложном алгоритме — сортировке вставками.
Описание алгоритма
Реализация
Предлагаю посмотреть на реализацию данного алгоритма на языке C:
Анализ
Предлагаю проанализировать данный алгоритм.
Начать анализ проще всего будет с получения асимптотики памяти. Независимо от длины и структуры предлагаемого для сортировки массива выделяется память только для двух счетчиков цикла и одной вспомогательной переменной, служащей для осуществления обмена двух переменных значениями. Таким образом всегда верно:
Со временем все несколько интереснее. Тело внутреннего цикла само по себе выполняется за O(1), то есть не зависит от размера сортируемого массива. Это означает, что для понимания асимптотики алгоритма необходимо посчитать сколько раз выполняется это тело. Но количество итераций внутреннего цикла зависит от того, насколько хорошо упорядочены (или не упорядочены) элементы сортируемого массива. Для осуществления анализа необходимо посмотреть несколько случаев.
Минимальное количество итераций достигается в том случае, если сортируемый массив уже отсортирован. Действительно, для каждой итерации внешнего цикла for происходит ровно одна итерация внутреннего цикла. Это так называемый лучший случай.
Таким образом, сортировка осуществляется за линейное время.
В худшем случае число итераций предполагается наибольшим, то есть break никогда не срабатывает. На первой итерации внешнего цикла осуществляется одна итерация внутреннего цикла. На второй итерации внешнего цикла осуществляется 2 итерации внутреннего цикла. Продолжая рассуждение дальше, можно прийти к тому, что на последней ((n — 1) — ой) итерации внешнего цикла выполниться (n — 1) итерация внутреннего цикла. Получаем:
Для осуществления вычислений мы воспользовались свойствами О — нотации и формулой суммы арифметической прогрессии.
В среднем случае предполагается, что число итераций внутреннего цикла для какой-то конкретной итерации внешнего цикла равно его среднему значению, то есть математическому ожиданию. Предположим, что все допустимые числа срабатываний внутреннего цикла равновероятны. В таком случае, среднее число итераций внутреннего цикла равно 
. Предполагается, что i — это номер итерации внешнего цикла. Теперь для подсчета асимптотики необходимо вычислить . То есть мы просто подсчитываем сколько раз выполняется тело внутреннего цикла. Таким образом, получаем .
Если подводить итоги, то асимптотика алгоритма по памяти —
по времени в лучшем случае
и в среднем и в худшем случаях
Поэтому данную сортировку относят к классу квадратичных сортировок.
Также важно заметить, что сортировка выбором в такой реализации является устойчивой. Позволю себе напомнить, что сортировка называется устойчивой, если при ее выполнении порядок следования равных элементов не меняется. Это свойство не очень принципиально для такой учебной задачи, как сортировка массива чисел, но если бы мы сортировали какие-то более сложные объекты с установленным отношением порядка это могло бы быть важно. Подобный пример мы можем рассмотреть как-нибудь в следующий раз, когда будем говорить о поразрядной сортировке.
Сортировка вставками.
Сортировка вставками – простой алгоритм сортировки, преимущественно использующийся в учебном программировании. К положительной стороне метода относится простота реализации, а также его эффективность на частично упорядоченных последовательностях, и/или состоящих из небольшого числа элементов. Тем не менее, высокая вычислительная сложность не позволяет рекомендовать алгоритм в повсеместном использовании.
Рассмотрим алгоритм сортировки вставками на примере колоды игральных карт. Процесс их упорядочивания по возрастанию (в колоде карты расположены в случайном порядке) будет следующим. Обратим внимание на вторую карту, если ее значение меньше первой, то меняем эти карты местами, в противном случае карты сохраняют свои позиции, и алгоритм переходит к шагу 2. На 2-ом шаге смотрим на третью карту, здесь возможны четыре случая отношения значений карт:
В первом случае не происходит никаких перестановок. Во втором – вторая карта смещается на место третьей, первая на место второй, а третья карта занимает позицию первой. В предпоследнем случае первая карта остается на своем месте, в то время как вторая и третья меняются местами. Ну и наконец, последний случай требует рокировки лишь первой и третьей карт. Все последующие шаги полностью аналогичны расписанным выше.
Рассмотрим на примере числовой последовательности процесс сортировки методом вставок. Клетка, выделенная темно-серым цветом – активный на данном шаге элемент, ему также соответствует i-ый номер. Светло-серые клетки это те элементы, значения которых сравниваются с i-ым элементом. Все, что закрашено белым – не затрагиваемая на шаге часть последовательности.
Ниже на анимированном изображении показан еще один пример работы алгоритма сортировки вставками. Здесь, как и в предыдущем примере, последовательность сортируется по возрастанию.
Таким образом, получается, что на каждом этапе выполнения алгоритма сортируется некоторая часть массива, размер которой с шагом увеличивается, и в конце сортируется весь массив целиком.