MTD>>>Выбор опорной точки не поможет.
Q>>Как это не поможет?
MTD>Да вот так. На отсортированных данных как опорные точки не ставь скорость алгоритма деградирует до квадратичной.
Почему это ?? Тривиальный выбор опорной точки (arr[l + (r — l) / 2]) на отсортированной последовательности делит массивы всегда пополам, никакого квадрата не будет. Худший случай — это массив типа: 1,2,...,X-1,X,X-1,...,2,1.
MS в этом месте споткнулась (правда в .NET'е) https://github.com/dotnet/corefx/issues/24110
Да: «The unordered associative containers defined in 26.5 use specializations of the class template hash (23.14.1) as the default hash function.» 23.14.15
MTD>Конечно, конечно, это же я с ходу сказал, что оппонент не читал тему.
Так ведь это немного досадно: кто-то тратит время, отвечает автору вопроса (не оппоненту!). А тот не читает, а просто начинает спорить с какими-то выцепленными из комментария словами.
MTD>Еще тебе надо почитать... про быструю сортировку, еще про стоимость операций. Не благодари. MTD>>>Выбор опорной точки не поможет. MTD>На отсортированных данных как опорные точки не ставь скорость алгоритма деградирует до квадратичной.
Слышал звон? На отсортированных данных ты получишь квадратичную сложность, если в качестве опорного будешь выбирать крайний элемент отрезка. Если будешь выбирать случайный, или хотя бы средний как в школьном учебнике, то никакой квадратичной сложности там не будет.
Зачем ты вообще начал под***ывать Быстрой Сортировкой, если твои познания в этой области столь фрагментарны? Ещё и отсылает почитать, смотри на него.
Здравствуйте, Jack128, Вы писали:
J>Почему это ?? Тривиальный выбор опорной точки (arr[l + (r — l) / 2]) на отсортированной последовательности делит массивы всегда пополам, никакого квадрата не будет. Худший случай — это массив типа: 1,2,...,X-1,X,X-1,...,2,1.
Тут ты прав, я выразился не точно. Если брать крайний опорный элемент — деградируем на упорядоченных, если брать средний — на упорядоченных горкой, если брать рандом — ну как повезет. В любом случае алгоритм чувствителен к входным данным.
Здравствуйте, Qbit86, Вы писали:
Q>Да: «The unordered associative containers defined in 26.5 use specializations of the class template hash (23.14.1) as the default hash function.» 23.14.15
Тут написано, что неупорядоченные ассоциативные контейнеры используют специализации шаблонного класса hash как хеш-функцию по умолчанию. Здесь не сказано, что нельзя использовать этот класс просто для получения хеша. Тебе правда понадобился перевод, сам не понял?
Q>Зачем ты вообще начал под***ывать Быстрой Сортировкой, если твои познания в этой области столь фрагментарны? Ещё и отсылает почитать, смотри на него.
Ух ты как бомбануло — это хорошо На самом деле ты сам виноват — сначала сморозил про использование хеша для вычисления контрольной суммы, потом назвал детскими алгоритмы зависимые от входных данных, то есть чуть более чем дофига широко используемых. Кто тебя за язык тянул в борьбе со мной? А самое главное, ну не понравилось тебе мое мнение, что так взъелся-то?
