|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Evgenij Masherov 2:5020/175.2 18 Dec 2001 10:33:55 To : Igor Grigoriev Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- Sun Dec 16 2001 02:59, Igor Grigoriev wrote to Yuriy Kaminskiy: YK>> Стандартными методами _внешней_ сортировки. YK>> Самое простое - разбиваем файл на куски, которые влезают в память, YK>> сортируем каждый кусок qsort, потом сливаем отсортированные YK>> куски. Примерно так, AFAIK, работает sort из gnu textutils на YK>> *больших* файлах. IG> Как сливаем, по подробнее? Если один в конец другого - то не верно, если IG> нет, то алгоритм с подсчетом сложности в студию. O(n) - вот и вся сложность... Два отсортированных куска (для определенности - по возрастанию), берем первые элементы, сравниваем, меньший пишем и продвигаемся по соответствующему файлу, затем продолжаем сравнивать вновь прочитанные (если в одном из файлов достигнут конец - переписываем остаток другого). Кстати, алгоритму этому, кажется скоро будет 100 лет - он был реализован в автоматическом подборщике перфокарт ИБМ в начале ХХ века... Евгений Машеров АКА СанитарЖеня --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/330007b8d4e7.html, оценка из 5, голосов 10
|