Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.17.128.129] |
|
Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Сообщ.
#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) переменные?
|