Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.216.233.58] |
|
Сообщ.
#1
,
|
|
|
Известно, что у "быстрой" сортировки (QuickSort) среднее число сравнений пропорционально O(N*logN). Хотя с дополнением, что для некоторых случаев оно стремится к O(N^2). Но нигде не сказано, как получить такой пример!
Мой вопрос сводится к тому, как работают генераторы "плохих" тестов для сортировок. Можно ли написать программу, которая для некоторго метода сортировки с сложностью O(N*logN) выдает пример входных данных, при которых сложность становится O(N^2)? |
Сообщ.
#2
,
|
|
|
помоему ето ересь!! у быстрой сортировки не может быть больше чем O(N*logN)! наверное ето ещё у какоголибо метода
|
Сообщ.
#3
,
|
|||
|
2 wormball В быстрой сортировке массив разделяется на 2 части: элементы, меньшие заданного ключа - в одну, а большие - в другую. Потом эти части сортируются отдельно и склеиваются вместе. Фишка в том, что может получиться так, что на каждом шаге массив из N элементов будет делиться на 2 подмассива: из 1 элемента и из (N - 1) элемента. Так понадобится O(N) сортировок, что дает суммарное время O(N^2). O(N*logN) - это когда массив всегда делится на 2 примерно равные по размеру части. 2 Lucifer: Это серьезно, или тонкий юмор?! Вот, например, какой самый "плохой" тест для quicksort-а из Паскаля?
|
Сообщ.
#4
,
|
|
|
А причем здесь мама и папа?
PS: тема уходит в offtopic... |
Сообщ.
#5
,
|
|
|
ну тогда я думаю ето просто числа, расположенные в обратном порядке.
|
Сообщ.
#6
,
|
|
|
Тогда quicksort из раскидает за один проход!
Т.е. более N сравнений, IMHO, не будет. |
Сообщ.
#7
,
|
|
|
Да не обязательно в обратном... Просто в некоторых реализациях быстрой сортировки медиана (тот елемент, справа от которого и слева от которого...) выбирается случайным образом. Поетому генератором "плохих" входных последовательностей, на самом деле является математический объект, который фсе привыкли называть "демон". Ен точно знает, какая последовательность будет самой плохой. И неважно откуда, лишь бы выполнялось условие существования етой самой плохой последовательности.
Если медиана выбирается каким-то определенным образом, надо разместить елементы массива так, чтобы ета самая медиана не делила массив на части. (т.е., всегда оказывалась минимальным или максимальным елементом сортируемой подпоследовательности). |
Сообщ.
#8
,
|
|||
|
ты ещё скажи шайтан тогда наоборот: чтобы они уже были в правильном порядке рассортированы. тоесь она поймёт, что все последующие числа больше первого, и честно вызовет саму себя с массивом, меньшим на один элемент. кстати если они в обратном порядке, так тоже произойдёт. |
Сообщ.
#9
,
|
|
|
Не, тогда сложность логарифмической останется....
|
Сообщ.
#11
,
|
|||
|
почему?? |
Сообщ.
#12
,
|
|
|
Дык массив так и будет делиться пополам на каждой итерации...
|
Сообщ.
#13
,
|
|
|
в томто и дело, что так он будет делиться не пополам, а будет делиться на часть нулевого размера и часть, где будет почти весь массив. а потому она претерпит n самовызовов, и сложность будет n^2.
|
Сообщ.
#14
,
|
|
|
Да, можно в процедуру сортировки вставлять проверку "а не отсортирован ли уже массив?", и тогда некоторые часные случаи будут обрабатываться сами собой. Обычно для алгоритмов сортировки условие конца работы несколько проще.
|
Сообщ.
#15
,
|
|
|
ну ето будет имхо глупость, так ещё более замедлится. можно делить не первым, а средним элементом. а есь ещё помнится двухсторонняя быстрая сортировка.
|
Сообщ.
#16
,
|
|
|
Брр... А как медиана-то выбирается тогда, если не пополам?
|
Сообщ.
#17
,
|
|||
|
От выбора медианы зависит только пример плохого теста. Какую бы мы медиану не выбрали бы, всегда можно будет получить сложность N^2. Часто медиану считают так: med:=(a[l] + a[r] + a[(l+r) div 2]) div 3; |
Сообщ.
#18
,
|
|
|
Помогите!!!! Кто знает алгоритм БЫСТРОЙ СОРТИРОВКИ???????
|
Сообщ.
#19
,
|
|
|
Код - Быстрая сортировка (сообщение #261491)
Алгоритм - берем массив, выбираем медиану X. Расбрасываем числа так, чтобы слева от медианы были числа меньше X, а справа - больше X. Сортируем отдельно левую и правые части (рекурсивно тем же самым алгоритмом) |
Сообщ.
#20
,
|
|
|
Алгоритм - берем массив, выбираем случайный элемент массива X. Расбрасываем числа так, чтобы слева от медианы были числа меньше X, а справа - больше X. Сортируем отдельно левую и правые части (рекурсивно тем же самым алгоритмом)
|
Сообщ.
#21
,
|
|
|
Самый плохой тест (получено эмпирически) - если множество элементов массива состоит их 2 элементов - 0 и 1 или только их одного элемента. По поводу порядка их размещения я не знаю. Еще раз повторю, что это получено эмпирически.
|
Сообщ.
#22
,
|
|
|
Тут уже ссылку кинули на генератор квадратичных тестов для qsort, чтобы qsort работала достаточно быстро проще всего выбирать медиану для разбиения произвыольным образом, то есть рандомный элемент, тогда шанс, что qsort будет работать за квадратичное время будет ничтожно мал. Если надо еще увеличить скорость, то можно не сортировать массивы длиной менее C (С - некоторая константа). В итоге получим "почти сортированный" массив, который можнно отсортировать примитивным алгоритмом, который быстро сортирует "почти отсортированные" массивы. Выигрыш насколько я помню около 15%.
|
Сообщ.
#23
,
|
|
|
А есть версия алгоритма быстрой сортировки где в качестве индексов массива используются без знаковые (byte, word, cardinal) переменные?
|