§ 18. Сортировка одномерного массива
18.1. Понятие сортировки массива
|
Сортировкой называется процесс упорядочения последовательности элементов по какому-либо признаку. С сортировкой вы уже сталкивались при работе с электронными таблицами. Там можно было упорядочить числовые значения в порядке возрастания или убывания, а строковые — в алфавитном (или обратном алфавитному) порядке (пример 18.1). В отсортированном виде хранятся данные в списке контактов в смартфоне (в алфавитном порядке) или письма в электронном почтовом ящике (в порядке получения), данные в различных справочниках и энциклопедиях. Задача сортировки состоит в такой перестановке элементов последовательности, чтобы для двух соседних элементов выполнялось условие того, что они находятся в порядке. Порядок элементов определяет функция сравнения, которая на любых двух элементах последовательности принимает одно из трех значений: меньше, больше или равно. Таким образом, сортировка множества элементов возможна тогда, когда для этого множества введено понятие порядка. Порядок, при котором на первом месте в отсортированной последовательности будет находиться самый маленький элемент, а каждый следующий будет больше предыдущего, называют возрастающим. Если на первом месте будет самый большой элемент, а каждый следующий будет меньше, то такой порядок называют убывающим. Часто среди элементов сортируемой последовательности могут оказаться равные по значению элементы. В этом случае принято говорить о порядке неубывания (невозрастания). В общем случае элементы могут быть не равны по значению, но считаться равными относительно функции сравнения (пример 18.2). Сортировка массива — расположение его элементов в некотором заданном порядке. В отсортированном массиве поиск элемента можно осуществлять, не просматривая весь массив. Например, в случае сортировки в порядке возрастания минимальный элемент массива всегда будет находиться на первом месте. Задача сортировки, как и любая другая задача, может решаться множеством способов, каждый из которых имеет как достоинства, так и недостатки. На сегодняшний день известно более десятка различных алгоритмов сортировки и их модификаций. Выбор алгоритма сортировки определяется особенностями решаемой задачи. Алгоритм сортировки — алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. При выборе метода сортировки необходимо учитывать следующие моменты: объем требуемой памяти и скорость работы. При сортировке массива желательно использовать как можно меньше дополнительной памяти, поэтому обычно рассматриваются алгоритмы, которые упорядочивают массив перестановками его элементов (без использования еще одного массива). Оценить скорость работы метода сортировки можно, оценив количество требуемых операций сравнения и (или) операций перестановок элементов. Ниже рассматриваются методы сортировки линейного массива по возрастанию (неубыванию). Сортировка по убыванию (невозрастанию) производится аналогично. Сортировка с использованием функции сравнения будет показана в конце параграфа. |
Пример 18.1. Сортировка в электронной таблице.
Функцией сравнения в первом случае будет функция, сравнивающая строки лексикографически. Во втором случае сравниваются числовые значения. Первые прототипы современных методов сортировки появились уже в XIX в., когда были изобретены сортировочные машины. Первая такая машина была изобретена Германом Холлеритом (1860–1929). Устройство называлось табулятор, патент на который был получен в 1884 г. Затем в течение пяти лет Г. Холлерит запатентовал перфоратор, сортировку и перфокарту. Табулятор использовался для обработки данных переписи населения в США в 1890 г.
При работе табулятор размещал перфокарты по 26 ячейкам «сортировального ящика» (слева) в зависимости от того, d каком месте перфокарты было сделано отверстие. Машина позволяла обрабатывать до 80 перфокарт за час. Созданная Г. Холлеритом в 1896 г. фирма Tabulating Machine Company по производству счетно-аналитических машин со временем слилась с другими компаниями в одну, которая с 1924 г. называется International Business Machines (IBM). До 1921 г. Холлерит оставался консультантом этой фирмы. Пример 18.2. Пусть элементами последовательности являются натуральные числа. Требуется расположить элементы последовательности так, чтобы в начале стояли четные числа, а затем нечетные. Для сортировки в таком порядке можно, например, сравнивать остатки от деления числа на 2. В этом случае четное число (остаток 0) меньше нечетного (остаток 1). Любые два четных числа так же, как и любые два нечетных числа, будут равны относительно функции сравнения. Работа сортировальной машины Г. Холлерита основывалась на методах поразрядной сортировки. Другие известные методы сортировок появились с развитием ЭВМ. По некоторым источникам[1], именно программа сортировки стала первой программой для вычислительных машин. Некоторые конструкторы ЭВМ, в частности разработчики EDVAC, называли задачу сортировки данных наиболее характерной нечисловой задачей для вычислительных машин. В 1945 г. Джон фон Нейман для тестирования ряда команд для EDVAC разработал программы сортировки методом слияния. В том же году немецкий инженер Конрад Цузе разработал программу для сортировки методом простых вставок. В 1959 г. был разработан метод Шелла, в 1962 г. появился алгоритм быстрой сортировки Хоара. Возникшие позже алгоритмы во многом являлись вариациями уже известных методов. Одной из последних разработок является алгоритм Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием. Опубликован в 2002 г. Тимом Петерсом (американский разработчик ПО, внес большой вклад в язык программирования Python). В настоящее время Timsort является стандартным алгоритмом сортировки в Python и др. Основная идея алгоритма в том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных Timsort существенно быстрее многих алгоритмов сортировки.[1] Дональд Е. Кнут. Искусство программирования. Т. 3. Сортировка и поиск. М: ООО «И.Д. Вильямс», 2018. – 832 с. |
