Форум на Исходниках.RU

Цитата

Да не обязательно в обратном... Просто в некоторых реализациях быстрой сортировки медиана (тот елемент, справа от которого и слева от которого...) выбирается случайным образом.

От выбора медианы зависит только пример плохого теста. Какую бы мы медиану не выбрали бы, всегда можно будет получить сложность N^2.
Часто медиану считают так: med:=(a[l] + a[r] + a[(l+r) div 2]) div 3; ]]> tserega Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261585 Thu, 11 Dec 2003 13:43:20 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261585 Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261582 Thu, 11 Dec 2003 13:42:24 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261582 wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261580 Thu, 11 Dec 2003 13:39:36 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261580 tserega Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261574 Thu, 11 Dec 2003 13:35:02 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261574

]]> wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261566 Thu, 11 Dec 2003 13:19:39 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261566 Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261562 Thu, 11 Dec 2003 13:15:59 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261562

Цитата

Visitor, 11.12.03, 16:07
Не, тогда сложность логарифмической останется....

почему?? ]]> wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261558 Thu, 11 Dec 2003 13:11:34 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261558 сюда! ]]> tserega Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261555 Thu, 11 Dec 2003 13:07:46 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261555 Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261527 Thu, 11 Dec 2003 12:38:47 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261527

Цитата

Visitor, 11.12.03, 15:22
математический объект, который фсе привыкли называть "демон"

ты ещё скажи шайтан

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

]]> wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261512 Thu, 11 Dec 2003 12:22:30 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261512

Если медиана выбирается каким-то определенным образом, надо разместить елементы массива так, чтобы ета самая медиана не делила массив на части. (т.е., всегда оказывалась минимальным или максимальным елементом сортируемой подпоследовательности). ]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261511 Thu, 11 Dec 2003 12:21:43 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261511

Т.е. более N сравнений, IMHO, не будет. ]]> tserega Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261508 Thu, 11 Dec 2003 12:17:40 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261508 wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261503 Thu, 11 Dec 2003 12:10:43 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261503
PS: тема уходит в offtopic... ]]> tserega Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261491 Thu, 11 Dec 2003 11:59:20 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261491 В быстрой сортировке массив разделяется на 2 части: элементы, меньшие заданного ключа - в одну, а большие - в другую. Потом эти части сортируются отдельно и склеиваются вместе. Фишка в том, что может получиться так, что на каждом шаге массив из N элементов будет делиться на 2 подмассива: из 1 элемента и из (N - 1) элемента. Так понадобится O(N) сортировок, что дает суммарное время O(N^2).
O(N*logN) - это когда массив всегда делится на 2 примерно равные по размеру части.

2 Lucifer:
Это серьезно, или тонкий юмор?!

Вот, например, какой самый "плохой" тест для quicksort-а из Паскаля?

procedure quicksort(var a: list; Lo,Hi: integer);

procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l; j:=r; x:=a[(l+r) DIV 2];
repeat
while a[i]<x do i:=i+1;
while x<a[j] do j:=j-1;
if i<=j then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

]]> tserega Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261479 Thu, 11 Dec 2003 11:43:44 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261479 wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261469 Thu, 11 Dec 2003 11:34:28 +0000 Быстрая сортировка https://forum.sources.ru/index.php?showtopic=40331&view=findpost&p=261469 среднее число сравнений пропорционально O(N*logN). Хотя с дополнением, что для некоторых случаев оно стремится к O(N^2). Но нигде не сказано, как получить такой пример!

Мой вопрос сводится к тому, как работают генераторы "плохих" тестов для сортировок. Можно ли написать программу, которая для некоторго метода сортировки с сложностью O(N*logN) выдает пример входных данных, при которых сложность становится O(N^2)? ]]> tserega Алгоритмы