Как верно реализовать внешнюю сортировку естественным слиянием с порогом?

Question

[EAVol]

Здравствуйте, форумчане! Задали мне вот такую задачку: реализовать внешнюю сортировку естественным слиянием. Есть примерное начало работы программы: случайно генерируется, например, 10К структур имеющих 5 полей (2 строковых и 3 числовых). Затем, полученный массив записывается в файл (test.txt). Далее генерируется случайное число до 1000 - назовем его Z. Затем нужно переписать Z строк основного файла (test.txt) в другой файл (каждый следующий файл новый), предварительно отсортировав по возрастанию. Повторяется генерация числа, сортировка и запись до тех пор, пока не перепишем все 10К структур. Затем нужно начать процедуру слияния файлов. С Merge вроде всё ясно - простое слияние 2-х массивов. Но не могу понять, как описать Split. Подскажите, пожалуйста.

Comments

[microphone]

"слитие" улыбает.

[EAVol]

я, конечно, рад что вы улыбаетесь, но хотелось бы ответов по существу, а не флуда

Answer 1

[microphone]

а сортируется по возрастанию структуры или строки или внутри строк элементы массива?
размерности заданы?
если сортировки, то тут АВЛ дерево скорее всего подойдет.

Comments

[EAVol]

Сортируется по 3-м полям в структуре. Номера полей пользователь задает с клавиатуры. Определение того, какая структура "больше" выполняет компаратор. Сортировка серии размером Z производится с помощью быстрой сортировки.

[microphone]

да делить можно банально, если это перевод коретки то это вполне однозначный символ, отсчитал себе Z символов, вот тебе предел одного фала, отсчитал еще Z -следующий, символ кнонца строки бывает двух видов.

[microphone]

Если структура в файле не имеет символа конца строки, для отделения элементов массива, но имеет фиксированный размер, обычно множат размер одной ячейки на количество, так и получают нужный сдвиг элемента.

Answer 2

[Mrrl]

Не очень понятно, зачем здесь Z. Если 1000 структур помещается в памяти, и мы их можем отсортировать, то казалось бы - читаем из файла 10 раз по 1000 структур (по порядку, за один проход), каждый раз структуры сортируем и в отсортированном порядке помещаем в новый файл. Всего получается 10 файлов. Дальше - обычный merge. Кстати, слить можно сразу все 10 файлов, если их можно открыть одновременно. Если нет - сливаем два самых маленьких файла, пока не останется один (выгодно, чтобы сливаемые файлы были примерно одинакового размера - как группы символов в коде Хаффмана).
Возможно, Z придумали, чтобы файлы были не совсем одинаковыми, чтобы алгоритм не закладывался на одинаковость размера. Но тогда лучше было бы, например, "случайное число от 500 до 1000". В любом случае, если брать не максимум, то алгоритму только хуже.