Какая разница между упорядочением и сортировкой?

Ответ 1

• " ordering" - это, в основном, набор правил, которые определяют, какие предметы появляются раньше или после каких других элементов. IE: элементы относительного порядка появятся, если они будут отсортированы. Для коллекций, обеспечивающих упорядочение, это упорядочение обычно указывается в терминах операторов сравнения (в частности, <), интерфейсов (a la Java Comparable<T>) или обратных вызовов сравнения и/или объектов функций (например, С++ std::less).

  Существуют также коллекции, описанные как " упорядоченные коллекции". Немного другое использование слова, но связанное с ним значение. Это означает, что коллекция представляет собой последовательность элементов и, следовательно, имеет некоторую встроенную концепцию порядка. (Контраст с, например, хэш-таблицами. Вы добавляете что-то в хеш-таблицу, вы понятия не имеете, где она появится, если вы когда-либо повторяете содержимое. С помощью упорядоченной коллекции вы знаете.) Списки, векторы, массивы и т.д. являются квинтэссенцией упорядоченных коллекций. Однако для примера, не являющегося списком, тип "массив" PHP - это фактически "упорядоченная карта" - тип словаря, где сохраняется порядок ключей. Ключи появляются в том порядке, в котором они были сначала вставлены (или в том порядке, в котором вы последний раз ставили их с помощью ksort() или тому подобного), когда вы перебираете массив.

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

Ответ 2

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

(Немного смешно, можно также говорить о "упорядочении" последовательности элементов, что означает то же самое, что и сортировка их в каком-то порядке, заданном упорядочением.)

UPDATE:

В терминах реализации хорошим примером могут быть стандартные контейнеры (например, map, http://en.cppreference.com/w/cpp/container/map), которые принимают дополнительный параметр шаблона который обеспечивает заказ. По умолчанию это значение std::less<Key> в случае карты. Если вам нужен собственный заказ, при создании карты вы используете другой тип компаратора и который используется вместо этого. Общим способом создания собственного компаратора является реализация небольшой структуры с bool operator()(const Key& lhs, const Key& rhs) const.

Ответ 3

IBM проводит различие между отсортированными и упорядоченными наборами:

Наборы могут быть отсортированы или упорядочены:

• Упорядоченный набор - это набор, элементы которого расположены в том порядке, в котором они были добавлены в набор. Обратите внимание, что так по умолчанию создаются наборы. Например:

  {int} S1 = {3,2,5}; 
  

  и

  ordered {int} S1 = {3,2,5};
  

  эквивалентны.

• Сортированный набор - это набор, в котором элементы расположены в их естественном, восходящем (или нисходящем) порядке. Для строк естественный порядок - лексикографический порядок. Естественный порядок также зависит от локали системы. Например:

  sorted {int} sortedS = {3,2,5};
  

  и

  ordered {int} orderedS = {2,3,5};
  

  эквивалентны, и итерация по отсортированным S или упорядоченным S будет иметь такое же поведение. Чтобы указать порядок убывания, вы добавляете ключевое слово reverse.

Кроме того, Национальное информационное партнерство предложило интерпретацию терминов Национальному институту стандартов и технологий в 2002 году:

ВОПРОС:

В чем заключается различие между терминами "сортировка" и "упорядочение"?   Иногда слова используются взаимозаменяемо.

О

Хотя термины "сортировка" и "упорядочение" иногда используются   взаимозаменяемы в дискуссиях по ИТ-системам, они несколько отличаются   значения. Когда кто-то сортирует, один отделяет предметы от разных видов или   классы; когда один заказывает, один упорядочивает предметы в определенном   порядок.

Ответ 4

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

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

См. алгоритмы сортировки в wiki, которые дают временную сложность и их стабильность. Стабильный означает, что первоначальный заказ сохраняется.
https://en.wikipedia.org/wiki/Sorting_algorithm

Ответ 5

Рейтинг: сравнение для частичного определения расположения множества; возможно столкновение

rank1 = max({foo1.bar, foo2.bar})
rank2 = min({foo2.kite, foo2.kite})

Заказ: состав взвешенных ранжировок, позволяющий полностью и однозначно располагать набор без латентного столкновения; порядок вставки часто является резервным разрешением, когда только явное ранжирование недостаточно для подмножества

order = {
   ordering1 = (foo1.bar != foo2.bar) ? rank1(foo1, foo2) : ordering2(foo1, foo2)
   ordering2 = (foo1.kite != foo2.kite) ? rank2(foo1, foo2) : fallback(foo1, foo2)
}

Сортировка: расположение набора по порядку с использованием конкретной стратегии доступа и разбиения

 sort1 = strand(foo, order)
 sort2 = bubble(foo, order)

Сортировка: двоичное состояние компоновки для набора в соответствии с порядком (истинным или ложным)

is_sorted = {
  for (each foo)
    (is_ordered(foo(n), foo(n-1)) ? continue : return false;
  return true;
}

Ответ 6

Отношение порядка транзитивно. Соотношение сортировки нет.
Вы можете заказать последовательность целых чисел. Вы можете сортировать только набор, содержащий бананы, яблоки, ягоды...

Ответ 7

Мой удар в этом... Заказ определяется пользователем. Например, вы можете заказать набор строк на основе наиболее доступных, наиболее популярных и т.д. Сортировка "в общем" происходит из набора существующих методов ОС. Примеры включают сортировку набора строк в алфавитном порядке по языку строки.

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

Глядя на мой ответ, я думаю, что упорядочение и сортировка почти взаимозаменяемы. Тем не менее, я бы сказал, что упорядочение определяется пользователем, сортировка - это известная концепция. Например, мы все знаем, что сортировка списка имен приводит к сортировке по алфавиту. Если я хочу отсортировать список имен по собственному алгоритму, скажем, исходя из популярности, я представляю свой собственный алгоритм сортировки, который упорядочивает строки, как я считаю нужным. Итак, я бы сказал, если вы представите алгоритм, который сортирует, но заказывает сортировку по вашим собственным требованиям, тогда вы заказываете.

Ответ 8

Коллекция упорядоченная подразумевает концепцию нелетучего, видимого и воспроизводимого адреса или положения его элементов относительно друг друга. Сортировка, то это фактическое размещение элементов по некоторым произвольным критериям.

Ответ 9

В качестве слов они почти синонимы в контексте компьютерного кода. Например:

• SQL имеет предложение order by, поэтому ваши строки данных упорядочены.
• Java имеет интерфейс SortedSet и SortedMap, Collections.sort() для интерфейса List и метод Arrays.sort() для массивов.

Если бы я собирался указать разницу, то я бы сказал, что массив или java.util.List упорядочен, но не отсортированный.

Когда вы помещаете объекты в array или List, они сохраняют порядок, в котором они были помещены туда, и вы можете получить к ним доступ по индексу, но они не отсортированы, потому что упорядочение произвольное.

С java.util.SortedSet вы можете поместить объекты в любом порядке, который вам нравится, потому что он будет сортировать их по natural ordering или по формуле в java.util.Comparator. Однако вы не можете получить доступ к элементам по индексу. Это сделало бы их отсортированными, но не упорядоченными.