Подскажите пожалуйста какой массив будет сортироваться быстрой сортировкой максимальное вермя? (В качестве опорного элемента выбирается средний элемент)

Это сообщение отредактировал(а) lucyk - 28.10.2008, 18:54

В котором на каждом шаге будет выполняться обмен.

Покажите пожалуйста пример

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

"Быстрота" быстрой сортировки заключается в разделении массива на примерно 2 равные подмасива. Если бы нам было гарантировано, что наш опорный элемент (взятый за константное время) всегда разобьет массив на 2 равные части, то алгоритм бы работал всегда O(n*logn) ( T(n) = T(n/2) + T(n/2) + n, если посчитать , что по идее должно получиться n*logn ).

Поэтому худший случай - когда опорным всегда выбирается такой элемент массива, который разобьет массив на 2 подмассива - 1 элемемент и остальные (n-1) и уже они идут на сортировку.


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

Добавлено через 47 секунд

Если всегда выбирать в качестве опорного не случайный по порядку, а первый элемент, то да.

Вроде когда-то давно мне попадалась именно такая олимпиадная задача.
Вот её условие:


Не знаю как решали эту задачу другие, а я написал перебор, выдающий все такие "плохие" перестановки, и долго вкуривал их. Через пару часов выявил одну из закономерностей, и закодил её:

maxdiver, 
Программа почему-то не работает: например для N=5 выводит 4(должно быть 10). Может есть другие идеи??

Это сообщение отредактировал(а) jessica - 3.9.2011, 09:43

Для этого нужен как минимум исходник QuickSort для конкретной целевой платформы/либы.
Потому как внутреннее устройство QuickSort зависит от реализации.

У вероятностной  реализации быстрой сортировки нет плохих массивов в принцепе, именно ее и используют

Вы дадите гарантию что при любом порядке входного массива сортировка будет идти с абсолютно одинаковой скоростью, вплоть до процессорного такта?   

jessica, может быть, у Вас немного другой алгоритм быстрой сортировки? Там же всё очень зависит от деталей.

esperanto, ну если включить "зануда-mode" - то сама по себе применяемая псевдо-рандомность не поможет, поскольку, зная алгоритм псевдо-рандома и его начальные параметры, можно сделать anti-тест и против такой сортировки. Так что если автор программы не позаботился о хитром rand-seed, сгенерить тест против программы будет вполне реально.

Кстати, вот легко читаемая статья по этому поводу: "A Killer Adversary for Quicksort".

Я такого не говорил. И гарантию не дам.))