Пусть есть последовательность a0, a1... an и функция сравнения, которая на любых двух элементах последовательности принимает одно из трех значений: меньше, больше или равно. Задача сортировки состоит в перестановке членов последовательности таким образом, чтобы выполнялось условие: ai <= ai+1, для всех i от 0 до n. Возможна ситуация, когда элементы состоят из нескольких полей: struct element { field x; field y; } Если значение функции сравнения зависит только от поля x, то x называют ключом, по которому производится сортировка. На практике, в качестве x часто выступает число, а поле y хранит какие-либо данные, никак не влияющие на работу алгоритма. Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий "универсальный", наилучший алгоритм ? Вообще говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом. Для того, чтобы обоснованно сделать такой выбор, рассмотрим параметры, по которым будет производиться оценка алгоритмов. Время сортировки - основной параметр, характеризующий быстродействие алгоритма. Память - ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы. Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, как на рис. 1, а сортировка происходит по одному из них, например, по x. Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" осталось прежним: элемент с полем "a", затем - с "b", затем - с "c". Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" изменилось. Естественность поведения - эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше. Еще одним важным свойством алгоритма является его сфера применения. Здесь основных позиций две: внутренние сортировки работают с данным в оперативной памяти с произвольным доступом; внешние сортировки упорядочивают информацию, расположенную на внешних носителях. Это накладывает некоторые дополнительные ограничения на алгоритм: доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим объем данных не позволяет им разместиться в ОЗУ Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью. Данный класс алгоритмов делится на два основных подкласса: Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат. Внешняя сортировка оперирует с запоминающими устройствами большого объема, но с доступом не произвольным, а последовательным (сортировка файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики . Это приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Основные методы сортировки Статьи ниже являются частями одной большой, так что в последующих может использоваться информация из предыдущих. В программах используются переопределения: typedef double real; typedef unsigned long ulong; typedef unsigned short ushort; typedef unsigned char uchar; Под переменной size принимается количество элементов в массиве, а для обозначения индекса последнего элемента используется N. Очевидно, size=N+1. Квадратичные и субквадратичные алгоритмы Сортировка выбором(SelectSort) Сортировка пузырьком(BubbleSort) и ее улучшения Сортировка простыми вставками(InsertSort) Cортировка Шелла (ShellSort) Сравнение времени сортировок Изображенный ниже график иллюстрирует разницу в эффективности изученных алгоритмов. коричневая линия: сортировка пузырьком; синяя линия: шейкер-сортировка; розовая линия: сортировка выбором; желтая линия: сортировка вставками; голубая линия: сортировка вставками со сторожевым элементом; фиолетовая линия: сортировка Шелла. Логарифмические и линейные алгоритмы Пирамидальная сортировка (HeapSort) Быстрая сортировка (QuickSort) Поразрядная сортировка(Radix sort) Некоторую информацию, которой нет выше, можно найти в FAQ по сортировкам из эхо конференции RU.ALGORITM. Если же требуется сортировать большие массивы и наложены очень серьезные требования по быстродейстивю, то весьма хорошее впечатление производит гибрид быстрой и распределяющей сортировок: "Быстрая сортировка с составными ключами". В материале сравниваются различные методы сортировки строк и приводятся исходные тексты на языке C. Кроме того, существует топологическая сортировка, оперерующая с частично упорядоченными структурами, например, с ориентированными графами без циклов . Она приводит их представление в ЭВМ к виду, при котором все ребра направлены в одну сторону. С циклами такой фокус, естественно, не пройдет. SpeedSIP значительно снижает расходы на телефонную связь и сервисы: бесплатные звонки внутри сети, выгодные международные и междугородные звонки, СМС по всему миру, покупка прямого номер любой страны, видеосвязь и видеоконференции. В этом разделе : 8  Сортировка выбором Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. 8  Сортировка пузырьком Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. 8  Сортировка вставками Сортировка простыми вставками в чем-то похожа на вышеизложенные методы. 8  Сортировка Шелла Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками. 8  Пирамидальная сортировка Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n). 8  Быстрая сортировка Быстрая сортировка, хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов. 8  Поразрядная сортировка Рассматриваемый ниже алгоритм существенно отличается от описанных ранее. 8  Сортировка слиянием Сортировка слиянием также построена на принципе "разделяй-и-властвуй", однако реализует его несколько по-другому, нежели quickSort. 8  Топологическая сортировка Нерекурсивный алгоритм топологической сортировки ориентированного графа без циклов. 8  FAQ Для удобства редактирования весь FAQ представлен в виде чистого текста, с минимумом ссылок, и без изображений. 8  Быстрые алгоритмы сортировки и поиска строк В материале сравниваются различные методы сортировки строк и приводятся исходные тексты на языке C.

8  Сортировка выбором 8  Сортировка пузырьком 8  Сортировка вставками 8  Сортировка Шелла 8  Пирамидальная сортировка 8  Быстрая сортировка 8  Поразрядная сортировка 8  Сортировка слиянием 8  Топологическая сортировка 8  FAQ 8  Быстрые алгоритмы сортировки и поиска строк