Эта тема на forum.dklab.ru


y0prst: Устойчива ли сортировка в PHP?
Для справки: сортировка называется устойчивой, если равные элементы сохраняют порядок после неё.
К сожалению, ничего не нашёл об этом в документации.
Константин Жинько [tIT]:
А что говорит эксперимент?
Евгений Галашин:
y0prst, если элементы равны, то какой у них может быть порядок? (-;
Константин Жинько [tIT]:
Евгений Галашин
Тот который был изначально.
y0prst:
А что говорит эксперимент?
Мммм... Эксперимент говорит, что неустойчивая.
Сам эксперимент:
<?
$a = array (
"0" => "100",
"1" => "101",
"2" => "102",
"3" => "102",
"4" => "100"
);
asort($a);
echo "<pre>";
print_r($a);
echo "</pre>";
?>

Вот что он выводит:
Array
(
[4] => 100
[0] => 100
[1] => 101
[2] => 102
[3] => 102
)
Я почему-то надеялся, что всё-таки сортировка будет устойчивой.
Хотя сейчас не могу вспомнить ни одного достаточно быстрого алгоритма устойчивой сортировки...
Константин Жинько [tIT]:
y0prst
Ну вот, видите, как все просто =))
Впрочем тему не зря создали -- наверняка будет много подобных вопросов в будущем %
Евгений Галашин:
y0prst,простите, а приведите пример, зачем это может понадобиться?
Ну и usort ещё никто не отменял... (-;
y0prst:
Евгений Галашин
Собственно, сам вопрос был навеян следующей ситуацией.
Мне необходимо было отсортировать команды в спортивном турнире по набранным очкам.
В случае равенства очков нужно было упорядочить команды по алфавиту.
Но.
Команды брались из БД уже отсортированными по алфавиту. Поэтому я и надеялся, что в случае равенства очков команды не "перемешаются".
Сейчас, естественно, запрос к БД никак не сортирует команды. Сравнение команд по имени заложено в пользовательской функции сравнения.
Eugene Babushkin:
Можно бес проблем написать свою сортирку (-;
Евгений Галашин:
y0prst, а почему нильзя сортировать данные как все, сразу при выборке? (-:
y0prst:
GreatWeb
Согласен, можно. Больше того, сначала именно так и было сделано. Просто недавно узнал о usort и сразу захотелось опробовать :-)
Евгений Галашин
На самом деле процедура сортировки команд не такая простая, как я её описал в первый раз. Идея состоит в том, что при равенстве очков у нескольких команд производится пересортировка с учётом только личных встреч. И так далее. Без рекурсии тут не обойтись. В общем, SQL отдыхает :-)

Кстати, тут я натолкнулся на один неприятный момент. Как можно было заметить, мне приходилось сортировать часть массива. Кажется, в php нет стандартных функций, делающих это. Поэтому пришлось писать довольно извратную функцию сравнения.

В общем, вопрос открыт: как отсортировать часть массива (с помощью стандартных функций сортировки)
Maus:
y0prst
Навскидку извратный вариант:
фильтр, отсеивающий часть массива, пихайте в $GLOBALS и в функции для usert() его используете...
WingedFox:
y0prst
Почему SQL отдыхает?
Приведите все правила сортировки =)
y0prst:
WingedFox
SQL отдыхает из-за рекурсии (хотя, может быть, я плохо знаю SQL? :)
В правила сравнения двух команд вдаваться не буду, так как они не очень простые. Да они и не нужны. Главное - что делать, если сравнение возвращает 0 (когда два элемента равны). Повторю: в этом случае получившаяся группа команд должна "пересортироваться" с учётом только личных встреч. Если опять все равны, то делать нечего, видно судьба у них такая :-)
Если же не все равны, но есть несколько равных, то с получившейся "подгруппой" нужно поступить точно также, то есть пересчитать очки с учётом только личных встреч. Налицо рекурсия.
WingedFox:
y0prst
Для этого можно, например, использовать последовательность из ORDER BY в запросе.
Она как раз и сортирует только те записи, которые равны ы предыдущем ORDER BY.
bæv:
Для этого можно, например, использовать последовательность из ORDER BY в запросе.

Э-э..
Для чего "для этого"?

Блин...
Между прочим, человек несколько раз подчеркнул:
пересортировка с учётом только личных встреч
группа команд должна "пересортироваться" с учётом только личных встреч

Вообще, представляете, как ведётся запись игр турнира, как считается итоговая таблица?
WingedFox:
baev
Для чего "для этого"?
Главное - что делать, если сравнение возвращает 0 (когда два элемента равны). Повторю: в этом случае получившаяся группа команд должна "пересортироваться" с учётом только личных встреч.
Вот для этого.
bæv:
Вот для этого.

Пример можно?
Хотя бы для восьми команд. Каждая с каждой, например, должна сыграть два раза -- дома и на выезде.
WingedFox:
Когда писал сие - была идея, как сделать.
Пока не могу вспомнить.

В общем, обещать не буду. Если получится - пример здесь выложу.
bæv:
Пока не могу вспомнить.

Случайно не вспомнили? (А то сезон уже начинается...)

Я, если честно, в таких случаях просто "ручками" таблицу подправляю -- вдруг в самом деле есть некий алгоритм?
WingedFox:
baev
Пока даже не начинал.
У меня сейчас на носу сдача проекта, так что несколько не до того =)

Я планирую на этих выходных поднять машину с сервером дома, тогда и займусь.
y0prst:
Кстати говоря, регулярный сезон российской баскетбольной суперлиги уже закончился (или остался 1 матч, не знаю точно). И регулярка НБА тоже подходит к концу...
На всякий случай, если вы займётесь этим вопросом, приведу цитату из официальных правил баскетбола (http://www.infobasket.ru/Doc/Rules2004/BasketballRules2004.pdf)
D – КЛАССИФИКАЦИЯ КОМАНД
D.1.1 Если имеются две команды с равным количеством очков, то для определения
мест должен(-ны) быть использован(-ы) результат(-ы) игры (игр) между этими
двумя командами.
D.1.2 Если в играх между двумя командами общее количество заброшенных и
пропущенных мячей одинаково, классификация определяется соотношением
заброшенных и пропущенных мячей во всех играх, проведенных в группе
каждой командой.
D.1.3 Если более двух команд при определении мест оказываются равными,
проводится вторая классификация. При этом принимаются во внимание
только результаты игр между командами, имеющими одинаковые показатели.
D.1.4 Если после второй классификации все еще сохраняется равенство команд,
тогда для определения мест учитывается соотношение заброшенных и
пропущенных мячей в играх между этими командами.
D.1.5 Если и после этого все еще сохраняется равенство команд, места должны
определяться с учетом соотношения заброшенных и пропущенных мячей по
результатам всех игр, проведенных в группе.
D.1.6 Если на любом этапе при использовании критериев, приведенных выше,
равенство нескольких команд сокращается до двух, то автоматически должна
быть применена процедура, приведенная в D.1.1 и D.1.2.
D.1.7 Если сохраняется равенство все еще более двух команд, процедура,
начинающаяся с D.1.3, повторяется.
D.1.8 Соотношение заброшенных и пропущенных мячей всегда подсчитывается
делением.

Эта тема на forum.dklab.ru