Методы сортировки

Методы сортировки

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

Содержание

Оценка алгоритма сортировки

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

  • Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = | A | . Для типичного алгоритма хорошее поведение — это O \left(n \log n \right) и плохое поведение — это O \left(n^2 \right). Идеальное поведение для упорядочения — O \left(n \right). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в \Omega \left(n \log n \right) сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O \left(n \cdot  \log \log n \cdot \log \log \log n \right), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O \left(\log^2 n \right) операций. При этом число n должно быть заранее известно;
  • Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O \left(\log n \right) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O \left(1 \right)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Классификация алгоритмов сортировки

  • Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.
  • Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
  • Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O \left(n \log n \right), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

  • Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
    • В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
  • Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.
    • Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
    • Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

  • потребности в дополнительной памяти или её отсутствии
  • потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствии таковой

Список алгоритмов сортировки

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

Алгоритмы устойчивой сортировки

  • Сортировка пузырьком (англ. Bubble sort ) — сложность алгоритма: O(n2); для каждой пары индексов производится обмен, если элементы расположены не по порядку.
  • Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n2)
  • Сортировка вставками (Insertion sort) — Сложность алгоритма: O(n2); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда
  • Блочная сортировка (Корзинная сортировка, Bucket sort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций "переставить" и "сравнить".
  • Сортировка подсчётом (Counting sort) — Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти (рассмотрено 3 варианта)
  • Сортировка слиянием (Merge sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки
  • In-place merge sort — Сложность алгоритма: O(n2), O(n log2 n) или O(n log n) в зависимости от применяемого алгоритма слияния.
  • Двоичное дерево сортировки (Binary tree sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти
  • Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort) — Сложность алгоритма: O(n+k); требуется O(k) дополнительной памяти
  • Гномья сортировка (Gnome sort) — Сложность алгоритма: O(n2)

Алгоритмы неустойчивой сортировки

  • Сортировка выбором (Selection sort) — Сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка
  • Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log2 n); попытка улучшить сортировку вставками
  • Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n)
  • Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
  • Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n)
  • Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n2) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
  • Introsort — Сложность алгоритма: O(n log n), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).
  • Patience sorting — Сложность алгоритма: O(n log n + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность
  • Обменная поразрядная сортировка — Сложность алгоритма: 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), требуется специализированное аппаратное обеспечение

Алгоритмы, не основанные на сравнениях

Остальные алгоритмы сортировки

См. также

Литература

  • Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0
  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
  • Роберт Седжвик Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Методы сортировки" в других словарях:

  • класс сортировки — Классификация контролируемого изделия в одном диапазоне или в нескольких диапазонах требуемых характеристик, например твердости, состава материала или размеров. [Система неразрушающего контроля. Виды (методы) и технология неразрушающего контроля …   Справочник технического переводчика

  • ГОСТ Р ИСО 14644-3-2007: Чистые помещения и связанные с ними контролируемые среды. Часть 3. Методы испытаний — Терминология ГОСТ Р ИСО 14644 3 2007: Чистые помещения и связанные с ними контролируемые среды. Часть 3. Методы испытаний оригинал документа: 3.2.11 U дескриптор (U descriptor): Полученное или заданное количество частиц, включая ультрамелкие… …   Словарь-справочник терминов нормативно-технической документации

  • ГОСТ Р ИСО 2859-5-2009: Статистические методы. Процедуры выборочного контроля по альтернативному признаку. Часть 5. Система последовательных планов на основе AQL для контроля последовательных партий — Терминология ГОСТ Р ИСО 2859 5 2009: Статистические методы. Процедуры выборочного контроля по альтернативному признаку. Часть 5. Система последовательных планов на основе AQL для контроля последовательных партий оригинал документа: 3.36… …   Словарь-справочник терминов нормативно-технической документации

  • Медицинская сортировка — У этого термина существуют и другие значения, см. Триаж (значения). Триаж во Франции, Первая мировая война. Медицинская сортир …   Википедия

  • Сортировка выбором — (Selection sort)  алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное… …   Википедия

  • семантическое пространство субъективное —         СЕМАНТИЧЕСКОЕ ПРОСТРАНСТВО СУБЪЕКТИВНОЕ (англ. Subjective Semantic Space) операциональнаяй модель представления категориальной структуры индивидуального сознания в виде математического пространства, координатные оси которого соответствуют …   Энциклопедия эпистемологии и философии науки

  • Лицей № 1580 — ГОУ Лицей № 1580 при МГТУ им. Н.Э. Баумана …   Википедия

  • Лицей 1580 — ГОУ Физико математический лицей № 1580 при МГТУ им. Н.Э. Баумана Основана: 1989г. Директор: Граськин Сергей Сергеевич Тип: Физико математический лицей Учеников: около 600 учащихся Адрес: (Южный округ) …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • РАЗРАБОТАН — 1 РАЗРАБОТАН: Обществом с ограниченной ответственностью Научно исследовательский институт природных газов и газовых технологий ВНИИГАЗ Источник …   Словарь-справочник терминов нормативно-технической документации


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»