Сортировка

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

упорядочивание : расположение элементов в последовательности, упорядоченной по некоторому критерию;
категоризация : группировка предметов со схожими свойствами.

Упорядочение элементов — это сочетание их категоризации на основе эквивалентного порядка и упорядочивания самих категорий.

По типу

Информация или данные

В В информатике упорядочивание в упорядоченной последовательности называется «сортировкой». Сортировка — обычная операция во многих приложениях, и эффективные алгоритмы для ее выполнения разработаны .

Наиболее распространенные варианты использования отсортированных последовательностей:

повышение эффективности поиска ;
повышение эффективности объединения последовательностей ;
возможность обработки данных в определенном порядке.

Противоположность сортировке, перестановка последовательности элементов в случайном или бессмысленном порядке, называется перетасовкой .

Для сортировки можно указать либо слабый порядок «не должен идти после», либо строгий слабый порядок «должен идти раньше» (указание одного определяет также другой, оба являются дополнением, обратным друг другу, см. операции над бинарными отношениями ). Чтобы сортировка была уникальной, эти два параметра ограничиваются общим порядком и строгим общим порядком соответственно.

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

Например, элементами являются книги, ключом сортировки является название, тема или автор, а порядок — в алфавитном порядке.

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

Например, адреса можно сортировать, используя город в качестве первичного ключа сортировки и улицу в качестве вторичного ключа сортировки.

Если значения ключа сортировки полностью упорядочены , ключ сортировки определяет слабый порядок элементов: элементы с одинаковым ключом сортировки эквивалентны в отношении сортировки. См. также стабильную сортировку . Если разные элементы имеют разные значения ключей сортировки, это определяет уникальный порядок элементов.

Стандартный порядок часто называют возрастающим (что соответствует тому факту, что стандартный порядок чисел является возрастающим, т.е. от A до Z, от 0 до 9), а обратный порядок - по убыванию (Z к A, от 9 до 0). Для дат и времени возрастание означает, что более ранние значения предшествуют более поздним, например, 01.01.2000 будет отсортировано раньше 1.01.2001.

Общие алгоритмы

Сортировка пузырьком / ракушкой : поменяйте местами два соседних элемента, если они не в порядке. Повторяйте, пока массив не будет отсортирован.
Сортировка вставкой : сканируйте последовательные элементы на наличие неупорядоченного элемента, затем вставьте его в нужное место.
Сортировка выбором : найдите самый маленький (или самый большой) элемент в массиве и поместите его в нужное место. Поменяйте его на значение в первой позиции. Повторяйте, пока массив не будет отсортирован.
Быстрая сортировка : разделите массив на два сегмента. В первом сегменте все элементы меньше или равны значению поворота. Во втором сегменте все элементы больше или равны значению поворота. Наконец, рекурсивно отсортируйте два сегмента.
Сортировка слиянием : разделите список элементов на две части, отсортируйте две части по отдельности, а затем объедините их.

Физический

Различные задачи сортировки необходимы в промышленных процессах, таких как переработка полезных ископаемых . Например, во время добычи золота из руды устройство, называемое вибростолом, использует силу тяжести , вибрацию и поток для отделения золота от более легких материалов в руде (сортировка по размеру и весу). Сортировка также является естественным процессом, в результате которого происходит концентрация руды или осадка . Сортировка является результатом применения некоторого критерия или дифференциальных стрессоров к массе для разделения ее на компоненты на основе некоторого переменного качества. Материалы, которые отличаются, хотя и незначительно, такие как изотопы урана, очень трудно разделить.

Оптическая сортировка — это автоматизированный процесс сортировки твердых продуктов с использованием камер и/или лазеров, который широко используется в пищевой промышленности. ^{[ нужна ссылка ]} Сенсорная сортировка используется при переработке полезных ископаемых. ^[1]

См. также

Справка:Сортировка в таблицах Википедии. Для сортировки категорий см. Википедию:Категоризация#Ключи сортировки , а для сортировки разделов статей см. WP:ORDER.
Сортировка
Обработка данных
Сортировка/объединение мэйнфреймов IBM
Алгоритм сопоставления Unicode
Ноллинг
5S (методология)

Ссылки

^ Дипак Малхотра (2009). Последние достижения в проектировании заводов по переработке полезных ископаемых . МСП. ISBN 978-0-87335-316-8 .

Внешние ссылки

Демонстрация алгоритмов сортировки (включая пузырьковую и быструю сортировку)
Анимированное видео, объясняющее пузырьковую сортировку и быструю сортировку, а также сравнение их производительности.

[Malhotra2009-1] Дипак Малхотра (2009). Последние достижения в проектировании заводов по переработке полезных ископаемых . МСП. ISBN 978-0-87335-316-8 .

[1]