Лекция
Сразу хочу сказать, что здесь никакой воды про алгоритмы сортировки, и только нужная информация. Для того чтобы лучше понимать что такое алгоритмы сортировки, сортировка, сортировка пузырьком , bubble sort, сортировка перемешиванием, cocktail sort, сортировка вставками, insertion sort, гномья сортировка, gnome sort, сортировка слиянием, merge sort, сортировка с помощью двоичного дерева, tree sort, сортировка timsort, timsort, сортировка выбором , selection sort, сортировка расческой, сортировка гребешком, comb sort, сортировка шелла , shell sort, пирамидальная сортировка , сортировка кучи, heapsort, плавная сортировка , smoothsort , быстрая сортировка, quicksort , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Табулятор Холлерита с «сортировальным ящиком»
Первые прототипы современных методов сортировки появились уже в XIX веке. К 1890 году для ускорения обработки данных переписи населения в США американец Герман Холлерит создал первый статистический табулятор — электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах . У машины Холлерита имелся специальный «сортировальный ящик» из 26 внутренних отделений. При работе с машиной от оператора требовалось вставить перфокарту и опустить рукоятку. Благодаря пробитым на перфокарте отверстиям замыкалась определенная электрическая цепь, и на единицу увеличивалось показание связанного с ней циферблата. Одновременно с этим открывалась одна из 26 крышек сортировального ящика, и в соответствующее отделение перемещалась перфокарта, после чего крышка закрывалась. Данная машина позволила обрабатывать около 50 карт в минуту, что ускорило обработку данных в 3 раза. К переписи населения 1900 года Холлерит усовершенствовал машину, автоматизировав подачу карт . Работа сортировальной машины Холлерита основывалась на методах поразрядной сортировки. В патенте на машину обозначена сортировка «по отдельности для каждого столбца», но не определен порядок. В другой аналогичной машине, запатентованной в 1894 году Джоном Гором, упоминается сортировка со столбца десятков . Метод сортировки, начиная со столбца единиц, впервые появляется в литературе в конце 1930-х годов . К этому времени сортировальные машины уже позволяли обрабатывать до 400 карт в минуту .
EDVAC
В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин. По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин. Некоторые конструкторы ЭВМ, в частности разработчики EDVAC, называли задачу сортировки данных наиболее характерной нечисловой задачей для вычислительных машин. В 1945 году Джон фон Нейман для тестирования ряда команд для EDVAC разработал программы сортировки методом слияния. В том же году немецкий инженер Конрад Цузе разработал программу для сортировки методом простой вставки. К этому времени уже появились быстрые специализированные сортировальные машины, в сопоставлении с которыми и оценивалась эффективность разрабатываемых ЭВМ . Первым опубликованным обсуждением сортировки с помощью вычислительных машин стала лекция Джона Мокли, прочитанная им в 1946 году. Мокли показал, что сортировка может быть полезной также и для численных расчетов, описал методы сортировки простой вставки и бинарных вставок, а также поразрядную сортировку с частичными проходами. Позже организованная им совместно с инженером Джоном Эккертом компания «Eckert–Mauchly Computer Corporation» выпустила некоторые из самых ранних электронных вычислительных машин BINAC и UNIVAC . Наряду с отмеченными алгоритмами внутренней сортировки, появлялись алгоритмы внешней сортировки, развитию которых способствовал ограниченный объем памяти первых вычислительных машин . В частности, были предложены методы сбалансированной двухпутевой поразрядной сортировки и сбалансированного двухпутевого слияния .
К 1952 году на практике уже применялись многие методы внутренней сортировки, но теория была развита сравнительно слабо . В октябре 1952 года Даниэль Гольденберг привел пять методов сортировки с анализом наилучшего и наихудшего случаев для каждого из них. В 1954 году Гарольд Сьюворд развил идеи Гольденберга, а также проанализировал методы внешней сортировки. Говард Демут в 1956 году рассмотрел три абстрактные модели задачи сортировки: с использованием циклической памяти, линейной памяти и памяти с произвольным доступом. Для каждой из этих задач автор предложил оптимальные или почти оптимальные методы сортировки, что помогло связать теорию с практикой . Из-за малого числа людей, связанных с вычислительной техникой, эти доклады не появлялись в «открытой литературе». Первой большой обзорной статьей о сортировке, появившейся в печати в 1955 году, стала работа Дж. Хоскена, в которой он описал все имевшееся на тот момент оборудование специального назначения и методы сортировки для ЭВМ, основываясь на брошюрах фирм-изготовителей. В 1956 году Э. Френд в своей работе проанализировал математические свойства большого числа алгоритмов внутренней и внешней сортировки, предложив некоторые новые методы .
После этого было предложено множество различных алгоритмов сортировки: например, вычисление адреса в 1956 году; слияние с вставкой, обменная поразрядная сортировка, каскадное слияние и метод Шелла в 1959 году, многофазное слияние и вставки в дерево в 1960 году, осциллирующая сортировка и быстрая сортировка Хоара в 1962 году, пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера в 1964 году. В конце 60-х годов произошло и интенсивное развитие теории сортировки . Появившиеся позже алгоритмы во многом являлись вариациями уже известных методов. Получили распространение адаптивные методы сортировки, ориентированные на более быстрое выполнение в случаях, когда входная последовательность удовлетворяет заранее установленным критериям .
Пусть требуется упорядочить N элементов: 
. Каждый элемент представляет из себя запись 
, содержащую некоторую информацию и ключ 
, управляющий процессом сортировки. На множестве ключей определено отношение порядка «<» так, чтобы для любых трех значений ключей 
выполнялись следующие условия[10]:
, либо 
, либо 
; и 
, то 
.Данные условия определяют математическое понятие линейного или совершенного упорядочения, а удовлетворяющие им множества поддаются сортировке большинством методов[10].
Задачей сортировки является нахождение такой перестановки записей 
с индексами 
, после которой ключи расположились бы в порядке неубывания[10]:
Сортировка называется устойчивой, если не меняет взаимного расположения элементов с одинаковыми ключами[10]:
для любых 
и }
.
Методы сортировки можно разделить на внутренние и внешние. Об этом говорит сайт https://intellect.icu . Внутренняя сортировка используется для данных, помещающихся в оперативную память, за счет чего является более гибкой в плане структур данных. Внешняя сортировка применяется, когда данные в оперативную память не помещаются, и ориентирована на достижение результата в условиях ограниченных ресурсов[11].
алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:
в общем случаеВ общем случае задача сортировки предполагает, что единственной обязательно доступной операцией над элементами является сравнение. Ответом на сравнение элементов 
и 
может быть один из двух вариантов: 
или . Поэтому если в ходе работы алгоритм совершает 
сравнений, то всего возможно }
вариантов комбинаций ответов на них.
Количество перестановок из 
элементов равно 
. Для того, чтобы можно было провести сюръекцию из множества комбинаций ответов во множество всех перестановок, количество сравнений должно быть не меньше, чем 
(поскольку сравнение — единственная разрешенная операция).
Прологарифмировав формулу Стирлинга, можно обнаружить, что 
[12]
( 
), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.Еще одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:
Также алгоритмы классифицируются по:
Классификация алгоритмов сортировки
В этой таблице — это количество записей, которые необходимо упорядочить, а — это количество уникальных ключей.
...; рекурсивная версия требует дополнительно памяти.
. Требуется 
дополнительной памяти. в лучшем случае, а в худшем. Требуется дополнительной памяти.. Требуется дополнительной памяти. Разработан для использования в языке Python[14]..; улучшение сортировки пузырьком.
или 
.
; превращаем список в кучу, берем наибольший элемент и добавляем его в конец списка.. — среднее время, — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине. При использовании дополнительной памяти, можно сделать сортировку устойчивой., сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает 
. — наихудший случай, требует дополнительно памяти, также находит самую длинную увеличивающуюся подпоследовательность.
.
в среднем. Произвольно перемешать массив, проверить порядок.
— худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива. или 
, требуется специализированное аппаратное обеспечение., требуется специализированное аппаратное обеспечение.
дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций «переставить» и «сравнить». Сложность алгоритма: {\displaystyle O(n)}.
; требуется дополнительной памяти.
. Требуется дополнительной памяти.
Эффективность алгоритвомов сортировок
Одним из наиболее частых приложений алгоритмов сортировки является сортировка строк. Обычно она производится так: сначала множество строк сортируется по первому символу каждой строки, затем каждое подмножество строк, имеющих одинаковый первый символ, сортируется по второму символу, и так до тех пор, пока все строки не будут упорядочены. При этом отсутствующий символ (при сравнении строки длины N со строкой длины N+1) считается меньше любого символа.
Применение данного метода к строкам, представляющим собой числа в естественной записи, выдает контринтуитивные результаты: например, «9» оказывается больше, чем «11», так как первый символ первой строки имеет бо́льшее значение, чем первый символ второй. Для исправления этой проблемы алгоритм сортировки может преобразовывать сортируемые строки в числа и сортировать их как числа. Такой алгоритм называется «числовой сортировкой», а описанный ранее — «строковой сортировкой». Так же на практике эффективным способом решения проблемы сортировки строк содержащих числа является добавление некоторого числа нулей перед числом, таким образом «011» будет считаться больше «009» из-за наличия нулей.
А как ты думаешь, при улучшении алгоритмы сортировки, будет лучше нам? Надеюсь, что теперь ты понял что такое алгоритмы сортировки, сортировка, сортировка пузырьком , bubble sort, сортировка перемешиванием, cocktail sort, сортировка вставками, insertion sort, гномья сортировка, gnome sort, сортировка слиянием, merge sort, сортировка с помощью двоичного дерева, tree sort, сортировка timsort, timsort, сортировка выбором , selection sort, сортировка расческой, сортировка гребешком, comb sort, сортировка шелла , shell sort, пирамидальная сортировка , сортировка кучи, heapsort, плавная сортировка , smoothsort , быстрая сортировка, quicksort и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов