| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [С++] сортировка массива |
| Автор: ghoul_2007 8.4.2007, 02:26 |
| Ссылка на условия задачи: http://imcs.dvgu.ru/cats/main.pl?f=problem_text&cpid=500038&sid=&cid=500001 Буду рад если кто нибудь посоветует как вообще за 4 сек. отсортировать массив 1000000 эл-тов p.s. быстрая сортировка справляется за 30 сек. :( |
| Автор: Void 8.4.2007, 02:59 |
| Какая-то странная быстрая сортировка, 30 сек для такого объёма — это очень много, если только тесты не гоняются на Pentium-100. Можно попробовать поразрядную сортировку, благо резерв по памяти огромный. |
| Автор: MBo 8.4.2007, 06:50 |
| Значит, быстрая сортировка у тебя плохонькая, а исходный массив специально подобран так, чтобы создать наихудший квадратичный случай (например, множество дублированных ключей). Есть 2 пути: 1) Cменить сортировку на MergeSort (если память позволяет), или HeapSort, для которых асимптотика O(NLogN) всегда выполняется 2) Найти приличный метод Partition, используемый в быстрой сортировке, который не боится дублированных ключей (сортированных массивов и др. хитростей) |