Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой.
Результат. Упорядоченнный по возрастанию список целых чисел, каждое из которых не превышает 10^7. На выходе должен быть получен файл отсортированных по возрастанию номеров.
Ограничения. ~1Мб ОП. место на диске не ограничено. время выполнения не должно превышать нескольких минут, если оно будет сокращено до нескольких секунд, то дальнейшая оптимизация не требуется.
Вот второй вариант сортировки (просто супер): 1) Читаем исходный файл насколько влазиет в память, потом сортируем и сохраняем во временный файл, следующая итерация чтения исходного файла также сортируется и заносится в следующий временный файл. Т.о. чем меньше памяти на данные мы выделяем, тем больше временных файлов. Сортировка проводится методом "Быстрой сортировки" описанной в FAQ и взятой от туда 2) Сливаем все временные файлы в итоговый, каждый раз выбирая минимальное значение среди прочтенных из всех временных файлов. Также везде буферный ввод вывод. Спасибо Volvo за FAQ и Michael_Rybak за метод сортировки слияниями файлов. См. пост 26
Итого: Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров). Время работы 3,421 сек. Кто еще быстрее? cool.gif Максимум выделяемой динамической памяти на данные не превысил 970372 байт. Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров). Программа - telsort2.zip ( 2.98 килобайт )
Кол-во скачиваний: 536
Параметры машины: теже
ЗЫ: К стати обновил первую версию - теперь повторяющихся номеров в итоговом файле не будет, даже если они были в исходном. См. пост 35. Во втором методе повторяющиеся номера не удаляются.
Цитата
Что такое битовая сортировка?
В принципе это то что говорил Altair в посте 32, только индексом является просто 1 бит. Именно поэтому это избавляет от дубликатов номеров при сортировке. А битовой я ее сам назвал из-за того, что индексный массив - битовый. Только не бейте меня за это, я еще учусь
Сообщение отредактировано: hiv -
--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
Правила форума
Оптимизация
