По сути, сортировка требует линейного порядка .
Ваше отношение должно быть линейным, что означает:
- a ≤ a (рефлексивность)
- если a ≤ b и b ≤ a, то a = b (антисимметрия)
- если a ≤ b и b ≤ c, то a ≤ c (транзитивность)
- для всех a и b, a ≤ b или b ≤ a (совокупность)
Итак, что это значит? Большинство обычных отношений линейны. Например, если вы говорите о оценках, которые на самом деле являются действительными числами, то да, оценки могут быть линейно упорядочены. Рейтинги тоже, так как они опять-таки являются только действительными числами.
Но, например, если вы занимаетесь ранжированием шахматистов, вы не можете использовать их историю матчей. Если игрок A побил игрока B в большинстве своих матчей, а B снова победил C в большинстве своих матчей, это НЕ означает, что A> B> C, просто потому что C, возможно, победил A в большинстве своих матчей. матч.
Это, кстати, одна из причин, по которой существуют рейтинги Эло , им нужен был линейный порядок, чтобы отсортировать, кто лучший игрок, и заметить, что Эло в основном просто действительное число, таким образом, имеет линейный заказ.
Итак, для оценки экзамена у вас просто нет этого линейного порядка. Зачем? Это реальные цифры! Ну, правда, у вас есть этот линейный порядок, но вы не можете задать этот линейный порядок все, вы ограничены предварительно определенным списком сравнения, который находится здесь:
- Джон добился большего успеха, чем Джейн
- Джейн сделала хуже, чем Люк
- Люк справился лучше, чем Джейсон
- Джейсон сделал хуже, чем Тим
Итак, ответ: Нет, вообще, вы не можете отсортировать список, если у вас нет сравнения между какой-либо парой элементов.
Сейчас я работаю над "наименее плохим" ответом, но для меня это не тривиально ...
Редактировать: ОК, я что-то придумал. Идея состоит в том, что вы собираетесь извлечь максимально возможную информацию из вашего предварительно определенного списка сравнения. Затем рассматривайте любое сравнение, отсутствующее в расширенном списке сравнения, как равенство.
Итак, как ты это делаешь?
Сначала, для любого сравнения a. Затем вы просматриваете свой предопределенный список сравнения для любого сравнения a a. Если вы знаете, что нет равных (ни один учащийся не имеет одинаковую оценку), он закончен. Иначе, вы должны добавить все отношения рефлексивности и антисимметрии. Вы ничего не можете сделать с тотальностью. Теперь у вас есть расширенный список сравнения.
Теперь возьмите ваш любимый алгоритм сортировки. Если у вас его нет, quicksort приятно, эффективно и коротко написать. Затем каждый раз, когда алгоритм запрашивает сравнение между a и b, вместо этого смотрите на свой расширенный список сравнения. Если сравнение здесь, отлично, обработайте сравнение как a = b. (Обратите внимание, что не имеет значения, если вы знаете, что нет равенств, алгоритму все равно)
Результатом будет отсортированный список «наименее плохо». Обычно существует несколько возможных отсортированных списков «наименее плохо», но этот алгоритм даст вам только один.
Итак, давайте приведем пример. Это почти то же самое, что дано в ОП, с небольшой разницей («Джон сделал хуже, чем Люк» вместо «Джейн сделал хуже, чем Люк»). Итак, начнем с:
- Джон добился большего успеха, чем Джейн
- Джон сделал хуже, чем Люк
- Люк справился лучше, чем Джейсон
- Джейсон сделал хуже, чем Тим
Теперь, для каждого «X хуже, чем Y», я добавляю «Y лучше, чем X», и наоборот. Новые предложения выделены жирным шрифтом:
- Джон добился большего успеха, чем Джейн
- Люк справился лучше, чем Джон
- Люк справился лучше, чем Джейсон
- Тим добился большего успеха, чем Джейсон
- Джейнсделал хуже, чем Джон
- Джон сделал хуже, чем Люк
- Джейсон сделал хуже, чем Люк
- Джейсон сделал хуже, чем Тим
Наконец, я просматриваю все возможные предложения «X сделал лучше, чем Y» и «Y сделал лучше, чем Z», и добавляю «X сделал лучше, чем Z»
- Джон добился большего успеха, чем Джейн
- Люк справился лучше, чем Джон
- Люк справился лучше, чем Джейсон
- Тим добился большего успеха, чем Джейсон
- Люк справился лучше, чем Джейн
- Джейн сделала хуже, чем Джон
- Джон сделал хуже, чем Люк
- Джейсон сделал хуже, чем Люк
- Джейсон сделал хуже, чем Тим
- Джейн сделала хуже, чем Люк
Расширенный стол закончен.
Давайте теперь посмотрим на псевдокод быстрой сортировки:
function quicksort('array')
if length('array') ≤ 1
return 'array' // an array of zero or one elements is already sorted
select and remove a pivot value 'pivot' from 'array'
create empty lists 'less' and 'greater'
for each 'x' in 'array'
if 'x' ≤ 'pivot' then append 'x' to 'less'
else append 'x' to 'greater'
return concatenate(quicksort('less'), 'pivot', quicksort('greater'))
Отличие * от стандартной быстрой сортировки состоит в том, что вы вообще не можете знать ответ на вопрос if('x' ≤ 'pivot') .... Так что вместо этого, если x=Luke и pivot = Tim, вы ищите в своей таблице предложение «Люк сделал хуже, чем Тим». Если вы найдете его, то считаете, что ответ true и делаете append 'x' to 'less'. Если вы найдете в таблице «Люк сделал лучше, чем Тим», то вы считаете, что ответ ложный, и вы делаете append 'x' to 'greater'. И, наконец, если вы не можете найти ни одного из двух предложений, упомянутых выше, вы действуете как 'x' == 'pivot', и вы делаете append 'x' to 'less'