IPB
ЛогинПароль:

> ВНИМАНИЕ!

Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Быстрая сортировка внутри файла txt
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 131
Пол: Мужской

Репутация: -  0  +


Задача состоит в том, чтобы реализовать быструю сортировку внутри txt файла, не используя массивы...все перестановки вести в файле...Может у кого есть наработки в это области....Заранее благодарен...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


code warrior
****

Группа: Пользователи
Сообщений: 484
Пол: Мужской
Реальное имя: Славен

Репутация: -  8  +


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


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

Код

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

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


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

Если запрещено использовать массивы, но можно использовать неограниченное количество файлов, то следует разбросать весь исходный файл по мелким файлам, каждый из которых содержит лишь одну строку, а затем из этх мелких файлов собирать выходной файл, содержащий строки в нужном порядке.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


Это почему ?


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

Группа: Пользователи
Сообщений: 131
Пол: Мужской

Репутация: -  0  +


Цитата(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);

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

Огромное спасибо...теперь у меня появились представления, как с этим работать....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


code warrior
****

Группа: Пользователи
Сообщений: 484
Пол: Мужской
Реальное имя: Славен

Репутация: -  8  +


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

Это почему ?

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

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

Сообщение отредактировано: hardcase -


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






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


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


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

Это почему ?

В этом случае можно менять строки на месте.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


не понимаю где проблема в перемене 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;


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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Цитата(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-й) позиции.

Сообщение отредактировано: andriano -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


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

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

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

seek(f, 1);
write(f, temp0);


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Да, но при этом, повторяю, у тебя получается не текстовый, а бинарный файл, что противоречит условию задачи.
С текстовым файлом, содержащим даже приведенные тобой в качестве примера строки, такое не выйдет.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 17:53
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name