Сортировка текста пузырьком.

Помогите пожалуйста с задачкой. - Используя простейшие сортировки отсортировать предложенный файл. Сортировка Пузырьком. Пояснение к заданию: на вход программы поступает файл, input.txt, после всех преобразований результат помещается в файл, output.txt. файл может быть любым. - Файл txt c какой-то немаленькой повестью или рассказом. Спасибо.

0

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

1

да, это вопрос. Тогда я вряд ли смогу помочь, это нужно динамическую память использовать, наверное, а я с ней как-то не очень. Ну, сделаю что смогу, пусть кто сможет, сделает точнее.

1

кот Бегемот, А какая разница как выделять память, вопрос в том, что расчитывается, что её не хватит. Я предлагаю ещё один способ, но он сложный в реализации и его я писать не буду, за неимением на то времени. Способ вот какой, нам ведь нужно отсортировать слова? Тогда реализуем внешнюю сортировку очень похожую на обычную сортировку пузырька. Что-то вот в таком духе:
1)Берём слово из файла
2)Берём следующее слово
3)Сравниваем их (по поводу прописных и строчных букв я уже говорил). Если надо меняем слова местами. идём в пункт 2
4)Когда просмотрим весь текст, идём в пункт 1 и берём уже следующее слово.

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

1

Ну, это не совсем пузырьковая сортировка, да и, ты прав, работать будет очень медленно.

1

кот Бегемот, эм, это именно пузырька сортировка, ну получается два цикла сложность O(N^2) ну и + время на считывание разбор слова и т.д.

1

Да, в принципе-то, тот же пузырёк, но гемороя с ним будет... Нет, лучше уж с массивом слов.

1

кот Бегемот, Да, я знаю, с массивом намного проще. И для массива можно организовать какой-нибудь QuickSort, ну а потом записать обратно в файл. Массив уже предлагался, так что подождём ответа автора.

1

Препод сказал использовать любую структуру (список, массив, динамич. и т.д.) главное чтобы после выполнения проги получился файл (output.txt) с отсортированным исходным текстом (input.txt). Сортировка пузырьковая все слова текста в алфавитном порядке. знаки препинания не учитывать. вот как-то так).

Добавлено через 8 часов 10 минут
?????

0

Нет. Всё сложнее, чем я думал. Вряд ли я смогу чем-то помочь вам. Возможно, помогут другие.

1

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

0

Разумеется, ваш препод более компетентен, чем я, я всего лишь любитель. Максимально, что я могу сделать - отсортировать файл из 255 слов. Чтобы отсортировать более объёмный текст, надо уметь работать с динамическими массивами, или обладать более глубокими знаниями, чем простой любитель.


Если она так легко решается, хотел бы увидеть когда-нибудь её решение.

1

Как появиться вариант (один товарищ обещал попробовать с помощью списков сделать) выложу здесь.

0

SerjD, а какая разница где хранить слова (в списках, в стеке, в дереве, в графе)? Весь вопрос в том, что не хватает памяти для загрузки всего файла в память, как я понимаю? Это так или нет ?

0

lexus_ilia,
заводим 2мерный динамический массив. В первом измерении храним СЛОВО, а во втором первую букву этого слова в нижнем регистре, а уже потом сортируем по второму измерению, а выводим по первому. Как-то так должна решаться задачка

Добавлено через 22 часа 1 минуту
Ну что никто не сможет таким образом слепить прогу?

0

А зачем тогда усложнять, если можно использовать массивы? Заведите себе одномерный массив и сортируйте по первой букве.

0

Хм... а зачем вообще заводить массив ? Насколько я понял нужно построчно сортировать сортировать слова в файле, а поэтому читаем строку, сортируем строку, записываем в output и так пока не конец файла. Или я что-то всё таки упустил...

0

Inadequate,
нужно отсортировать слова в файле но не построчно а все слова по алфавиту

Добавлено через 3 минуты
а вот он файл для сортировки
http://disk.tom.ru/tcrhy47

0

SerjD, у тебя же написано, что нужно отсортировать слова по алфавиту в файле построчно. Разве нет ?

0

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

0

да построчно не принимают нужна сортировка всех слов

0