Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Данные).pdf

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

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

Эффективны при сортировке подходящего массива входных данных. Низкая эффективность если массив входящих данных слабо подходит для соответствующего алгоритма сортировки.

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

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

Сравнивать алгоритмы сортировки удобно матричным методом, предполагающим сравнение по двум параметрам. При сравнении по устойчивости алгоритмы сортировки делятся на устойчивые и неустойчивые. При сравнении по скорости алгоритмы можно разделить на 3 группы: число операций в которых <n², n² и >n².

Из представленных алгоритмов сортировки большинство входит в три получившихся группы. Это - «Быстрая устойчивая сортировка» (алгоритм сортировки Тима Петерса и сортировка слиянием), «Быстрая неустойчивая сортировка» (интроспективная сортировка, сортировка Шелла, плавная сортировка, терпеливая сортировка, пирамидальная сортировка) и «Медленная устойчивая сортировка» (гномья сортировка, сортировка вставками, сортировка пузырьком, сортировка выбором, сортировка перемешиванием).

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

Глава 6. Сортировка строк

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

Применение данного метода к строкам, представляющим собой числа в естественной записи, выдаёт контринтуитивные результаты: например, «9» оказывается больше, чем «11», так как первый символ первой строки имеет бо́льшее значение, чем первый символ второй. Для исправления этой проблемы алгоритм сортировки может преобразовывать сортируемые строки в числа и сортировать их как числа. Такой алгоритм называется «числовой сортировкой», а описанный ранее — «строковой сортировкой».

Глава 7. Сортировки в программе Excel

В программе Excel предусмотрены следующие методы сортировки.

Можно выполнять сортировку данных по тексту (от А к Я или от Я к А), при необходимости можно выполнить сортировку с учетом регистра, по числам (от наименьших к наибольшим или от наибольших к наименьшим), а также датам и времени (от старых к новым или от новых к старым) в нескольких столбцах. Можно также выполнять сортировку по настраиваемым спискам (таким как состоящий из элементов "Большой", "Средний" и "Маленький") или по формату, включая цвет ячеек, цвет шрифта, а также по значкам. Большинство сортировок применяются к столбцам, но возможно также применить сортировку к строкам. Имеется сортировка по цвету ячейки, цвету шрифта или значку. Предусмотрена сортировка по нескольким столбцам или строкам

Заключение

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

Список использованных источников

1. ГОСТ 17657-79. Передача данных. Термины и определения.
2. ГОСТ 15971-90. Системы обработки информации. Термины и определения
3. ГОСТ 34.320-96. Информационные технологии. Система стандартов по базам данных. Концепции и терминология для концептуальной схемы и информационной базы.
4. ГОСТ Р ИСО/МЭК 12119-2000. Информационная технология. Пакеты программ. Требования качеству и тестирование.
5. ГОСТ Р 52292-2004. Информационная технология. Электронный обмен информацией. Термины и определения.
6. URL: https://ru.wikipedia.org/wiki/Данные . (Дата обращения 11.08.2016).
7. Ожегов С. И., Шведова Н. Ю. Толковый словарь русского языка: 80 000 слов и фразеологических выражений / Российская академия наук. Институт русского языка им. В. В. Виноградова. — 4-е изд., дополненное. — М.: Азбуковник, 1999. — 944 с.
8. проф. Ушаков Д. Н. Орфографический словарь русского языка. — М.: Учпедгиз, 1937. — 162 с.
9. Райзберг Б.А., Лозовский Л.Ш., Стародубцева Е.Б. Современный экономический словарь. — 2-е изд., испр. М.: ИНФРА-М, 1999. 479 с.
10. Большой энциклопедический словарь / Ред. А. М. Прохоров . – 2-е изд., перераб. и доп . – М. : Большая Российская энциклопедия, 2000 . – 1456 с.
11. URL: http://dic.academic.ru/dic.nsf/es/92145/Герман Холлерит (Дата обращения 11.08.2016).
12. URL: https://en.wikipedia.org/wiki/Tabulating_machine (Дата обращения 11.08.2016).
13. Суменко Л.Г. Англо-русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003
14. URL: https://ru.wikipedia.org/wiki/Поразрядная_сортировка (Дата обращения 11.08.2016).
15. URL: http://rain.ifmo.ru/cat/data/theory/school/ses-VectSort-05/pres.pdf. (Дата обращения 11.08.2016).
16. URL: https://ru.wikipedia.org/wiki/Мокли,_Джон (Дата обращения 11.08.2016).
17. URL: https://ru.wikipedia.org/wiki/Шелл,_Дональд (Дата обращения 11.08.2016).
18. URL: https://ru.wikipedia.org/wiki/Хоар,_Чарльз_Энтони_Ричард (Дата обращения 11.08.2016).
19. URL: http://www.tp7.info/ebook/piramid_sort.pdf (Дата обращения 11.08.2016).
20. Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. —М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4.
21. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4.
22. Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4.
23. Magnus Lie Hetland. Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с. — ISBN 978-1-4302-3237-7.
24. URL: http://www.moluch.ru/archive/56/7702/ (Дата обращения 11.08.2016).
25. URL: http://www.moluch.ru/archive/55/7474/ (Дата обращения 11.08.2016).
26. URL: http://www.intuit.ru/studies/courses/12181/1174/lecture/25257 (Дата обращения 11.08.2016).
27. Дупленко А. Г. Сравнительный анализ алгоритмов сортировки данных в массивах // Молодой ученый. — 2013. — № 8. — С. 50–53.
28. Никитин Ю. Б. Сложность алгоритмов сортировки на частично упорядоченных множествах: автореферат дис. … канд. физ.-мат. наук: 01.01.09 / Никитин Юрий Борисович. — Москва, 2001. — 80 с.
29. URL: http://articles.org.ru/docum/sort.php (Дата обращения 11.08.2016).
30. URL: https://ru.wikipedia.org/wiki/Сортровка_перемешиванием (Дата обращения 11.08.2016).
31. URL: http://articles.org.ru/docum/sort.php (Дата обращения 11.08.2016).
32. URL: https://ru.wikipedia.org/wiki/Гномья_сортировка (Дата обращения 11.08.2016).
33. URL: https://habrahabr.ru/post/280848/ (Дата обращения 11.08.2016).
34. URL: https://habrahabr.ru/post/221095/ (Дата обращения 11.08.2016).
35. URL: https://ru.wikipedia.org/wiki/Timsort (Дата обращения 11.08.2016).
36. URL: https://ru.wikipedia.org/wiki/Сортировка_вставками (Дата обращения 11.08.2016).
37. URL: https://ru.wikipedia.org/wiki/Метод_перебора (Дата обращения 11.08.2016).
38. URL: https://ru.wikipedia.org/wiki/Двоичный_поиск (Дата обращения 11.08.2016).
39. URL: https://ru.wikipedia.org/wiki/Быстрая_сортировка (Дата обращения 11.08.2016).
40. URL: http://www.pvsm.ru/algoritmy/50063/print/ (Дата обращения 11.08.2016).
41. URL: https://ru.wikipedia.org/wiki/Сортировка_Шелла (Дата обращения 11.08.2016).
42. URL: https://ru.wikipedia.org/wiki/Сортировка_подсчётом (Дата обращения 11.08.2016).
43. URL: https://ru.wikipedia.org/wiki/Глупая_сортировка (Дата обращения 11.08.2016).
44. URL: https://ru.wikipedia.org/wiki/Bogosort (Дата обращения 11.08.2016).
45. URL: https://ru.wikipedia.org/wiki/Пирамидальная_сортировка (Дата обращения 11.08.2016).