Вставками

Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса Алгоритмы и структуры данных от OTUS.

---

Введение

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

Постановка задачи

Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.

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

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

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

Сортировка массива вставками осуществляется так: также как и в случае сортировки выбором массив делится на две части. Одна из частей называется отсортированной, а другая неотсортированной. Алгоритм предполагает проход по всему массиву с тем, чтобы длина отсортированной части стала равна длине всего массива. В рамках каждой итерации мы берем первый элемент неотсортированной части массива и осуществляем с ним следующую операцию: пока наш элемент строго меньше чем предыдущий меняем их местами. После чего увеличиваем длину отсортированной части массива на единицу. Таким образом путем последовательного перемещения изучаемого элемента мы добиваемся того, чтобы он встал на свое место. Пример осуществления одной итерации представлен ниже:
1 3 5 | 2 9 6 -> 1 3 2 5 9 6 -> 1 2 3 5 9 6 -> 1 2 3 5 | 9 6

Реализация

Предлагаю посмотреть на реализацию данного алгоритма на языке C:

void insertionSortFunction(double array[], int size) {    int i, j, temp;    // i представляет длину отсортированной части массива, начинаем с 1, потому что один элемент сам по себе считается упорядоченным    for (i = 1; i < size; i++) {        temp = array[i];        for (j = i - 1; j >= 0; j--) {            if (array[j] < temp) {                break;            }              array[j + 1] = array[j];            array[j] = temp;        }    }}

Анализ

Предлагаю проанализировать данный алгоритм.

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

.

Со временем все несколько интереснее. Тело внутреннего цикла само по себе выполняется за O(1), то есть не зависит от размера сортируемого массива. Это означает, что для понимания асимптотики алгоритма необходимо посчитать сколько раз выполняется это тело. Но количество итераций внутреннего цикла зависит от того, насколько хорошо упорядочены (или не упорядочены) элементы сортируемого массива. Для осуществления анализа необходимо посмотреть несколько случаев.

Минимальное количество итераций достигается в том случае, если сортируемый массив уже отсортирован. Действительно, для каждой итерации внешнего цикла for происходит ровно одна итерация внутреннего цикла. Это так называемый лучший случай.

Таким образом, сортировка осуществляется за линейное время.

В худшем случае число итераций предполагается наибольшим, то есть break никогда не срабатывает. На первой итерации внешнего цикла осуществляется одна итерация внутреннего цикла. На второй итерации внешнего цикла осуществляется 2 итерации внутреннего цикла. Продолжая рассуждение дальше, можно прийти к тому, что на последней ((n 1) ой) итерации внешнего цикла выполниться (n 1) итерация внутреннего цикла. Получаем:

Для осуществления вычислений мы воспользовались свойствами О нотации и формулой суммы арифметической прогрессии.

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

Если подводить итоги, то асимптотика алгоритма по памяти

по времени в лучшем случае

и в среднем и в худшем случаях

Поэтому данную сортировку относят к классу квадратичных сортировок.

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

Итоги

Мы рассмотрели еще одну квадратичную сортировку: сортировку вставками, посмотрели на ее устойчивую реализацию. Сортировка является преимущественно учебной, хотя на практике она может применяться благодаря неплохой асимптотике в лучшем случае: если к достаточно большому упорядоченному объему данных понадобится добавить новые данные так, чтобы все данные были опять упорядочены, может пригодится внутренний цикл for. Таким образом, можно поддерживать за

упорядоченность объема данных.

---

Узнать о курсе подробнее.

---

Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса Алгоритмы и структуры данных от OTUS. По ссылке вы сможете подробно узнать о курсе, а также бесплатно посмотреть запись Demo-урока по теме: Три алгоритма поиска шаблона в тексте.

---

Введение

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

Постановка задачи

Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.

Быстрая сортировка

В прошлый раз мы поговорили о чуть более сложной сортировке сортировке вставками. Сегодня речь пойдет о существенно более сложном алгоритме быстрой сортировке (еще ее называют сортировкой Хоара).

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

Алгоритм быстрой сортировки является рекурсивным, поэтому для простоты процедура на вход будет принимать границы участка массива от l включительно и до r не включительно. Понятно, что для того, чтобы отсортировать весь массив, в качестве параметра l надо передать 0, а в качестве r n, где по традиции n обозначает длину массива.

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

Реализация partiion'а:
partition(l, r):
pivot = a[random(l ... r - 1)]
m = l
for i = l ... r - 1:
if a[i] < pivot:
swap(a[i], a[m])
m++
return m


Пивот в нашем случае выбирается случайным образом. Такой алгоритм называется рандомизированным. На самом деле пивот можно выбирать самым разным образом: либо брать случайный элемент, либо брать первый / последний элемент учатка, либо выбирать его каким-то умным образом. Выбор пивота является очень важным для итоговой сложности алгоритма сортировки, но об этом несколько позже. Сложность же процедуры partition O(n), где n = r l длина участка.

Теперь используем partition для реализации сортировки:

Реализация partiion'а:
sort(l, r):
if r - l = 1:
return
m = partition(l, r)
sort(l, m)
sort(m, r)


Крайний случай массив из одного элемента обладает свойством упорядоченности. Если массив длинный, то применяем partition и вызываем процедуру рекурсивно для двух половин массива.

Если прогнать написанную сортировку на примере массива 1 2 2, то можно заметить, что она никогда не закончится. Почему так получилось?

При написании partition мы сделали допущение все элементы массива должны быть уникальны. В противном случае возвращаемое значение m будет равно l и рекурсия никогда не закончится, потому как sort(l, m) будет вызывать sort(l, l) и sort(l, m). Для решения данной проблемы надо массив разделять не на 2 части (< pivot и >= pivot), а на 3 части (< pivot, = pivot, > pivot) и вызывать рекурсивно сортировку для 1-ой и 3-ей частей.

Анализ

Предлагаю проанализировать данный алгоритм.

Временная сложность алгоритма выражается через нее же по формуле: T(n) = n + T(a * n) + T((1 a) * n). Таким образом, когда мы вызываем сортировку массива из n элементов, тратится порядка n операций на выполнение partition'а и на выполнения себя же 2 раза с параметрами a * n и (1 a) * n, потому что пивот разделил элемент на доли.

В лучшем случае a = 1 / 2, то есть пивот каждый раз делит участок на две равные части. В таком случае: T(n) = n + 2 * T(n / 2) = n + 2 * (n / 2 + 2 * T(n / 4)) = n + n + 4 * T(n / 4) = n + n + 4 * (n / 4 + 2 * T(n / 8)) = n + n + n + 8 * T(n / 8) =. Итого будет log(n) слагаемых, потому как слагаемые появляются до тех пор, пока аргумент не уменьшится до 1. В результате T(n) = O(n * log(n)).

В худшем случае a = 1 / n, то есть пивот отсекает ровно один элемент. В первой части массива находится 1 элемент, а во второй n 1. То есть: T(n) =n + T(1) + T(n 1) = n + O(1) + T(n 1) = n + O(1) + (n 1 + O(1) + T(n 2)) = O(n^2). Квадрат возникает из-за того, что он фигурирует в формуле суммы арифметической прогрессии, которая появляется в процессе расписывания формулы.

В среднем в идеале надо считать математическое ожидание различных вариантов. Можно показать, что если пивот делит массив в отношении 1:9, то итоговая асимптотика будет все равно O(n * log(n)).

Сортировка называется быстрой, потому что константа, которая скрывается под знаком O на практике оказывается достаточно небольшой, что привело к широкому распространению алгоритма на практике.

Читать ещё:

• Сортировка вставками
• Удаление узлов из красно-чёрного дерева