Сортировка слиянием по-простому. Сортировка Слиянием (Merge-Sort)

Сортировка слиянием

(См. стр. 430 Ф.М. Каррано и Дж.Дж.Причард)

Два важных алгоритма сортировки, основанных на принципе "разделяй и властвуй", сортировка слиянием и быстрая сортировка, имеют элегантное рекурсивное воплощение и чрезвычайно эффективны. В этом разделе мы рассмотрим сортировку массивов методом слияний, однако в главе 14 будет показано, что этот алгоритм можно обобщить на внешние файлы. Формулируя алгоритм, будем пользоваться обозначением отрезка массива theArray .

Алгоритм сортировки методом слияний является рекурсивным. Его эффективность не зависит от порядка следования элементов в исходном массиве. Допустим, что мы разделили массив пополам, рекурсивно упорядочили обе половины, а затем объединили их в одно целое, как показано на рис. 9.8. На рисунке показано, что части массива <1, 4, 8> и <2, 3> объединяются в массив <1, 2, 3, 4, 8>. В ходе слияния элементы, стоящие в разных частях массива, попарно сравниваются друг с другом, и меньший элемент отправляется во временный массив. Этот процесс продолжается до тех пор, пока не будет использована одна из двух частей массива. Теперь достаточно просто скопировать оставшиеся элементы во временный массив. В заключение содержимое временного массива копируется обратно в исходный массив.

Рис. 9.8. Сортировка методом слияния с помощью вспомогательного массива

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

mergesort(inout theArray:ItemArray,

in first:integer, in last: integer)

// Упорядочивает отрезок theArray,

// 1) сортируя первую половину массива;

// 2) сортируя вторую половину массива;

// 3) объединяя две упорядоченные половины массива.

If (first < last)

mid = (first + last)/2 // Определяем середину

// Сортируем отрезок theArray mergesort(theArray, first, mid)

// Сортируем отрезок theArray mergesort(theArray, mid + 1, last)

// Объединяем упорядоченные отрезки theArray

// и theArray

merge(theArray, first, mid, last)

} // Конец оператора if

// Если first >= last, операции завершены

Совершенно ясно, что основные операции этого алгоритма выполняются на этапе слияния, и все же, почему в результате возникает упорядоченный массив? Рекурсивные вызовы продолжают разделять части массива пополам, пока в них не останется только по одному элементу. Очевидно, что массив, состоящий из одного элемента, является упорядоченным. Затем алгоритм объединяет фрагменты массива, пока не образуется один упорядоченный массив. Рекурсивные вызовы функции mergesort и результаты слияний проиллюстрированы на рис. 9.9 на примере массива, состоящего из шести целых чисел.

Рис. 9.9. Сортировка методом слияния массива, состоящего из шести целых чисел

Ниже приведена функция на языке C++, реализующая алгоритм сортировки методом слияний. Для того чтобы упорядочить массив theArray, состоящий из n элементов, выполняется рекурсивный вызов mergesort (theArray, 0, n-1).

const int MAX_SIZE = максимальное-количество-элементов-массива,-

void merge(DataType theArray, int first, int mid, int last)

// Объединяет два упорядоченных отрезка theArray и

//theArray в один упорядоченный массив.

// Предусловие: first <= mid <= last. Оба подмассива

// theArray и theArray упорядочены

// по возрастанию.

// Постусловие: отрезок theArray упорядочен.

// Замечание о реализации: функция выполняет слияние двух

// подмассивов во временный массив, а затем копирует его

// содержимое в исходный массив theArray.

// _________________________________________________________

Анализ. Поскольку основные операции в этом алгоритме выполняются на этапе слияния, начнем анализ с него. На каждом шаге происходит объединение подмассивов theArray и theArray . На рис. 9.10 показан пример, в котором требуется выполнить максимальное количество сравнений. Если общее количество элементов объединяемых отрезков массива равно п, то при их слиянии потребуется выполнить п-1 сравнений. (Например, на рис. 9.10 показан массив, состоящий из шести элементов, следовательно, выполняется пять сравнений.) Кроме того, после сравнений осуществляется копировние п элементов временного массива в исходный. Таким образом, на каждом шаге слияния выполняется 3*п-1 основных операций.

В функции mergesort выполняются два рекурсивных вызова. Как показано на рис. 9.11, если исходный вызов функции mergesort принадлежит нулевому уровню, то на первом уровне возникают два рекурсивных вызова. Затем каждый из этих вызовов порождает еще два рекурсивных вызова второго уровня и т.д. Сколько уровней рекурсии возникнет? Попробуем их подсчитать.

Каждый вызов функции mergesort делит массив пополам. На первом этапе исходный массив оказывается разделенным на две части. При следующем рекурсивном вызове функции mergesort каждая из этих частей снова делится пополам, образуя четыре части исходного массива. При следующем рекурсивном вызове каждая из этих четырех частей опять делится пополам, образуя восемь частей массива и т.д. Рекурсивные вызовы продолжаются до тех пор, пока части массива не станут содержать только по одному элементу, иными словами, пока исходный массив не будет разбит на п частей, что соответствует количеству его элементов, если число п является степенью двойки (n=2 m), глубина рекурсии равна k=log 2 n Например, как показано на рис. 9.11, если исходный массив содержит восемь элементов (8=2 3), то глубина рекурсии равна 3. Если число п неявляется степенью двойки, глубина рекурсии равна 1+ log 2 n (округленное значение).

Исходный вызов функции mergesort (ypoвень 0) обращается к функции merge только один раз. Затем функция merge осуществляет слияние п элементов, выполняя 3*n-1 операций. На первом уровне рекурсии выполняются два вызова функции mergesort и, следовательно, функции merge. Каждый из этих двух вызовов приводит к слиянию n/2 элементов и требует выполнения 3*(n/2)-1 операций. Таким образом, на этом уровне выполняется 2*(3*(n/2)-1)=3*n-2 операций. На m-м уровне рекурсии выполняются 2 т вызовов функции merge. Каждый из этих вызовов приводит к слиянию п/2 т элементов, а общее количество операций равно 3*(n/2 m)-2. В целом, 2 m рекурсивных вызова функции merge порождает 3*n-2 m операций. Таким образом, на каждом уровне рекурсии выполняется О(л) операций. Поскольку количество уровней рекурсии равно log 2 n или log 2 n+l, в наихудшем и среднем вариантах функция mergesort имеет сложность O(n*log 2 n). Посмотрите на рис. 9.3 и еще раз убедитесь, что величина O(n*log 2 n) растет намного медленнее, чем величина О(п г).

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

Объединить упорядоченные подмассивы theArray и theArray

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

Разбиение, показанное на рис. 9.12, характеризуется тем, что все элементы множества Si=theArray меньше опорного элемента р, а множество S 2 = theArray состоит из элементов, больших или равных опорному. Хотя из этого свойства не следует, что массив упорядочен, из него вытекает чрезвычайно полезный факт: если массив упорядочен, элементы, стоящие на позициях от first до pivotlndex-l, остаются на своих местах, хотя их позиции относительно друг друга могут измениться. Аналогичное утверждение выполняется и для элементов, стоящих на позициях от pivotlndex+l до last. Опорный элемент в полученном упорядоченном массиве останется на своем месте.

своем месте

Такое разбиение массива определяет рекурсивный характер алгоритма. Разбиение массива относительно опорного элемента р порождает две задачи сортировки меньшего размера - сортировка левой (S 1) и правой (S 2) частей массива. Решив эти две задачи, мы получим решение исходной задачи. Иными словами, разбиение массива перед рекурсивными вызовами оставляет опорный элемент на своем месте и гарантирует, что левый и правый отрезки массива окажутся упорядоченными. Кроме того, алгоритм быстрой сортировки конечен: размеры левого и правого отрезка массива меньше размера исходного массива, причем каждый шаг рекурсии приближает нас к базису, когда массив состоит из одного элемента. Это следует из того факта, что опорный элемент р не принадлежит ни одному из массивов S l и S 2 .

Псевдокод алгоритма быстрой сортировки выглядит следующим образом.

quicksort (inout theArray .- ItemArray,

in first:integer, in last:integer) // Упорядочивает массив theArray

if (first < last)

Выбрать опорный элемент р из массива theArray Разбить массив theArray относительно

опорного элемента р // Разбиение имет вид theArray

// Упорядочиваем массив SI

quicksort(theArray, first, pivotlndex-l)

// Упорядочиваем массив S2

quicksort(theArray, pivotlndex+l, last) } // Конец оператора if // если first >= last, ничего не делаем

Как выбрать опорный элемент? Если элементы массива записаны в произвольном порядке, в качестве опорного можно выбрать любой элемент, например theArray . (Более детально процедура выбора опорного элемента будет рассмотрена позднее.) При разбиении массива опорный элемент удобно помещать в ячейку theArray , независимо от того, какой именно элемент выбран в качестве опорного.

Часть массива, в которой находятся элементы, еще не распределенные по отрезкам S1 и S 2 , называется неопределенной. Итак, рассмотрим массив, изображенный на рис. 9.14. Индексы first, lastS1, firstUnknown и last разделяют массив на три части. Отношения между опорным элементом и элементами неопределенной части theArray неизвестны.

Puc. 9.14. Инвариант алгоритма разбиения

В процессе разбиения массива должно выполняться следующее условие.

Элементы множества S1 должны быть меньше опорного элемента, а элементы множества S 2 - больше или равны ему.

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

first firstUnknown last

Puc. 9.15. Исходное состояние массива

На каждом шаге алгоритма разбиения проверяется один элемент из неопределенной части. В зависимости от его значения он помещается в множество S1 или S 2 . Таким образом, на каждом шаге размер неопределенной части уменьшается на единицу. Алгоритм останавливается, когда размер неопределенной части становится равным нулю, т.е. выполняется условие firstUnknown > last.

Рассмотрим псевдокод этого алгоритма.

partition (inout theArray:ItemArray,

in first:integer, in last:integer,

out pivotlndex:integer) // Разделяет массив theArray

// Инициализация

Выбрать опорный элемент и поменять его местами

с элементом theArray
р = theArray // p - опорный элемент

// Задаем пустые множества S1 и S 2 , а неопределенную // часть массива инициализируем отрезком

// theArray lastSl = first firstUnknown = first + 1

// Определяем множества Sj и S 2 while (firstUnknown <= last)

// Вычисляем индекс самого левого элемента // неопределенной части массива if (theArray < р)

Поместить элемент theArray в Si else

Поместить элемент theArray в S 2 } // Конец оператора while

// Ставим опорный элемент между множествами S 2 и S 2 // и запоминаем его новый индекс

Поменять местами theArray и theArray pivotlndex = lastSl

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

Поместить элемент theArray в множество S t . Множество S1 и неопределенная часть, как правило, не являются смежными. Обычно между ними располагается множество S 2 . Однако эту операциюможно выполнить более эффективно. Элемент theArray можно поменять местами с первым элементом множества S 2 , т.е. с элементом theArray , как показано на рис. 9.16. Как быть сэлементом множества S 2 , который был помещен в ячейку theArray? Если увеличить индекс firstUnknown на единицу, этот элемент становится самым правым в множестве S 2 . Таким образом, для переноса элемента theArray в массив S1 необходимо выполнить следующие шаги.

Поменять местами элементы theArray

и theArray Увеличить индекс lastSl на единицу Увеличить индекс firstUnknown на единицу

Эта стратегия остается верной, даже если множество S 2 пусто. В этом случае величина lastSl+l равна индексу firstUnknown, и элемент просто остается на своем месте.

Поместить элемент theArray в множество S 2 . Эту операцию легко выполнить. Напомним, что индекс крайнего правого элемента множества S 2 равен firstUnknown-1, т.е. множество S 2 и неизвестная часть являются смежными (рис. 9.17). Таким образом, чтобы переместить элемент theArray в множество S 2 , нужно просто увеличить индекс firstUnknown на единицу, расширяя множество S 2 вправо.Инвариант при этом не нарушается.

После переноса всех элементов из неопределенной части в множества S 1 и S 2 остается решить последнюю задачу. Нужно поместить опорный элемент между множествами S1 и S 2 . Обратите внимание, что элемент theArray явля-

Рис. 9.17. Перенос элемента theArray в множество S2 после увеличения индекса firstUnknown на единицу

ется крайним правым элементом множества S1. Если поменять его местами с опорным элементом, тот станет на правильное место. Следовательно, оператор

pivotlndex = lastSl

позволяет определить индекс опорного элемента. Этот индекс можно использовать в качестве границы между множествами Sj и 5г. Результаты трассировки алгоритма разбиения массива, состоящего из шести целых чисел, когда опорным является первый элемент, показаны на рис. 9.18.

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

Все элементы множества S 2 (theArray) меньше опорного, а все элементы множества S 2 (theArray) больше или равны опорному

Напомним, что для определения правильности алгоритма с помощью его инвариантов, необходимо выполнить четыре шага.

1. Инвариант должен быть истинным с самого начала, до выполнения цикла. В алгоритме разбиения опорным элементом является theArray , неизвестной частью- отрезок массива theArray , a множества S1 и S 2 пусты. Очевидно, что при этих условиях инвариант является истинным.

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

3. Инвариант должен определять корректность алгоритма. Иными словами, из истинности инварианта должна следовать корректность алгоритма. Выполнение алгоритма разбиения прекращается, когда неопределенная область становится пустой. В этом случае каждый элемент отрезка theArray должен принадлежать либо множеству S1, либо множеству S2. В любом случае из корректности инварианта следует, что
алгоритм достиг своей цели.

4. Цикл должен быть конечным. Иными словами, нужно показать, что выполнение цикла завершится после конечного числа итераций. В алгоритме разбиения размер неопределенной части на каждой итерации уменьшается на единицу. Следовательно, после выполнения конечного количества итераций неопределенная часть становится пустой, и цикл завершается.

Рис. 9.18. Первое разбиение массива, когда опорным является первый элемент

Перед вызовом функции quicksort выполняется разбиение массива на части S1 и S2. Затем алгоритм упорядочивает отрезки S1 и S2 независимо друг от друга, поскольку любой элемент отрезка S1 находится левее любого элемента отрезка S2. В функции mergeSort, наоборот, перед рекурсивными вызовами никакая работа не выполняется. Алгоритм упорядочивает каждую из частей массива, постоянно учитывая отношения между элементами обеих частей. По этой причине алгоритм должен объединять две половины массива после выполнения рекурсивных вызовов.

Анализ. Основная работа в алгоритме quicksort выполняется на этапе разбиения массива. Анализируя каждый элемент, принадлежащий неопределенной части, необходимо сравнивать элемент theArray с опорным и помещать его либо в отрезок S1, либо в отрезок S2. Один из отрезков S1 или S2 может быть пустым; например, если опорным элементом является наименьший элемент отрезка, множество S1 останется пустым. Это происходит в наихудшем случае, поскольку размер отрезка S2 при каждом вызове функции quicksort уменьшается только на единицу. Таким образом, в этой ситуации будет выполнено максимальное количество рекурсивных вызовов функции quicksort.

При следующем рекурсивном вызове функции quicksort функция partition просмотрит п-1 элемент. Чтобы распределить их по отрезкам, понадобится п-2 сравнений. Поскольку размер отрезка, рассматриваемого функцией quicksort, на каждом уровне рекурсии уменьшается только на единицу, возникнет п-1 уровней рекурсии. Следовательно, функция quicksort выполняет 1 + 2 + ...+ (n-1) = n * (n-1)/2 сравнений. Напомним, однако, что при переносе элемента в множество S2 выполнять перестановку элементов не обязательно. Для этого достаточно лишь изменить индекс firstUnknown.

Аналогично, если множество S2 при каждом рекурсивном вызове остается пустым, потребуется n * (n-1)/2 сравнений. Кроме того, в этом случае для переноса каждого элемента из неизвестной части в множество S1 придется выполнять перестановку элементов. Таким образом, понадобится * (n-1)/2 перестановок. (Напомним, что каждая перестановка выполняется с помощью трех операций присваивания.) Итак, в худшем случае сложность алгоритма quicksort равна О(n2).

Для контраста на рис. 9.20 продемонстрирован пример, когда множества S1 и S2 состоят из одинакового количества элементов. В среднем случае, когда множества S1 и S2 состоят из одинакового - или приблизительно одинакового - количества элементов, записанных в произвольном порядке, рекурсивных вызовов функции quicksort потребуется меньше. Как и при анализе алгоритма mergeSort, легко показать, что глубина рекурсии в алгоритме quicksort равна log2n или log2n+l. При каждом вызове функции quicksort выполняется m сравнений и не больше, чем m перестановок, где m - количество элементов в подмассиве, подлежащем сортировке.

Быстрая сортировка: наихудший вариант О(п 2), средний вариант O(n*logn).

Таким образом, с большими массивами алгоритм

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

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

Значительное различие между оценками сложности в среднем и наихудшем вариантах выделяет алгоритм быстрой сортировки среди остальных алгоритмов, рассмотренных в данной главе. Если порядок записи элементов в исходном массиве является "случайным", алгоритм quicksort работает по крайней мере не хуже любого другого алгоритма, использующего сравнения элементов. Если исходный массив совершенно не упорядочен, алгоритм quicksort работает лучше всех.

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

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

Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.

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

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

В этой статье приведены примеры реализации стандартных алгоритмов сортировки.

Сортировка выбором (Selection sort)

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

Код C++

void SortAlgo::selectionSort(int data, int lenD) { int j = 0; int tmp = 0; for (int i=0; idata[k]){ j = k; } } tmp = data[i]; data[i] = data[j]; data[j] = tmp; } }

Пузырьковая сортировка (Bubble sort)

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

Код C++

void SortAlgo::bubbleSort(int data, int lenD) { int tmp = 0; for (int i = 0;i=(i+1);j--){ if (data[j]

Сортировка вставками (Insertion sort)

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

На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной области сокращается на 1.

Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в правильное положение в упорядоченной области. Это сделано путем сдвига всех элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i] вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i].

Код C++

void SortAlgo::insertionSort(int data, int lenD) { int key = 0; int i = 0; for (int j = 1;j=0 && data[i]>key){ data = data[i]; i = i-1; data=key; } } }

Сортировка слиянием (Merge sort)

Код C++

void SortAlgo::mergeSort(int data, int lenD) { if (lenD>1){ int middle = lenD/2; int rem = lenD-middle; int * L = new int ; int * R = new int ; for (int i=0;i

Быстрая сортировка (Quick sort)

Быстрая сортировка использует алгоритм "разделяй и властвуй". Она начинается с разбиения исходного массива на две области. Эти части находятся слева и справа от отмеченного элемента, называемого опорным. В конце процесса одна часть будет содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше опорного.

Код C++

void SortAlgo::quickSort(int * data, int const len) { int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1){ int * L = new int ; int * R = new int ; pivot = data; for (i=0;i

Кто-то сказал однажды, что

...any scientist who couldn"t explain to an eight-year-old what he was doing was a charlatan.

Оказывается, это был Курт Воннегут.

Я не стремился доказать это высказывание. Я стремился опровергнуть свою тупость.

Допустим у нас есть два массива чисел, отсортированных по возрастанию.

Int a1 = new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2 = new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000};
Необходимо слить их в один упорядоченный массив.

Int a3 = new int;
Это задача для сортировки слиянием.

Что это такое? В интернете есть ответ, есть описание алгоритма, но я его не понял с одного присеста и решил разобраться сам. Для этого необходимо понять базовый принцип алгоритма, чтобы можно было по памяти воссоздать алгоритм применительно к своей задаче.

Начали за здравие

Давайте пойдем постепенно и воспользуемся тем, что лежит на поверхности: будем брать поочередно по одному элементу из каждого массива, сравнивать их и «сливать» в один массив. Меньший элемент будем ставить первым, больший – вторым. Тогда после первого прохода все нормально:

10, 21
А после второго прохода уже не очень:

10, 21, 11, 23
Понятно, что надо сравнивать элементы еще и с уже добавленными.

Начнем еще раз

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

После второго прохода в буфере будет 21, 23 и 11. Что с ними делать – непонятно, сравнить более двух элементов можно, но уже не так просто.

Давайте тогда условимся, что будем брать в этот буфер по одному элементу от каждого массива. Так как проще сравнивать два элемента между собой, да и вообще у нас две сущности – два массива. Тогда после второго прохода в буфере будет 21 и 11, потому что «представитель» первого массива в буфере уже есть – это 21. Сравниваем их и меньший отправляем в результирующий массив. Тогда после второго прохода будем иметь в результирующем массиве:

10, 11
А в буфере – 21.

На третьем проходе берем в буфер из второго массива 41, потому что «представитель» первого массива в буфере так и остался. Сравниваем 21 и 41, и наконец-то убираем из буфера 21.

После третьего прохода будем иметь в результирующем массиве:

10, 11, 21
На четвертом проходе будем сравнивать два значения из буфера - 41 и 23. В результирующем массиве будет:

10, 11, 21, 23
То есть только сейчас – на четвертом, а не на втором проходе - результат получился правильным. Получается, что в цикле надо помнить текущий индекс для каждого массива, а сам цикл может быть длиной равной сумме длин массивов.

Подходим к концу, но вдруг

Что будем делать, когда результирующий массив будет состоять из:

10, 11, 21, 23, 24, 40, 41, 50, 65, 75, 76, 78, 77, 86, 98, 101, 190, 900, 1100, 1200, 2100, 2200, 2300, 2400, 2500,
В буфере будет 3000 из второго массива, а в первом - все элементы кончатся? Так как массивы у нас отсортированы, то просто берем 3000 из буфера и оставшееся 5000. То есть нужно для каждого индекса выполнять проверку – не превысили ли мы количество элементов в каждом из массивов.

Усложним задачу

А если у нас не отсортированные массивы? Обычно задача сводится к тому, чтобы отсортировать один массив. Тогда сортировка слиянием тоже может быть использована.

Пусть первый массив (для примера возьмем из него несколько элементов) имеет следующее расположение элементов:

2100, 23, 40, 24, 2, 1.
Будем его сортировать. Раз легче сравнивать по два элемента, то разобьем поровну массив на два:

2150, 23, 40
и
24, 2, 1.
Получится по три элемента. Много! Разобьем поровну каждый массив, получится четыре массива:

2100, 23 40 24, 2 1
Отсортируем теперь каждый из массивов простым сравнением первого и второго элементов (там где они есть):

23, 2100 40 2, 24 1
И будем сливать обратно по предыдущему алгоритму – через буфер. После первого слияния получим два массива:

23, 40, 2100 1, 2, 24
И снова сливаем – уже в один массив:

1, 2, 23, 24, 40, 2100
Так мы отсортировали слиянием массив.

В сухом остатке

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

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

Выразим в коде (Java)

Пример сортировки по возрастанию двух отсортированных массивов:

Int a1 = new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2 = new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3 = new int; int i=0, j=0; for (int k=0; k a1.length-1) { int a = a2[j]; a3[k] = a; j++; } else if (j > a2.length-1) { int a = a1[i]; a3[k] = a; i++; } else if (a1[i] < a2[j]) { int a = a1[i]; a3[k] = a; i++; } else { int b = a2[j]; a3[k] = b; j++; } }
Здесь:

A1 и a2 – массивы, которые надо слить;
a3 – результирующий массив;
i и j – индексы для массивов a1 и a2 соответственно, которые указывают на текущие элементы на каждом шаге и образуют тот самый буфер.

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

Функция сортировки слиянием

Оформим приведенный код как рекурсивную функцию, которая станет разделять массивы до тех пор, пока это возможно, с параметрами, соответствующими целому массиву при первом вызове, его половинам при втором и третьем вызовах и т. д.

Private void SortUnsorted(int a, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; SortUnsorted(a, lo, mid); SortUnsorted(a, mid + 1, hi); int buf = Arrays.copyOf(a, a.length); for (int k = lo; k <= hi; k++) buf[k] = a[k]; int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = buf[j]; j++; } else if (j > hi) { a[k] = buf[i]; i++; } else if (buf[j] < buf[i]) { a[k] = buf[j]; j++; } else { a[k] = buf[i]; i++; } } }
Здесь:

A – массив;
lo – позиция первого элемента в массиве (для первой итерации = 0);
hi – позиция последнего элемента в массиве (для первой итерации = a.length - 1).

Алгоритмы ,

Программирование

Кто-то сказал однажды, что

...any scientist who couldn"t explain to an eight-year-old what he was doing was a charlatan.

Оказывается, это был Курт Воннегут.

Я не стремился доказать это высказывание. Я стремился опровергнуть свою тупость.

Допустим у нас есть два массива чисел, отсортированных по возрастанию.

Int a3 = new int;
Это задача для сортировки слиянием.

Начали за здравие

10, 21
А после второго прохода уже не очень:

10, 21, 11, 23
Понятно, что надо сравнивать элементы еще и с уже добавленными.

Начнем еще раз

10, 11
А в буфере – 21.

После третьего прохода будем иметь в результирующем массиве:

10, 11, 21
На четвертом проходе будем сравнивать два значения из буфера - 41 и 23. В результирующем массиве будет:

Подходим к концу, но вдруг

Что будем делать, когда результирующий массив будет состоять из:

Усложним задачу

2100, 23, 40, 24, 2, 1.
Будем его сортировать. Раз легче сравнивать по два элемента, то разобьем поровну массив на два:

2150, 23, 40
и
24, 2, 1.
Получится по три элемента. Много! Разобьем поровну каждый массив, получится четыре массива:

23, 40, 2100 1, 2, 24
И снова сливаем – уже в один массив:

1, 2, 23, 24, 40, 2100
Так мы отсортировали слиянием массив.

В сухом остатке

Выразим в коде (Java)

Пример сортировки по возрастанию двух отсортированных массивов:

Функция сортировки слиянием

Для упрощения кода и улучшения читаемости мы введем метод Swap , который будет менять местами значения в массиве по индексу.

Void Swap(T items, int left, int right) { if (left != right) { T temp = items; items = items; items = temp; } }

Пузырьковая сортировка

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

Например, у нас есть массив целых чисел:

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

Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так:

Поскольку был совершен по крайней мере один обмен значений, нам нужно пройти по массиву еще раз. В результате этого прохода мы перемещаем на место число 6.

И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз.

При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу.

Public void Sort(T items) { bool swapped; do { swapped = false; for (int i = 1; i < items.Length; i++) { if (items.CompareTo(items[i]) > 0) { Swap(items, i - 1, i); swapped = true; } } } while (swapped != false); }

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

Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее - нет.

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

Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным.

Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать:

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

На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно.

Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex . Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки.

Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так:

Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки.

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

Public void Sort(T items) { int sortedRangeEndIndex = 1; while (sortedRangeEndIndex < items.Length) { if (items.CompareTo(items) < 0) { int insertIndex = FindInsertionIndex(items, items); Insert(items, insertIndex, sortedRangeEndIndex); } sortedRangeEndIndex++; } } private int FindInsertionIndex(T items, T valueToInsert) { for (int index = 0; index < items.Length; index++) { if (items.CompareTo(valueToInsert) > 0) { return index; } } throw new InvalidOperationException("The insertion index was not found"); } private void Insert(T itemArray, int indexInsertingAt, int indexInsertingFrom) { // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // // Действия: // 1: Сохранить текущий индекс в temp // 2: Заменить indexInsertingAt на indexInsertingFrom // 3: Заменить indexInsertingAt на indexInsertingFrom в позиции +1 // Сдвинуть элементы влево на один. // 4: Записать temp на позицию в массиве + 1. // Шаг 1. T temp = itemArray; // Шаг 2. itemArray = itemArray; // Шаг 3. for (int current = indexInsertingFrom; current > indexInsertingAt; current--) { itemArray = itemArray; } // Шаг 4. itemArray = temp; }

Сортировка выбором

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

Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве.

При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало.

Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение - 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход - на этот раз по индексам от 1 до n — 1.

На втором проходе мы определяем, что наименьшее значение - 4. Мы меняем его местами со вторым элементом, семеркой, после чего 4 встает на свою правильную позицию.

Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован.

После еще двух проходов алгоритм завершает свою работу:

Public void Sort(T items) { int sortedRangeEnd = 0; while (sortedRangeEnd < items.Length) { int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd); Swap(items, sortedRangeEnd, nextIndex); sortedRangeEnd++; } } private int FindIndexOfSmallestFromIndex(T items, int sortedRangeEnd) { T currentSmallest = items; int currentSmallestIndex = sortedRangeEnd; for (int i = sortedRangeEnd + 1; i < items.Length; i++) { if (currentSmallest.CompareTo(items[i]) > 0) { currentSmallest = items[i]; currentSmallestIndex = i; } } return currentSmallestIndex; }

Сортировка слиянием

Разделяй и властвуй

До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй» (divide and conquer) .

Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще. Мы пользуемся ими каждый день. К примеру, поиск в телефонной книге - один из примеров такого алгоритма.

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

Насколько эффективны эти алгоритмы?

Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске.

Сортировка слиянием

При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке.

Давайте посмотрим на такой массив:

Разделим его пополам:

И будем делить каждую часть пополам, пока не останутся части с одним элементом:

Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке.

Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.

Для работы алгоритма мы должны реализовать следующие операции:

Операцию для рекурсивного разделения массива на группы (метод Sort).
Слияние в правильном порядке (метод Merge).

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

Public void Sort(T items) { if (items.Length <= 1) { return; } int leftSize = items.Length / 2; int rightSize = items.Length - leftSize; T left = new T; T right = new T; Array.Copy(items, 0, left, 0, leftSize); Array.Copy(items, leftSize, right, 0, rightSize); Sort(left); Sort(right); Merge(items, left, right); } private void Merge(T items, T left, T right) { int leftIndex = 0; int rightIndex = 0; int targetIndex = 0; int remaining = left.Length + right.Length; while(remaining > 0) { if (leftIndex >= left.Length) { items = right; } else if (rightIndex >= right.Length) { items = left; } else if (left.CompareTo(right) < 0) { items = left; } else { items = right; } targetIndex++; remaining--; } }

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

Быстрая сортировка - это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги:

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

Давайте посмотрим на работу алгоритма на следующем массиве:

Сначала мы случайным образом выбираем ключевой элемент:

Int pivotIndex = _pivotRng.Next(left, right);

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

Перемещение значений осуществляется методом partition .

На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива.

У нас осталось одно неотсортированное значение, а, поскольку мы знаем, что все остальное уже отсортировано, алгоритм завершает работу.

Random _pivotRng = new Random(); public void Sort(T items) { quicksort(items, 0, items.Length - 1); } private void quicksort(T items, int left, int right) { if (left < right) { int pivotIndex = _pivotRng.Next(left, right); int newPivot = partition(items, left, right, pivotIndex); quicksort(items, left, newPivot - 1); quicksort(items, newPivot + 1, right); } } private int partition(T items, int left, int right, int pivotIndex) { T pivotValue = items; Swap(items, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) { if (items[i].CompareTo(pivotValue) < 0) { Swap(items, i, storeIndex); storeIndex += 1; } } Swap(items, storeIndex, right); return storeIndex; }

Заключение

На этом мы заканчиваем наш цикл статей по алгоритмам и структурам данных для начинающих. За это время мы рассмотрели связные списки, динамические массивы, двоичное дерево поиска и множества с примерами кода на C#.