Помощь - Поиск - Пользователи - Календарь
Полная версия: Быстрая сортировка внутри файла txt
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Делфи
Vardes
Задача состоит в том, чтобы реализовать быструю сортировку внутри txt файла, не используя массивы...все перестановки вести в файле...Может у кого есть наработки в это области....Заранее благодарен...
hardcase
Имхо, очень глупо. Читаем содержимое файла в массив. Сортируем его. Перезаписываем файл новыми данными.
klem4
Да уж, без массива быстро врятли получится... Как вариант - переписать текст в типизированный of string и там уже работать любым методом, юзая seek, либо работать с текстовым примерно так:

Код

i := 1;
repeat
  if not(eof(f1))  then begin
    reset(f1);
    читаем "впустую" i - 1 записей
    начиная с i-й записи ищем минимальное значение в файле (проходим до конца)
    дописываем найденный минимум во второй файл (кооторый в итоге будет содержать отсортированные значения)
   i := i + 1;
end;
until eof(f1);

но это дико долго.
andriano
Задача в такой постановке принципиально не может быть решена в общем случае. Она может иметь лишь решение в частном случсе, когда длина всех строк строго одинакова.

Если запрещено использовать массивы, но можно использовать неограниченное количество файлов, то следует разбросать весь исходный файл по мелким файлам, каждый из которых содержит лишь одну строку, а затем из этх мелких файлов собирать выходной файл, содержащий строки в нужном порядке.
klem4
Цитата(andriano)
Она может иметь лишь решение в частном случсе, когда длина всех строк строго одинакова.


Это почему ?
Vardes
Цитата(klem4 @ 20.04.2008 10:18) *

Да уж, без массива быстро врятли получится... Как вариант - переписать текст в типизированный of string и там уже работать любым методом, юзая seek, либо работать с текстовым примерно так:

Код

i := 1;
repeat
  if not(eof(f1))  then begin
    reset(f1);
    читаем "впустую" i - 1 записей
    начиная с i-й записи ищем минимальное значение в файле (проходим до конца)
    дописываем найденный минимум во второй файл (кооторый в итоге будет содержать отсортированные значения)
   i := i + 1;
end;
until eof(f1);

но это дико долго.

Огромное спасибо...теперь у меня появились представления, как с этим работать....
hardcase
Цитата(klem4 @ 20.04.2008 10:37) *

Это почему ?

Задача решаема.
Но есть 2 МЕГАПРОБЛЕМЫ.
1) Каждый раз seek- до итой/житой-строки - тухлятинкой несет.
2) Поменять местами строки. - это надо, ТО, что между ними еще и сдвигать на разность длин тех строк. - тоже не весело, однако.

Но этот весь цирк при перестановках только в исходном файле.
volvo
Цитата
теперь у меня появились представления, как с этим работать....
Только учти, что все эти представления ничего общего с быстрой сортировкой не имеют (я про QuickSort, возможно именно это имелось в виду в названии темы?) ...
andriano
Цитата(klem4 @ 20.04.2008 10:37) *

Это почему ?

В этом случае можно менять строки на месте.
klem4
не понимаю где проблема в перемене 2-х строк различной длины


write(f, 'this is first string');
write(f, 'this is second string');

seek(f, 0); read(f, temp0);
seek(f, 1); read(f, temp1);

write(f, temp0);
seek(f, 0); write(f, temp1);

while not(eof(f)) do begin
read(f, temp0); writeln(temp0);
end;


Речь ведь об этом ?
andriano
Цитата(klem4 @ 20.04.2008 15:33) *

не понимаю где проблема в перемене 2-х строк различной длины


write(f, 'this is first string');
write(f, 'this is second string');

seek(f, 0); read(f, temp0);
seek(f, 1); read(f, temp1);

write(f, temp0);
seek(f, 0); write(f, temp1);

while not(eof(f)) do begin
read(f, temp0); writeln(temp0);
end;


Речь ведь об этом ?

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

PS. Да и сама программа делает совсем не то, что нужно автору, хотя и выдает на экран ВРОД БЫ искомый вариант.
На самом деле эта программа во 2-ю позицию (нумерация с 0) вписывает first string, а в нулевую - second string. secod string при этом остается на прежней 1-й позиции. Затем мы читаем файл, начиная с 1-й (а не 0-й) позиции.
klem4
Действительно иллюзия получилась ... вот так нужно:


seek(f, 0);
read(f, temp0);

seek(f, 1);
read(f, temp1);

seek(f, 0);
write(f, temp1);

seek(f, 1);
write(f, temp0);
andriano
Да, но при этом, повторяю, у тебя получается не текстовый, а бинарный файл, что противоречит условию задачи.
С текстовым файлом, содержащим даже приведенные тобой в качестве примера строки, такое не выйдет.
klem4
Так один из предложенных мною вариантов подразумевал переписывание слов в типизированный файл, последующая его сортировка и обратная запись в txt.

Цитата(klem4)
Как вариант - переписать текст в типизированный of string и там уже работать любым методом, юзая seek, либо работать с текстовым примерно так:
andriano
Совершенно верно. Но я писал по поводу исходной задачи, а но по поводу твоего предложения изменить ее условие (что, в общем-то, вполне закономерно).
Я, кстати, предложил другой вариант - раскидать строки по отдельным файлам, после чего сорировать, например, слиянием.
Но ни тот, ни другой вариант не удовлетворяет поставленным в задаче условиям.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.