Подборка — это сборка письменной информации в стандартный порядок. Многие системы подборки основаны на числовом или алфавитном порядке , или их расширениях и комбинациях. Подборка — это фундаментальный элемент большинства офисных систем хранения , библиотечных каталогов и справочников .
Сортировка отличается от классификации тем, что сами классы не обязательно упорядочены. Однако, даже если порядок классов не имеет значения, идентификаторы классов могут быть членами упорядоченного набора, что позволяет алгоритму сортировки упорядочить элементы по классу.
Формально говоря, метод сортировки обычно определяет общий порядок для набора возможных идентификаторов, называемых ключами сортировки, что в результате создает общий предварительный порядок для набора элементов информации (элементы с одинаковым идентификатором не размещаются в каком-либо определенном порядке).
Алгоритм сортировки, такой как алгоритм сортировки Unicode, определяет порядок посредством процесса сравнения двух заданных строк символов и принятия решения о том, какая из них должна предшествовать другой. Когда порядок определен таким образом, можно использовать алгоритм сортировки для помещения списка из любого количества элементов в этот порядок.
Главное преимущество сортировки заключается в том, что она позволяет пользователю быстро и легко находить элемент в списке или подтверждать его отсутствие в списке. В автоматических системах это можно сделать с помощью алгоритма бинарного поиска или интерполяционного поиска ; ручной поиск может выполняться с использованием примерно похожей процедуры, хотя это часто будет делаться неосознанно. Другие преимущества заключаются в том, что можно легко найти первый или последний элемент в списке (что, скорее всего, будет полезно в случае числовых отсортированных данных) или элементы в заданном диапазоне (опять же полезно в случае числовых данных, а также с данными, упорядоченными по алфавиту, когда можно быть уверенным только в первых нескольких буквах искомого элемента или элементов).
Строки, представляющие числа, могут быть отсортированы на основе значений чисел, которые они представляют. Например, "−4", "2.5", "10", "89", "30,000". Чистое применение этого метода может обеспечить только частичное упорядочение строк, поскольку разные строки могут представлять одно и то же число (как в случае с "2" и "2.0" или, при использовании научной нотации , "2e3" и "2000").
Аналогичный подход можно использовать со строками, представляющими даты или другие элементы, которые можно упорядочить в хронологическом порядке или каким-либо другим естественным образом.
Алфавитный порядок является основой для многих систем сопоставления, где элементы информации идентифицируются строками, состоящими в основном из букв алфавита . Порядок строк зависит от существования стандартного порядка для букв рассматриваемого алфавита. (Система не ограничивается алфавитами в строгом техническом смысле; языки, использующие слоговую азбуку или абугиду , например чероки , могут использовать тот же принцип упорядочения при условии, что существует установленный порядок для используемых символов.)
Чтобы решить, какая из двух строк идет первой в алфавитном порядке, сначала сравниваются их первые буквы. Строка, первая буква которой появляется раньше в алфавите, идет первой в алфавитном порядке. Если первые буквы одинаковы, то сравниваются вторые буквы и так далее, пока порядок не будет определен. (Если в одной строке заканчиваются буквы для сравнения, то она считается первой; например, "cart" идет перед "carthorse".) Результатом расположения набора строк в алфавитном порядке является то, что слова с одинаковой первой буквой группируются вместе, а внутри такой группы группируются вместе слова с одинаковыми первыми двумя буквами и так далее.
Заглавные буквы обычно рассматриваются как эквиваленты соответствующих им строчных букв. (Альтернативные варианты обработки в компьютеризированных системах см. в разделе Автоматизированная сортировка ниже.)
При использовании алфавитного порядка могут применяться определенные ограничения, осложнения и особые соглашения:
В некоторых языках правила со временем изменились, поэтому старые словари могут использовать другой порядок, чем современные. Кроме того, сортировка может зависеть от использования. Например, немецкие словари и телефонные справочники используют разные подходы.
Некоторые словари арабского языка , такие как двуязычный словарь современного письменного арабского языка Ганса Вера , группируют и сортируют арабские слова по семитическому корню . [1] Например, слова китаба ( كتابة «письмо»), китаб ( كتاب «книга»), катиб ( كاتب «писатель»), мактаба ( مكتبة «библиотека»), мактаб ( مكتب «офис»), мактуб ( مكتوب «судьба» или «написанный») объединяются под трехбуквенным корнем k - t - b ( ك ت ب ), который означает «письмо». [2]
Другой формой сортировки является сортировка по радикалам и чертам , используемая для неалфавитных систем письма, таких как ханзи в китайском языке и кандзи в японском языке , чьи тысячи символов не поддаются упорядочению по соглашению. В этой системе определяются общие компоненты символов; они называются радикалами в китайском языке и логографических системах, полученных из китайского языка. Затем символы группируются по их первичному радикалу, затем упорядочиваются по количеству штрихов пера внутри радикалов. Когда нет очевидного радикала или более одного радикала, соглашение определяет, какой из них используется для сортировки. Например, китайский иероглиф 妈 (что означает «мать») сортируется как шестичертный символ под трехчертовым первичным радикалом 女.
Система радикалов и штрихов громоздка по сравнению с алфавитной системой, в которой есть несколько символов, все из которых однозначны. Выбор того, какие компоненты логографа включают отдельные радикалы и какой радикал является первичным, не является четким. В результате логографические языки часто дополняют упорядочивание радикалов и штрихов алфавитной сортировкой фонетического преобразования логографов. Например, слово кандзи Tōkyō (東京) можно отсортировать так, как если бы оно было написано японскими иероглифами слоговой азбуки хирагана как «to-u-ki- yo -u» (とうきょう), используя обычный порядок сортировки для этих символов. [ необходима цитата ]
Кроме того, китайские иероглифы также можно сортировать по штрихам . В Большом Китае порядок штрихов в фамилии является общепринятым в некоторых официальных документах, где имена людей перечислены без иерархии.
Когда информация хранится в цифровых системах, сопоставление может стать автоматизированным процессом. Тогда необходимо реализовать соответствующий алгоритм сопоставления , который позволит сортировать информацию удовлетворительным образом для рассматриваемого приложения. Часто целью будет достижение алфавитного или числового порядка, который следует стандартным критериям, описанным в предыдущих разделах. Однако не все эти критерии легко автоматизировать. [3]
Самый простой вид автоматизированной сортировки основан на числовых кодах символов в наборе символов , например, кодировке ASCII (или любом из ее надмножеств , например, Unicode ), при этом символы упорядочиваются в порядке возрастания их числовых кодов, и этот порядок распространяется на строки в соответствии с основными принципами алфавитного упорядочения (выражаясь математически, лексикографического упорядочения ). Таким образом, компьютерная программа может обрабатывать символы a , b , C , d и $ как упорядоченные $ , C , a , b , d (соответствующие коды ASCII: $ = 36, a = 97, b = 98, C = 67 и d = 100). Поэтому строки, начинающиеся с C , M или Z, будут сортироваться раньше строк со строчными буквами a , b и т. д. Иногда это называется ASCIIбетическим порядком . Это отклоняется от стандартного алфавитного порядка, в частности из-за расположения заглавных букв перед всеми строчными (и, возможно, обработки пробелов и других небуквенных символов). Поэтому он часто применяется с определенными изменениями, наиболее очевидным из которых является преобразование регистра (часто в верхний регистр, по историческим причинам [примечание 1] ) перед сравнением значений ASCII.
Во многих алгоритмах сортировки сравнение основано не на числовых кодах символов, а на ссылке на последовательность сортировки — последовательность, в которой символы, как предполагается, попадают с целью сортировки — а также на другие правила упорядочивания, соответствующие данному приложению. Это может служить для применения правильных соглашений, используемых для алфавитного упорядочения в рассматриваемом языке, правильного обращения с буквами с разным регистром, измененными буквами , диграфами , определенными сокращениями и т. д., как упоминалось выше в разделе Алфавитный порядок и подробно в статье Алфавитный порядок . Такие алгоритмы потенциально довольно сложны, возможно, требуя нескольких проходов по тексту. [3]
Тем не менее, проблемы все еще распространены, когда алгоритм должен охватывать более одного языка. Например, в немецких словарях слово ökonomisch находится между offenbar и olfaktorisch , в то время как турецкие словари рассматривают o и ö как разные буквы, помещая oyun перед öbür .
Стандартный алгоритм для сортировки любой коллекции строк, состоящих из любых стандартных символов Unicode , — это алгоритм сортировки Unicode . Его можно адаптировать для использования соответствующей последовательности сортировки для данного языка, настроив его таблицу сортировки по умолчанию. Несколько таких подгонок собраны в Common Locale Data Repository .
В некоторых приложениях строки, по которым сортируются элементы, могут отличаться от отображаемых идентификаторов. Например, The Shining может быть отсортирован как Shining, The (см. Алфавитный порядок выше), но может быть все равно желательно отображать его как The Shining . В этом случае можно сохранить два набора строк: один для отображения, а другой для сортировки. Строки, используемые для сортировки таким образом, называются ключами сортировки .
Иногда требуется упорядочить текст со встроенными числами, используя правильный числовой порядок. Например, «Figure 7b» идет перед «Figure 11a», хотя «7» идет после «1» в Unicode . Это можно распространить на римские цифры . Такое поведение не особенно сложно реализовать, если сортировать только целые числа, хотя это может значительно замедлить сортировку. Например, Microsoft Windows делает это при сортировке имен файлов .
Правильная сортировка десятичных дробей немного сложнее, поскольку в разных локалях используются разные символы для десятичной точки , а иногда один и тот же символ, используемый в качестве десятичной точки, также используется в качестве разделителя, например "Section 3.2.5". Универсального ответа на вопрос, как сортировать такие строки, не существует; любые правила зависят от приложения.
В некоторых контекстах числа и буквы используются не столько как основа для установления порядка, сколько как средство маркировки элементов, которые уже упорядочены. Например, страницы, разделы, главы и т. п., а также элементы списков часто «нумеруются» таким образом. Серии маркировки, которые могут использоваться, включают обычные арабские цифры (1, 2, 3, ...), римские цифры (I, II, III, ... или i, ii, iii, ...) или буквы (A, B, C, ... или a, b, c, ...). (Альтернативный метод обозначения элементов списка без их нумерации — использование маркированного списка .)
Когда буквы алфавита используются для перечисления , существуют определенные языковые соглашения относительно того, какие буквы используются. Например, русские буквы Ъ и Ь (которые на письме используются только для изменения предшествующего согласного ), а также обычно Ы , Й и Ё , опускаются. Кроме того, во многих языках, использующих расширенную латиницу , измененные буквы часто не используются при перечислении.
