Сортировка длинного списка.

[Mtyn]

Здраствуйте,помогите мне пожалуйста разобраться  с программой.
Написать программу которая сортирует длинный список (файл прилагается),причем ф-цию сортировки нужно писать самому(
Если список очень длинный,то получается создать новый список и занести из файла данные в него не хватит памяти,если писать под Doc,подскажите возможные пути решения этой проблемы.

[Вад]

Не совсем понял - нужно сортировать очень большой файл, не помещающийся в памяти? Сортировка слиянием?
И при чём тут Borland C/C++?

[Алексей++]

стандартные методы не ведаю, а на ум приходит:

написать класс-менеджер, который позволит работать с файлом как с огромным байтовым массивом. Класс будет открывать файл страницами, при чтении тормозов будет мало, а вот при менянии строк местами будут небольшие тормоза (так как , возможно, придётся страницы активно переключать). Но зато - не зависим от размера озу )

[Mtyn]

Список огромен представим что к примеру 100000 фамилий,главное что б работала быстро и жрала мало памяти.Есть предположени сначала сортировать по 1-й букве,потом по 2-ой и так далеее.

[Finch]

Mtyn, Разбиваеш файл на несколько фрагментов. Отсортировываеш их, И затем как сказал Вад сортировка слиянием. Это же классика. Дональд Кнут "Искусство программирования" 3 том.

[Алексей++]

Mtyn, во, ещё вариант - организовать связанный список

 перебрать файл по записи и составить новый по принципу:

Код:

\r\n
#num1|next|prev|text\r\n
#num2|next|prev|text\r\n
#num3|next|prev|text\r\n

где
numX - идентификатор строки (например, поиск 57-й строки будет осуществляться как поиск строки "\r\n#57" ) !=0
next - идентификатор предыдущей строки (если не 0)
prev - идентификатор следующей строки (если не 0)

в составленном новом файле обеспечить, что цепь будет содержать строки по возрастанию. При редактировании , удалении и добавлении обеспечивать правильное расположение новой строки в цепи

[Finch]

Алексей1153++, А как ты примерно собираешся раздвигать файл. Mtyn, сказал, что у него 100 тысяч примерно записей. Отведем под каждую запись скажем 80 символов итого примерно 8 мегабайт только исходного файла. Кстати Mtyn 8 мегов это не слишком большой объем информации для современных компов, можно и напрямую в пасять полностью все считать, и затем сортировать.

[Алексей++]

Finch, только новый файл создавать, видимо

А насчёт размера в 8 метров - он же написал

Код:

если писать под Doc

полагаю, DOS имеется в виду

[Mtyn]

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

[Вад]

Mtyn, это смотря какой лимит по памяти ты себе поставил. А ну как фамилии, начинающиеся на какую-нибудь популярную букву, не влезут-таки в память? Этого никто не может гарантировать - сегодня у тебя 100 тыс. фамилий, завтра - 10 млн.

Тут я согласен с Finch, лучше (и надёжнее с точки зрения налагаемых тобой ограничений по памяти) разделить файл на блоки фиксированного размера (+- погрешность в 1 запись), сортировать каждый блок отдельно внутри себя (тем же quicksort, например), а потом сливать результат сортированных блоков воедино (возможно, установив ограничение на число одновременно сливаемых блоков - в каких-то случаях может потребоваться несколько итераций слияния, если уж очень много данных по отношению к объёму памяти).

[Алексей++]

одно не пойму - если блоки сортировались отдельно, то какой выигрыш получится ? Ведь, когда будем сливать, наступит та же фигня, что и с одним большим файлом

[Finch]

Леш не будет такой же фигни. С каждого отсортированного блока ты считываеш несколько первых записей. Потом береш первые записи со всех блоков. Записываеш самое наименьшее (наибольшее) значение. перемешаеш курсор блока на следуюшую запись. Если закончился лимит считанных записей в блоке, то просто дочитываеш блок дальше.

[Алексей++]

то есть это сначала надо много маленьких промежуточных файлов создать

[Вахмурка]

 Просто будет много открытых уже отсортированных файлов, с каждого считываем по записи, выбераем ту которая по алфатвиту должна идти первой, и записываем в файл вывода, указатель записи того файла из которого была взята фамилия на выход, перемещаем в перёд. Если какой-то файл закончился, работаем с оставшиемися. Всё это дело можно дополнительно ускорить используя буфер.

[Mtyn]

Спасиб за оказанную помощь,подскажите где найти справочник в котором описаны действия с бинарными файлами(чтение из файла,запись,вставка в файл и т.д

[Finch]

Mtyn, любой нормальный учебник по С++ тебе поможет. Самое главное, чтоб этот учебник не был из серии "С++ для чайников за 21 день". Там кроме "Взлет и посадка" (с) ничего и нет.