Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Делфи _ Быстрая сортировка внутри файла txt

Автор: Vardes 19.04.2008 23:38

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

Автор: hardcase 20.04.2008 4:38

Имхо, очень глупо. Читаем содержимое файла в массив. Сортируем его. Перезаписываем файл новыми данными.

Автор: klem4 20.04.2008 13: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);

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

Автор: andriano 20.04.2008 13:27

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

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

Автор: klem4 20.04.2008 13:37

Цитата(andriano)
Она может иметь лишь решение в частном случсе, когда длина всех строк строго одинакова.


Это почему ?

Автор: Vardes 20.04.2008 15:05

Цитата(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 20.04.2008 15:18

Цитата(klem4 @ 20.04.2008 10:37) *

Это почему ?

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

Но этот весь цирк при перестановках только в исходном файле.

Автор: volvo 20.04.2008 15:59

Цитата
теперь у меня появились представления, как с этим работать....
Только учти, что все эти представления ничего общего с быстрой сортировкой не имеют (я про QuickSort, возможно именно это имелось в виду в названии темы?) ...

Автор: andriano 20.04.2008 17:40

Цитата(klem4 @ 20.04.2008 10:37) *

Это почему ?

В этом случае можно менять строки на месте.

Автор: klem4 20.04.2008 18: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;


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

Автор: andriano 20.04.2008 19:58

Цитата(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 21.04.2008 2:00

Действительно иллюзия получилась ... вот так нужно:


  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 21.04.2008 11:44

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

Автор: klem4 21.04.2008 12:10

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

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

Автор: andriano 21.04.2008 12:34

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