Introsort — Сложность алгоритма: o(n log n), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).
Patience sorting — Сложность алгоритма: O(n log n + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность
Stooge sort — рекурсивный алгоритм сортировки с временной сложностью .
Поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.
Цифровая сортировка — то же, что и Поразрядная сортировка.
Непрактичные алгоритмы сортировки
Bogosort — O(n·n!) в среднем. Произвольно перемешать массив, проверить порядок.
Сортировка перестановкой — O(n·n!) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.
Глупая сортировка (Stupid sort) — O(n3); рекурсивная версия требует дополнительно O(n2) памяти
Bead Sort — O(n) or O(√n), требуется специализированное аппаратное обеспечение
Блинная сортировка (Pancake sorting) — O(n), требуется специализированное аппаратное обеспечение
Алгоритмы, не основанные на сравнениях:
Блочная сортировка (Корзинная сортировка, Bucket sort)
Лексикографическая или поразрядная сортировка (Radix sort)
Сортировка подсчётом (Counting sort)
Прочие алгоритмы сортировки
Топологическая сортировка
Внешняя сортировка.
Список алгоритмов сортировки.
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort)
Простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, сортировка Шелла и быстрая сортировка.
Содержание
1 Алгоритм
2 Псевдокод
3 Пример работы алгоритма
4 Литература
5 Ссылки
Алгоритм
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Псевдокод
Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n-1], A[n]
t := истина
цикл пока t:
t := ложь
цикл для j = 1, 2, ..., n − 1:
если A[j] > A[j+1], то:
обменять местами элементы A[j] и A[j+1]
t := истина
Булевая переменная t используется для того, чтобы определить, был ли произведён хотя бы один обмен на очередной итерации внешнего цикла. Алгоритм останавливается, когда таких обменов не было.
Можно показать, что для сортировки требуется сделать не более n − 1 итераций внешнего цикла, поэтому в некоторых реализациях внешний цикл всегда выполняется ровно n − 1 или n раз, и не отслеживается, были ли обмены или нет на каждой итерации.
Алгоритм можно немного улучшить следующими способами:
Внутренний цикл можно выполнять для j = 1,2,...,n − i, где i — номер итерации внешнего цикла (нумерация с единицы), так как на i-й итерации последние i элементов массива уже будут правильно упорядочены.
Внутренний цикл можно модифицировать так, чтобы он поочерёдно просматривал массив то с начала, то с конца. Модифицированный таким образом алгоритм называется сортировкой перемешиванием или шейкерной сортировкой.
Ниже написан псевдокод сортировки. Это оптимизированная версия с использованием переменной j, чтобы разрешить прыжок вперёд туда, где он остановился до движения влево, избегая лишние итерации и сравнения:
gnomeSort(a[0..size - 1])
i = 1;
j = 2;
while i < size
if a[i - 1] <= a[i] //для сортировки по убыванию поменяйте знак сравнения на >=
i = j;
j = j + 1;
else
swap a[i - 1] and a[i]
i = i - 1;
if i == 0
i = j;
j = j + 1;
Сортировка вставками — простой алгоритм сортировки.
Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:
эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
эффективен на наборах данных, которые уже частично отсортированы;
это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
может сортировать список по мере его получения;
не требует временной памяти, даже под стек.
Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n]
for i = 2, 3, ..., n:
key := A[i]
j := i - 1
while j > 0 and A[j] > key:
A[j + 1] := A[j]
j := j - 1
A[j + 1] := key
Реализация на С++[2]
void insertionSort(int arr[], int length) {
int i, j, tmp;
for (i = 1; i < length; i++) {
j = i;
while (j > 0 && arr[j - 1] > arr[j]) {
tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
j--;
}
}
}
4.Бинарный поиск в сортированном массиве. «Быстрая» сортировка.
Структурные типы и структуры данных
Большинство императивных языков программирования, в частности язык Паскаль, поддерживают парадигму «структурного программирования». В частности это проявляется в том, понятие «структура» входит в программу не только на уровне общего ее построения, но и предусматривает структурирование самой логики программы и структурирование используемых данных.
Принцип «структурирования данных» воплощается в типизации языка, т.е. наделении языка программирования строгой системой предопределенных типов, комбинируя которые программист может создавать свои собственные структурные типы, причем уже не только простые, но и представляющие собой сложные конструкции – структуры данных.
Возможность создания новых типов данных очень важна, так как моделирование всевозможных реальных процессов является одной из основных областей применения ЭВМ. Моделирование приводило к абстракции, т.е. к упрощенному (или обобщенному) представлению объектов, их свойств и отношений в зависимости от поставленной задачи. Некоторые такие абстрактные объекты из-за своих полезных качеств стали необычайно «популярны». Они получили точную спецификацию и с тех пор стали называться абстрактными типами данных (или АТД). Наиболее популярные АТД – стеки, очереди, деки, списки, деревья, упорядоченные множества.
Массив – это одно- (или многомерная) таблица данных одного типа. Каждая ячейка таблицы имеет свой индекс (или набор индексов в случае многомерного массива). Массив называют структурой данных со случайным доступом, поскольку к любому элементу массива можно обратиться, просто указав его индексы, т.е. все элементы одинаково доступны в любой момент времени. Основные характеристики массива - общий тип его элементов и их количество. Количество элементов массива определяется количеством индексов и диапазоном их изменения. Главным недостатком этой структуры является то, что в некоторых системах программирования под переменную выделяется ограниченное количество памяти, что не позволяет использовать массивы больших размеров, во-вторых, потому что нет возможности изменять размер массива.
Записи. Запись – связанная структура, состоящая из нескольких элементов (полей) разных (можно и одинаковых) типов. По сути, запись очень похожа на одномерный массив, но с элементами разных типов, кроме того, доступ к конкретному полю записи осуществляется уже не через индекс, а указанием идентификатора (имени) этого поля.
Файлы. Файл – динамическая структура данных, размер которой может меняться в процессе выполнения над ним каких-либо действий (размер файла может быть равен нулю, что соответствует пустому файлу). Файл – структура, состоящая из последовательности компонент одного типа. В каждый момент времени может быть доступен только один элемент файла. Существует несколько видов файлов. Текстовые файлы трактуются как последовательности строк переменной длины. В конце каждой строки ставится специальный признак конца строки EOLN. Типизированные файлы – последовательности компонент определенного типа. Длина любого элемента типизированного файла строго постоянна, что дает возможность организовать прямой доступ к каждому компоненту. Нетипизированные файлы отличаются тем, что для них не указан тип компонент. Такой подход делает нетипизированные файловые переменные совместимыми с файлами любых типов, а также позволяет организовать высокоскоростной обмен данными между оперативной и внешней памятью.
Динамические структуры. Работа с динамической памятью. Динамический объект представляет собой область памяти без идентификатора. Для обращения к этой области заводится специальная ссылочная переменная, которая описывается в программе. Элементами множества значений ссылочного типа являются значения адресов оперативной памяти. Чаще всего динамические структуры состоят из объектов, являющихся записями из нескольких полей, одна или несколько из которых являются ссылками на такой же объект. Таким образом можно составлять цепочки или более сложные структуры ссылающихся друг на друга объектов. Размер таких структур ограничивается только объемом свободной памяти и может легко меняться при удалении и создании объектов, что и определило основную область их применения – моделирование нелинейных последовательных структур данных (например, деревьев). Однако, несмотря на кажущееся отсутствие недостатков, динамические структуры тоже имеют свои минусы. Главный из них – отсутствие наглядности программы – вызывает трудности при создании особо крупных структур.
Представление абстрактных типов данных (АТД). Моделирование абстрактных типов данных на конкретных структурах данных языка программирования не является однозначным. Практически любой АТД может быть эффективным образом представлен как на массиве, так и на файле или на динамической структуре, но чаще всего конкретное представление диктуется особенностью доступа к элементам рассматриваемого абстрактного типа.
Стек. Стек – структура данных, представляющая собой последовательность элементов. Добавление и удаление элементов происходит только с одного конца последовательности, т.е. при изменении структуры предыдущая последовательность остается неизменной.
Это значит, что по идее идеальной структурой представления для стека должен быть файл. Действительно, добавление элементов происходит только в конец файла, однако при удалении последнего элемента придется два раза переписывать весь файл, причем с подсчетом элементов. Это главный недостаток файла – для удаления компоненты требуется слишком много действий. С другой стороны время удаления элементов из файла не зависит ни от положения этого элемента в файле, ни от количества удаляемых элементов – это плюс!
Реализация стека с помощью массива позволяет уравнять время выполнения действий по добавлению и удалению элемента. Нужно всего лишь хранить в отдельной переменной длину последовательности и увеличивать ее или уменьшать соответственно при добавлении и удалении. Единственный недостаток такого представления – недостаток самого массива – ограниченный размер, приводящий к переполнению стека.
Использование динамических структур полностью решает эту проблему. В этом случае при добавлении и удалении элемента модифицируется только ссылка на начало цепочки динамических объектов, что снижает до минимума количество используемых для действия операторов. При этом размер стека почти неограничен.
Очередь, дек. Очередь – структура данных, как и стек представляющая собой последовательность элементов. Добавление элементов происходит на одном конце последовательности, удаление – на другом. Дек – двусторонняя очередь, т.е. и добавление и удаление осуществляется с обеих сторон.
Представление на файле этих АТД имеет такой же характер и «преимущества» как и у стека, т.е. переписывание файла происходит во всех случаях кроме добавления компоненты в его конец.
Представление очередей и деков на массиве отличается тем, что последовательность элементов может «перемещаться» по массиву, следовательно, чтобы последовательность не выскочила за границы, нужно границы соединить вместе (зациклить). Проблемы все те же – возможность переполнения.
Реализация на динамической структуре использует ту же особенность (цикличность) и лучше всего представляется в виде кольцевого двунаправленного списка.
Линейный список. Линейный список – одна из тех структур данных, которая если не приравнивается, то ассоциируется с динамическими структурами. Он представляет собой упорядоченное множество (возможно пустое), в котором добавление и удаление элементов может происходить в любом месте. Элементы списков чаще всего представляют в виде записей, состоящих из поля-информации и одного или двух полей-ссылок на другие элементы списка. Списки имеют последовательную структуру, т.е. для того чтобы перейти к какому-либо элементу, нужно пройти все элементы, предшествующие искомому. Причем если каждый элемент имеет ссылку только на следующий за ним элемент, то каждый такой проход нужно начинать с «головы» списка. Этот недостаток устраняется либо зацикливанием списка (ссылка последнего элемента указывает на первый) – в этом случае вообще теряются понятия начала и конца списка – либо использованием второй ссылки (на предыдущий элемент), чтобы можно было перемещаться в обе стороны.
При моделировании списка с помощь массива элементом списка будет запись, состоящая из поля информационной части и поля, хранящего индекс следующего элемента в массиве (аналог ссылки). Для того чтобы смоделировать «кучу» свободной памяти, из которой берется память под новые объекты, можно создаеть список свободных элементов.
Деревья. Дерево – множество, состоящее из элемента, называемого корнем, и конечного (возможно пустого) множества деревьев, называемых поддеревьями данного дерева. Дерево, так же как и список, реализуется прежде всего на динамических структурах, т.е. узел дерева содержит два поля-ссылки – на левое и правое поддерево для двоичного дерева и на брата и старшего сына для дерева общего вида. Дерево уже не является линейной структурой, поэтому представление деревьев на последовательной памяти (файлах) представляет собой определенную проблему. Однако все данные хранятся во внешней памяти в виде файлов, поэтому решение этой проблемы необходимо. Тем не менее, сразу стоит оговориться, что это представление не будет в полной мере реализацией АТД дерева на структуре данных файл, поскольку требуется лишь создать обратимое отображение дерева в файл – никаких операций с файлом-деревом совершаться не будет. Создадим новый тип узла дерева (он станет компонентом файла) – запись информационного поля и поля, хранящего число поддеревьев данного узла. В файл будем последовательно записывать каждый узел так, чтобы поддеревья записывались после своего корня. Обратная операция производится с использованием рекурсии. Читаем из файла узел дерева, создаем его и ссылки на его поддеревья (столько, сколько указано в соответствующем поле). Затем для всех указанных поддеревьев повторяем ту же процедуру.
Множества и деревья. Бинарное дерево называется упорядоченным, если для каждого его узла, имеющего поддеревья, корень больше левого поддерева и меньше правого. Используя упорядоченные бинарные деревья, можно реализовать математическое множество данных, для которого существует отношение порядка. При добавлении элемента нужно сохранить свойство упорядоченности, поэтому у добавляемого элемента существует единственное место в дереве (конечно, если такой элемент еще не присутствует в дереве). Проверка наличия элемента в дереве осуществляется тем же способом – переход от узла к узлу происходит по принципу максимального приближения к искомому значению. Если на том месте, где должен находиться искомый элемент, отсутствует поддерево, значит можно утверждать, что такого элемента нет во множестве.
Базовые алгоритмы обработки данных.
Базовые алгоритмы обработки данных являются результатом исследований и разработок, проводившихся на протяжении десятков лет. Но они, как и прежде, продолжают играть важную роль во все расширяющемся применении вычислительных процессов.
К базовым алгоритмам императивного программирования можно отнести:
Алгоритмы работы со структурами данных. Они определяют базовые принципы и методологию, используемые для реализации, анализа и сравнения алгоритмов. Позволяют получить представление о методах представления данных. К таким структурам относятся связные списки и строки, деревья, абстрактные типы данных, такие как стеки и очереди.
Алгоритмы сортировки, предназначенные для упорядочения массивов и файлов, имеют особую важность. С алгоритмами сортировки связаны, в частности, очереди по приоритету, задачи выбора и слияния.
Алгоритмы поиска, предназначенные для поиска конкретных элементов в больших коллекциях элементов. К ним относятся основные и расширенные методы поиска с использованием деревьев и преобразований цифровых ключей, в том числе деревья цифрового поиска, сбалансированные деревья, хеширование, а также методы, которые подходят для работы с очень крупными файлами.
Алгоритмы на графах полезны при решении ряда сложных и важных задач. Общая стратегия поиска на графах разрабатывается и применяется к фундаментальным задачам связности, в том числе к задаче отыскания кратчайшего пути, построения минимального остовного дерева, к задаче о потоках в сетях и задаче о паросочетаниях. Унифицированный подход к этим алгоритмам показывает, что в их основе лежит одна и та же процедура, и что эта процедура базируется на основном абстрактном типе данных очереди по приоритету.
Алгоритмы обработки строк включают ряд методов обработки (длинных) последователей символов. Поиск в строке приводит к сопоставлению с эталоном, что в свою очередь ведет к синтаксическому анализу. К этому же классу задач можно отнести и технологии сжатия файлов.
Геометрические алгоритмы – это методы решения задач с использованием точек и линий (и других простых геометрических объектов), которые вошли в употребление достаточно недавно. К ним относятся алгоритмы построения выпуклых оболочек, заданных набором точек, определения пересечений геометрических объектов, решения задач отыскания ближайших точек и алгоритма многомерного поиска. Многие из этих методов дополняют простые методы сортировки и поиска.
Сортировка
При рассмотрении задачи сортировки рассматривают методы сортировки файлов элементов, обладающих ключами. Цель сортировки – в переупорядочении элементов таким образом, чтобы ключи следовали в соответствии с четко определенными правилами (обычно это цифровой или алфавитный порядок).
Если сортируемый файл целиком помещается в памяти, то используемый метод сортировки называется внутренним (internal). Сортировка файлов на внешних носителях называется внешней (external). Основное различие между ними состоит в том, что при внутренней сортировке доступ к любому элементу файла не предоставляет трудностей, в то время как в условиях внешней сортировки возможен только последовательный доступ к элементу или, по крайней мере, доступ к большим блокам элементов.
На ряду с сортировкой массивов большой интерес представляет изучение методов сортировки связных списков (динамических структур). Однако большинство классических методов сортировки массивов обладают столь высокой степенью абстракции, что могут без труда быть применены к сортировке связных списков.
Можно выделить пять типов алгоритмов сортировки:
Обменом – выполняются проходы по файлу с обменом местами элементов, до тех пор, пока файл не будет окончательно отсортирован.
Вставками – отдельно анализируется каждый конкретный элемент, который затем помещается на надлежащее ему место среди других, уже отсортированных элементов
Выбором – сначала отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сортируемом массиве и т.д.
Слиянием – сортируемый файл, расположенный во внешней памяти, разбивается на части, которые могут быть считаны в память, отсортированы каким-либо методом и записаны в отдельные временные файлы. Затем отсортированные временные файлы сливаются попарно с сохранением порядка сортировки. И так до тех пор, пока все временные файлы не будут объединены в один отсортированный файл.
сортировка деревом – сортируемые элементы добавляются в бинарное дерево. Отсортированный массив формируется путем концевого обхода построенного дерева.
Основной характеристикой алгоритма сортировки является время, затраченное на его выполнение. Так для массива из N элементов:
Сортировка выбором производит в среднем N^2 / 2 операций сравнения и N операций обмена
Сортировка вставками – в среднем N^2 / 4 сравнений и N^2 / 4 операций полуобмена (перемещений) и в два раза больше в наихудшем случае
Сортировка обменом (метод пузырька) – N^2 / 2 операций сравнения и N^2 / 2 обменов как в среднем так и наихудшем случае
Сортировка деревом – N * log (N) операций сравнения и N операций вставки
Второй по важности фактор в алгоритмах сортировки – объем используемой дополнительной памяти. По существу, все методы можно разбить на три группы:
Те, которые выполняют сортировку на месте и не нуждаются в дополнительной памяти, за исключением, возможно, стека или таблицы
Те, которые используют представление в виде связного списка для размещения указателей или индексов
Те, которые требуют дополнительной памяти для размещения еще одной копии сортируемого массива
Поиск
Поиск – получение конкретного фрагмента или фрагментов информации из больших объемов ранее сохраненных данных. Как и с случае алгоритмов сортировки, мы работаем с данными, разделенными на записи (элементы), каждая из которых имеет ключ, используемый при поиске. Цель поиска – отыскание элементов с ключами, значения которых соответствуют ключу поиска.
Структуру данных, в которой проводится поиск, можно рассматривать как таблицу символов (таблицу имен или таблицу идентификаторов) – структуру, содержащую ключи и данные, и допускающую две операции – вставку нового элемента и возврат элемента с заданным ключом.
Иногда таблицы символов называют словарями по аналогии с хорошо известной системой упорядочивания слов в алфавитном порядке: слово – ключ, его толкование – данные.
Основные методы поиска:
Поиск с использованием индексации по ключам. Пусть ключи – различные небольшие числа. В этом случае простейший алгоритм поиска предполагает хранение элементов в массиве St, проиндексированном значениями ключей. Изначально массив проинициализирован значениями Null. Затем можно вставить элемент со значением K записав его в St[K] или найти его, обратившись к St[K]. Удалить элемент K можно записав в St[K] значение Null.
Последовательный поиск – в случае, когда диапазон ключей слишком велик, простейший способ реализации таблицы символов – упорядоченное хранение в последовательном массиве. Когда требуется вставить элемент в массив, мы вставляем его, сдвигая остальные, как в случае сортировки вставкам. Когда необходимо выполнить поиск – выполняется последовательный просмотр массива. Поскольку массив упорядочен, при встрече ключа больше искомого можно сделать вывод о неудаче поиска. При удачном поиске используется в среднем N / 2 сравнений, при неудачном – N.
Бинарный поиск – основан на принципе «разделяй и властвуй». Мы делим упорядоченную таблицу символов на две части, определяем часть, в которой может лежать ключ и производим в ней такую же процедуру поиска. При бинарном поиске используется не более чем Log2(N)+1 опeраций сравнения как при удачном поиске, так и при неудачном.
Сортировка вставками
Сортировка вставками похожа на процесс тасования карточек с именами. Регистратор заносит каждое имя на карточку, а затем упорядочивает карточки по алфавиту, вставляя карточку в верхнюю часть стопки в подходящее место. Опишем этот процесс на примере нашего пятиэлементного списка A = 50, 20, 40, 75, 35 (рисунок 17).
В функцию InsertionSort передается массив A и длина списка n. Рассмотрим i-ый проход (1<i<n-1). Подсписок от A[0] до A[i-1] уже отсортирован по возрастанию. В качестве вставляемого (TARGET) выберем элемент A[i] и будем продвигать его к началу списка, сравнивая с элементами A[i-1], A[i-2] и т.д. Просмотр заканчивается на элементе A[j], который меньше или равен TARGET, или находится в начале списка (j = 0). По мере продвижения к началу списка каждый элемент сдвигается вправо (A[j] = A[j-1]). Когда подходящее место для A[i] будет найдено, этот элемент вставляется в точку j.
Рис. 17.
// Сортировка вставками упорядочивает подсписки A[0]...A[i], 1 <= i <= n-1. Для
// каждого i A[i] вставляется в подходящую позицию A[j]
template <class T>
void InsertionSort(T A[], int n)
{
int i, j;
T temp;
// i определяет подсписок A[0]...A[i]
for (i=1; i<n; i++)
{
// индекс j пробегает вниз по списку от A[i] в процессе
// поиска правильной позиции вставляемого значения
j = i;
temp = A[i];
// обнаружить подходящую позицию для вставки, сканируя подсписок,
// пока temp < A[j-1] или пока не встретится начало списка
while (j > 0 && temp < A[j-1])
{
// сдвинуть элементы вправо, чтобы освободить место для вставки
A[j] = A[j-1];
j--;
}
// точка вставки найдена; вставить temp
A[j] = temp;
}
}
5.Сортировка слиянием.
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
Сортируемый массив разбивается на две части примерно одинакового размера;
Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
Два упорядоченных массива половинного размера соединяются в один.
1.1. - 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
3.1. Cоединение двух упорядоченных массивов в один.
Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два подмассива. Пусть также, элементы подмассивов в каждом из этих подмассивов отсортированы по возрастанию. Тогда:
3.2. Слияние двух подмассивов в третий результирующий массив.
На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1.
3.3. "Прицепление" остатка.
Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.
Псевдокод алгоритма слияния без "прицепления" остатка на C++-подобном языке:
L = *In1;
R = *In2;
if( L == R )
{
*Out++ = L;
In1++;
*Out++ = R;
In2++;
}
else if( L < R )
{
*Out++ = L;
In1++;
}
else
{
*Out++ = R;
In2++;
}
Алгоритм был изобретён Джоном фон Нейманом в 1945 году.[1]
В приведённом алгоритме на C++-подобном языке используется проверка на равенство двух сравниваемых элементов подмассивов с отдельным блоком обработки в случае равенства. Отдельная проверка на равенство удваивает число сравнений, что замедляет алгоритм и усложняет код программы. Вместо отдельной проверки на равенство и отдельного блока обработки в случае равенства можно использовать одну общую проверку if( L <= R ) и общий блок обработки во всех случаях, что вдвое уменьшает число проверок, повышает быстродействие программ, почти вдвое уменьшает код программы и упрощает алгоритм.
Псевдокод улучшенного алгоритма слияния без "прицепления" остатка на C++-подобном языке:
L = *In1;
R = *In2;
if( L <= R ) {
*Out++ = L;
In1++;
}
else {
*Out++ = R;
In2++;
}
Две операции пересылки в переменные L и R упрощают некоторые записи в программе, что может оказаться полезным в учебных целях, но в действительных программах они потребляют дополнительное машинное время и дополнительные ячейки памяти, поэтому в действительных программах они не нужны и их можно удалить, что ещё более увеличит быстродействие, уменьшит расход памяти и сократит программный код.
Псевдокод ещё более улучшенного алгоритма слияния без "прицепления" остатка на C++-подобном языке:
if( *In1 <= *In2 ) {
*Out++ = *In1;
In1++;
}
else {
*Out++ = *In2;
In2++;
}
Время работы алгоритма порядка O(n * log n) при отсутствии деградации на неудачных случаях, которая есть больное место быстрой сортировки (тоже алгоритм порядка O(n * log n), но только для среднего случая). Расход памяти выше, чем для быстрой сортировки, при намного более благоприятном паттерне выделения памяти — возможно выделение одного региона памяти с самого начала и отсутствие выделения при дальнейшем исполнении.
Популярная реализация требует однократно выделяемого временного буфера памяти, равного сортируемому массиву, и не имеет рекурсий. Шаги реализации:
InputArray = сортируемый массив, OutputArray = временный буфер
над каждым отрезком входного массива InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] выполняется какой-то вспомогательный алгоритм сортировки, например, сортировка Шелла или быстрая сортировка.
устанавливается ChunkSize = MIN_CHUNK_SIZE
сливаются два отрезка InputArray[N * ChunkSize..(N + 1) * ChunkSize] и InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize] попеременным шаганием слева и справа (см. выше), результат помещается в OutputArray[N * ChunkSize..(N + 2) * ChunkSize], и так для всех N, пока не будет достигнут конец массива.
ChunkSize удваивается
если ChunkSize стал >= размера массива — то конец, результат в OutputArray, который (ввиду перестановок, описанных ниже) есть либо сортируемый массив, либо временный буфер, во втором случае он целиком копируется в сортируемый массив.
иначе меняются местами InputArray и OutputArray перестановкой указателей, и все повторяется с пункта 4.
Такая реализация также поддерживает размещение сортируемого массива и временного буфера в дисковых файлах, то есть пригодна для сортировки огромных объемов данных. Реализация ORDER BY в СУБД MySQL при отсутствии подходящего индекса устроена именно так (источник: filesort.cc в исходном коде MySQL).
Пример реализации алгоритма простого двухпутевого слияния на псевдокоде:
function mergesort(m)
var list left, right, result
if length(m) ≤ 1
return m
else
middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = mergesort(left)
right = mergesort(right)
result = merge(left, right)
return result
end if
Есть несколько вариантов функции merge(), наиболее простой вариант может выглядеть так:
function merge(left,right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end if
if length(left) > 0
append left to result
if length(right) > 0
append right to result
return result.
продолжение.
/**
* @brief Сортировка элементов от l до r массива buf
* @param[in/out] buf - сортируемый массив
* @param[in] l - левая граница. При первой итерации l = 0
* @param[in] r - правая граница. При первой итерации r = buf.size() - 1
*
* В результате сортируются все элементы массива buf от l до r включительно.
*/
template<typename Type>
void MergeSort(vector<Type>& buf, size_t l, size_t r)
{
//! Условие выхода из рекурсии
if(l >= r) return;
size_t m = (l + r) / 2;
//! Рекурсивная сортировка полученных массивов
MergeSort(buf, l, m);
MergeSort(buf, m+1, r);
merge(buf, l, r, m);
}
/**
* @brief Слияние элементов.
* @param[in/out] buf - массив
* @param[in] l - левая граница. При певой итерации l = 0
* @param[in] r - правая граница. При первой итерации r = buf.size() - 1
* @param[in] m - граница подмассивов.
*
* Массив buf содержит два отсортированных подмассива:
* - [l; m] - первый отсортированный подмассив.
* - [m+1; r] - второй отсортированный подмассив.
* В результате получаем отсортированный массив, полученный из двух подмассивов,
* который сохраняется в buf[l; r].
*/
template<typename Type>
static void merge(vector<Type>& buf, size_t l, size_t r, size_t m)
{
if(l >= r || m < l || m > r) return;
if(r == l + 1 && buf[l] > buf[r])
{
swap(buf[l], buf[r]);
return;
}
vector<Type> tmp(&buf[l], &buf[r+1]);
for(size_t i = l, j = 0, k = m - l + 1; i <= r; i++)
{
if(j > m - l) buf[i] = tmp[k++];
else if(k > r - l) buf[i] = tmp[j++];
else buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
}
}
Существует также итеративный алгоритм сортировки, избавленный от рекурсивных вызовов. Такой алгоритм называют «Восходящей сортировкой слиянием».
// Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
template <class T>
T* merge(T *m1, T* m2, int l1, int l2)
{
T* ret = new T[l1+l2];
int n = 0;
// Сливаем массивы, пока один не закончится
while (l1 && l2)
{
if (*m1 < *m2)
{
ret[n] = *m1;
m1++;
l1--;
}
else
{
ret[n] = *m2;
m2++;
l2--;
}
n++;
}
// Если закончился первый массив
if (l1 == 0)
{
for (int i=0; i<l2; i++)
{
ret[n++] = *m2++;
}
}
// Если закончился второй массив
else
{
for (int i=0; i<l1; i++)
{
ret[n++] = *m1++;
}
}
return ret;
}
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len)
{
int n = 1, l, ost;
T * mas1;
while (n < len)
{
l = 0;
while (l < len)
{
if (l+n >= len) break;
ost = (l+n*2>len) ? (len-(l+n)) : n;
mas1 = merge(mas + l, mas + l + n, n, ost);
for (int i = 0; i<n+ost; i++) mas[l+i] = mas1[i];
delete [] mas1;
l += n*2;
}
n *= 2;
}
}
Пример: char a[] = "ASORTINGEXAMPLE"; mergeSort(a, 16); Альтернативная версия алгоритма Сортировки Слиянием.
template <typename Item>
void Merge(Item Mas[], int left, int right, int medium)
{
int j = left;
int k = medium + 1;
int count = right - left + 1;
if (count <= 1) return;
Item *TmpMas = new Item[count];
for (int i = 0; i < count; i++)
{
if (j <= medium && k <= right)
{
if (Mas[j] < Mas[k])
TmpMas[i] = Mas[j++];
else
TmpMas[i] = Mas[k++];
}
else
{
if (j <= medium)
TmpMas[i] = Mas[j++];
else
TmpMas[i] = Mas[k++];
}
}
j = 0;
for (int i = left; i <= right; i++)
{
Mas[i] = TmpMas[j++];
}
delete[] TmpMas;
}
template <typename Item>
void MergeSort(Item a[], int l, int r)
{
int m;
// Условие выхода из рекурсии
if(l >= r) return;
m = (l + r) / 2;
// Рекурсивная сортировка полученных массивов
MergeSort(a, l, m);
MergeSort(a, m + 1, r);
Merge(a, l, r, m);
}
Это все СИ.
Теперь кому удобно на паскале. Программа.
Program SlivSort;
Var A,B : array[1..1000] of integer;
N : integer;
Procedure Sliv(p,q : integer); {процедура сливающая массивы}
Var r,i,j,k : integer;
Begin
r:=(p+q) div 2;
i:=p;
j:=r+1;
for k:=p to q do
if (i<=r) and ((j>q) or (a[i]<a[j])) then
begin
b[k]:=a[i];
i:=i+1;
end
else
begin
b[k]:=a[j];
j:=j+1;
end ;
for k:=p to q do
a[k]:=b[k];
End;
Procedure Sort(p,q : integer); {p,q - индексы начала и конца сортируемой части массива}
Begin
if p<q then {массив из одного элемента тривиально упорядочен}
begin
Sort(p,(p+q) div 2);
Sort((p+q) div 2 + 1,q);
Sliv(p,q);
end;
End;
Begin
{Определение размера массива A - N) и его заполнение}
…
{запуск сортирующей процедуры}
Sort(1,N);
{Вывод отсортированного массива A}
…
End.
Структуры и базы данных, методы сортировки. Сортировка слиянием
Сортировка слиянием (метод простого двухпутевого слияния)
В основе данного метода внутренней сортировки лежит процедура слияния двух упорядоченных таблиц. Эти таблицы должны быть объединены таким образом, чтобы получилась одна упорядоченная таблица.
Пусть имеются две таблицы А и В, упорядоченные по возрастанию ключей . Слияние заключается в поочередной пересылке элементов из таблиц А и В в зону формирования С. Порядок пересылки в зону формирования зависит от результата попарного сравнения ключей таблиц А и В.
Сортировка слиянием производится на основе использования рассмотренной выше процедуры. Сущность сортировки состоит в том, что упорядочиваемая таблица разделяется на равные группы элементов. Группы упорядочиваются, а затем попарно сливаются, образуя новые группы, содержащие вдвое больше элементов.
Процедура слияния двух групп должна иметь такие параметры:
TAB - имя сортируемой таблицы;
n - длина таблицы (количество записей);
i1,i2 - начальные индексы сливаемых групп;
l1,l2 - длины сливаемых групп;
h - шаг слияния;
PS - поле слияния.
TAB TAB
--------------- ---------------
¦ . . . ¦ ¦ . . . ¦
i1 +-------------+ ------- i1 +-------------+
¦ 23 ¦ l1 ¦ 17 ¦ ¦ 17 ¦
¦ 68 ¦ +-----+ ¦ 19 ¦
i2 +-------------+ ¦ 19 ¦ ¦ 23 ¦
¦ 17 ¦ +-----+ ¦ 68 ¦
¦ 19 ¦ l2 ¦ 23 ¦ ¦ ¦
+-------------+ +-----+ +-------------+
¦ ¦ ¦ 68 ¦ ¦ ¦
¦ . . . ¦ ------ ¦ . . . ¦
-------------- --------------
На первом этапе каждая группа содержит два соседних элемента исходного массива. Элементы внутри групп упорядочиваются (напр., методом вставки). Затем происходит попарное слияние групп. Количество групп в списке уменьшается вдвое до тех пор, пока не будет получена одна упорядоченная группа. Если число элементов нечетное, то вводится дополнительный элемент с максимальным значением. После сортировки он отбрасывается. Если число групп, сформированных на первом этапе, нечетно, то непарная группа переписывается без слияния. Рассмотренный метод двухпутевой сортировки слиянием весьма эффективен. Поскольку при сортировке нужно выполнить log2(n) проходов,то необходимое суммарное число сравнений равно,примерно,n*log2(n). Одним из недостатков данного метода является требование большого резерва памяти:
S = [n/2].
Сортировка слиянием (естественное слияние)
Метод простого слияния никак не учитывает тот факт,что в таблице могут быть сразу или получаться на некотором шаге упорядоченые группы записей длиной m и l,которые можно сразу объединить в одну упорядоченную группу длиной m+l (более того,эти упорядоченные последовательности могут разрываться,их
элементы будут относиться к разным группам). Сортировка,при которой сливаются рядом стоящие упорядоченные группы произвольной длины,называется естественным слиянием. Цель естественного слияния-исключить лишние просмотры. Процедура слияния двух групп такая же,как и в методе простого слияния,но длины l1 и l2 сливаемых групп нужно каждый раз подсчитывать,сравнивая ключи двух рядом стоящих записей (можно составить массив длин упорядоченных групп).