![]() |
|
Модераторы: Poseidon |
![]()
|
|
| ghoul_2007 |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 1 Регистрация: 8.4.2007 Репутация: нет Всего: нет |
Ссылка на условия задачи:
http://imcs.dvgu.ru/cats/main.pl?f=problem...&cid=500001 Буду рад если кто нибудь посоветует как вообще за 4 сек. отсортировать массив 1000000 эл-тов p.s. быстрая сортировка справляется за 30 сек. :( |
|||
|
||||
| Void |
|
|||
![]() λcat.lolcat ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 2206 Регистрация: 16.11.2004 Где: Zürich Репутация: 6 Всего: 173 |
Какая-то странная быстрая сортировка, 30 сек для такого объёма — это очень много, если только тесты не гоняются на Pentium-100.
Можно попробовать поразрядную сортировку, благо резерв по памяти огромный. -------------------- “Coming back to where you started is not the same as never leaving.” — Terry Pratchett |
|||
|
||||
| MBo |
|
|||
|
Бывалый ![]() Профиль Группа: Участник Сообщений: 234 Регистрация: 10.6.2002 Репутация: 7 Всего: 18 |
Значит, быстрая сортировка у тебя плохонькая, а исходный массив специально подобран так, чтобы создать наихудший квадратичный случай (например, множество дублированных ключей).
Есть 2 пути: 1) Cменить сортировку на MergeSort (если память позволяет), или HeapSort, для которых асимптотика O(NLogN) всегда выполняется 2) Найти приличный метод Partition, используемый в быстрой сортировке, который не боится дублированных ключей (сортированных массивов и др. хитростей) |
|||
|
||||
![]()
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |